題1 單詞的壓縮編碼

描述

給定一個(gè)單詞列表，我們將這個(gè)列表編碼成一個(gè)索引字符串 S 與一個(gè)索引列表 A。
例如，如果這個(gè)列表是 [“time”, “me”, “bell”]，我們就可以將其表示為 S = “time#bell#” 和 indexes = [0, 2, 5]。
對于每一個(gè)索引，我們可以通過從字符串 S 中索引的位置開始讀取字符串，直到 “#” 結(jié)束，來恢復(fù)我們之前的單詞列表。
那么成功對給定單詞列表進(jìn)行編碼的最小字符串長度是多少呢？
示例：輸入: words = [“time”, “me”, “bell”]
輸出: 10
說明: S = “time#bell#” ， indexes = [0, 2, 5] 。
提示：
1 <= words.length <= 2000
1 <= words[i].length <= 7
每個(gè)單詞都是小寫字母 。

題解

思路：如果單詞集合中存在一個(gè)單詞是另一個(gè)單詞的后綴則這個(gè)單詞被壓縮，不計(jì)入最后的長度計(jì)算，相當(dāng)于我們需要做的是：1.創(chuàng)建集合給原單詞集合去重，2.刪除原單詞集合中的后綴單詞，3.統(tǒng)計(jì)單詞長度和，每個(gè)單詞后面還有#，需要加一。
定義集合
Set<String> myset = new HashSet(Arrays.asList(words))

class Solution {public int minimumLengthEncoding(String[] words) {Set <String> mySet = new HashSet(Arrays.asList(words));for(String word: words){for(int k = 1; k < word.length(); k++){mySet.remove(word.substring(k));}}int ans = 0;for(String word: mySet){ans += word.length() + 1;}return ans;} }

題2 最后一個(gè)單詞的長度

描述

給定一個(gè)僅包含大小寫字母和空格 ’ ’ 的字符串 s，返回其最后一個(gè)單詞的長度。如果字符串從左向右滾動(dòng)顯示，那么最后一個(gè)單詞就是最后出現(xiàn)的單詞。
如果不存在最后一個(gè)單詞，請返回 0 。
說明：一個(gè)單詞是指僅由字母組成、不包含任何空格字符的 最大子字符串。
示例:
輸入: “Hello World”
輸出: 5

題解1

思路：思路簡單，通過修用例bug實(shí)現(xiàn)，首先把字符串最后一個(gè)單詞后的所有空格去掉，然后根據(jù)空格來截取最后一個(gè)單詞的長度。
速度很慢內(nèi)存占用高
執(zhí)行用時(shí) :2 ms, 在所有 Java 提交中擊敗了17.69%的用戶
內(nèi)存消耗 :37.9 MB, 在所有 Java 提交中擊敗了5.06%的用戶

class Solution {public int lengthOfLastWord(String s) {int count = 0;int len = s.length();if(len == 0){return 0;}int space = 0;for(int i = len - 1; i >= 0; i--){if(s.charAt(i) == ' '){++space;}else{break;}}System.out.println(space);if(space > 0){len = len - space;}System.out.println(len);for(int i = len - 1; i >= 0; i--){if(s.charAt(i) != ' '){count++;}else{break;}}return count;} }

題解2

思路一致：速度提升
執(zhí)行用時(shí) :0 ms, 在所有 Java 提交中擊敗了100.00%的用戶
內(nèi)存消耗 :37.9 MB, 在所有 Java 提交中擊敗了5.06%的用戶

class Solution {public int lengthOfLastWord(String s) {int end = s.length() - 1;while(end >= 0 && s.charAt(end) == ' ') end--;if(end < 0) return 0;int start = end;while(start >= 0 && s.charAt(start) != ' ') start--;return end - start;} }

題3 二進(jìn)制求和

描述

給定兩個(gè)二進(jìn)制字符串，返回他們的和（用二進(jìn)制表示）。
輸入為非空字符串且只包含數(shù)字 1 和 0。
示例 1:
輸入: a = “11”, b = “1”
輸出: “100”
示例 2:
輸入: a = “1010”, b = “1011”
輸出: “10101”

題解 逐位求和

思路：大值用來控制外層循環(huán)，小值用來控制內(nèi)層循環(huán)，始終讓大值位于第一個(gè)參數(shù)，如果不符合，用return 交換一次參數(shù)位置。
carry用來保存進(jìn)位值，如果carry=2 則要進(jìn)位 當(dāng)前位置為0 否則為1，進(jìn)位之后carry/2=1用于下一步進(jìn)位值計(jì)算。
時(shí)耗和內(nèi)存都不佳，勉強(qiáng)算做出來

class Solution {public String addBinary(String a, String b) {int alen = a.length();int blen = b.length();if(blen > alen){return addBinary(b, a);}int L = Math.max(alen,blen);StringBuilder sb = new StringBuilder();int carry = 0; int j = blen-1;for(int i = L - 1; i >= 0; --i){if(a.charAt(i) == '1') ++carry;if(j >= 0 && b.charAt(j--) == '1') ++carry;if(carry % 2 == 0) sb.append('0');else sb.append('1');carry /= 2;}if(carry == 1) sb.append('1');sb.reverse();return sb.toString();} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode】3月28日打卡-Day13的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。