周末周末瘦黑，今天的目標(biāo)五道題就好~~~加油！

數(shù)組的度

題目：給定一個(gè)非空且只包含非負(fù)數(shù)的整數(shù)數(shù)組 nums, 數(shù)組的度的定義是指數(shù)組里任一元素出現(xiàn)頻數(shù)的最大值缘琅。你的任務(wù)是找到與 nums 擁有相同大小的度的最短連續(xù)子數(shù)組的猛，返回其長(zhǎng)度安皱。

示例 1:
輸入: [1, 2, 2, 3, 1]
輸出: 2
解釋:
輸入數(shù)組的度是2，因?yàn)樵?和2的出現(xiàn)頻數(shù)最大认然，均為2.
連續(xù)子數(shù)組里面擁有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短連續(xù)子數(shù)組[2, 2]的長(zhǎng)度為2补憾，所以返回2.
示例 2:
輸入: [1,2,2,3,1,4,2]
輸出: 6
注意:
nums.length 在1到50,000區(qū)間范圍內(nèi)。
nums[i] 是一個(gè)在0到49,999范圍內(nèi)的整數(shù)卷员。

思路：講真盈匾，我現(xiàn)在覺(jué)得難的不是題目本身或者思路，而且閱讀理解的水平毕骡。讀了兩遍題目大概覺(jué)得所謂的數(shù)組的度：就是數(shù)組中最多元素的個(gè)數(shù)削饵。這道題我理解的就是找到數(shù)組中包含最多元素個(gè)數(shù)的子串。比如 1 1 1 1 2 3 4 5 這個(gè)子串就是前面四個(gè)1.再比如1 01 2 1 3 1 4 1這個(gè)子串就是全串未巫。我不知道我說(shuō)明白沒(méi)有窿撬，反正我自己明白了。我去嘗試寫(xiě)代碼了叙凡。
說(shuō)一下思路：最笨的就是先獲取出現(xiàn)次數(shù)最多的元素值劈伴。然后判斷第一次出現(xiàn)和最后一次出現(xiàn)的位置，然后截取字串握爷。但是我目前的想要是要借助map來(lái)判斷跛璧。嘗試去寫(xiě)了严里。
寫(xiě)完回來(lái)了，首先這道題我的思路沒(méi)問(wèn)題追城，但是真寫(xiě)出來(lái)有點(diǎn)麻煩刹碾。其次性能超過(guò)百分之八十多，沒(méi)達(dá)到我心里預(yù)期漓柑。但是我已經(jīng)想好改進(jìn)的辦法了教硫，一會(huì)兒去試試，先把第一版本的代碼貼上來(lái)：

class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer,List<Integer>> map = new HashMap<Integer,List<Integer>>();
        int n = 0;
        int[] val = new int[nums.length];
        int index = 0;
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                List<Integer> list = map.get(nums[i]);
                list.add(i);
                map.put(nums[i],list);
                if(n<list.size()){
                    n = list.size();
                    index = 0;
                    val[index] = nums[i]; 
                    index++;
                }else if(n == list.size()){
                    val[index] = nums[i];
                    index++;
                }
            }else{
                List<Integer> list = new ArrayList<Integer>();
                list.add(i);
                map.put(nums[i],list);
            }
        }
        //數(shù)組中沒(méi)有重復(fù)元素辆布，每一個(gè)子串都是度
        if(index==0) return 1;
        int res = 50001;
        for(int x = 0;x<index;x++){
            List<Integer> list = map.get(val[x]);
            //最后一次出現(xiàn)的下標(biāo)減去第一次出現(xiàn)的下標(biāo)+1就是字串的長(zhǎng)度
            int temp = list.get(list.size()-1)-list.get(0)+1;
            res = res<temp?res:temp;
        }
        return res;
    }
}

寫(xiě)的比較墨跡，我改進(jìn)一下的茶鉴。改進(jìn)完了性能和消耗都更好了我能說(shuō)什么锋玲？我也很絕望啊！：！惭蹂！
看了第一的代碼，不能不說(shuō)這些數(shù)據(jù)結(jié)構(gòu)中割粮，數(shù)組是最簡(jiǎn)單方便快捷的處理方式了盾碗，性能不行用數(shù)組快成為真理了。這個(gè)性能第一的代碼用的數(shù)組處理舀瓢。我這里map的key是數(shù)字本身廷雅，value是list，用list的長(zhǎng)度判斷次數(shù)京髓，用list中的int記錄下標(biāo)航缀。而人家是用了三個(gè)數(shù)組，下標(biāo)代表元素來(lái)處理的堰怨！
說(shuō)不會(huì)有點(diǎn)過(guò)了芥玉，但是處理起來(lái)比較繞。而且沒(méi)有我上面的直觀备图，可是性能真的是好太多灿巧！我執(zhí)行下來(lái)31ms，人家用2ms揽涮。也不是很難抠藕，只不過(guò)一來(lái)是我沒(méi)想到那么做而已。接下來(lái)附上代碼：

class Solution {
    public int findShortestSubArray(int[] nums) {
        if (nums.length < 2) {
            return nums.length;
        }
        int max = 0;
        for (int i : nums) {
            max = Math.max(i, max);
        }
        int[] temp = new int[max + 1];
        int[] first = new int[max + 1];
        int[] last = new int[max + 1];
        int maxTime = 1;
        for (int i = 0; i < nums.length; i++) {
            temp[nums[i]]++;
            //這里如果這個(gè)元素第一次出現(xiàn)則在first數(shù)組中存儲(chǔ)绞吁，是第一次出現(xiàn)的下標(biāo)
            if (temp[nums[i]] == 1) {
                first[nums[i]] = i;
            }
            //肯定是越往后數(shù)字越大幢痘， 所以這個(gè)last中不斷替換，存儲(chǔ)的就是最后一次出現(xiàn)的下標(biāo)
            last[nums[i]] = i;
            //這個(gè)遍歷是記錄出現(xiàn)次數(shù)最多的次數(shù)個(gè)數(shù)
            maxTime = Math.max(maxTime, temp[nums[i]]);
        }
        int result = nums.length;
        for (int i = 0; i < max + 1; i++) {
            //只有本身是次數(shù)最多的元素才有必要判斷家破，
            if (temp[i] == maxTime) {
                result = Math.min(result, last[i] - first[i] + 1);
            }
        }
        return result;
    }
}

好了颜说，我自己理了一遍思路购岗，想法都寫(xiě)在注釋上了，這道題其實(shí)不難门粪，感覺(jué)考點(diǎn)是性能喊积，下一題吧。

二叉搜索樹(shù)中的搜索

題目：給定二叉搜索樹(shù)（BST）的根節(jié)點(diǎn)和一個(gè)值玄妈。 你需要在BST中找到節(jié)點(diǎn)值等于給定值的節(jié)點(diǎn)乾吻。 返回以該節(jié)點(diǎn)為根的子樹(shù)。 如果節(jié)點(diǎn)不存在拟蜻，則返回 NULL绎签。

題目截圖

思路：這道理怎么說(shuō)呢，感覺(jué)簡(jiǎn)單的離譜霸凸诡必？？是我想簡(jiǎn)單了么搔扁？因?yàn)槭嵌嫠阉鳂?shù)爸舒，所以遵循左小右大的原則，我現(xiàn)在的理解就是根據(jù)條件遍歷稿蹲。扭勉。我去試試有沒(méi)有坑吧。
試完了苛聘，完全沒(méi)坑涂炎，三分鐘搞定，性能超過(guò)百分百焰盗，確定他就是一道小白題璧尸！直接上代碼:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root==null) return null;
        if(root.val==val) return root;
        if(root.val>val) return searchBST(root.left,val);
        if(root.val<val) return searchBST(root.right,val);
        return null;
    }
}

哈哈，我都是順序刷的簡(jiǎn)單的題目熬拒，知道我周末不太愿意刷題所以給我湊題數(shù)的么爷光？希望接下來(lái)的幾道題都這么簡(jiǎn)單~~~

數(shù)據(jù)流中的第K大元素

題目：設(shè)計(jì)一個(gè)找到數(shù)據(jù)流中第K大元素的類(lèi)（class）。注意是排序后的第K大元素澎粟，不是第K個(gè)不同的元素蛀序。你的 KthLargest 類(lèi)需要一個(gè)同時(shí)接收整數(shù) k 和整數(shù)數(shù)組nums 的構(gòu)造器，它包含數(shù)據(jù)流中的初始元素活烙。每次調(diào)用 KthLargest.add徐裸，返回當(dāng)前數(shù)據(jù)流中第K大的元素。

示例:
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8
說(shuō)明:
你可以假設(shè) nums 的長(zhǎng)度≥ k-1 且k ≥ 1啸盏。

思路：先說(shuō)題目重贺，看了兩遍，認(rèn)真看了給的demo，才算是明白了是什么意思气笙。首先這個(gè)add不是一次性操作次企，而是add一次同一個(gè)對(duì)象的數(shù)組里就一直多這么一個(gè)元素了。其實(shí)這個(gè)題我感覺(jué)是實(shí)現(xiàn)簡(jiǎn)單潜圃，但是性能好的實(shí)現(xiàn)比較難缸棵，不然一個(gè)Arrays.sort就搞定了沒(méi)什么意義了。我去嘗試寫(xiě)代碼了谭期。
咳咳堵第，反正第一版代碼我用賊無(wú)腦的形式實(shí)現(xiàn)了，起碼先實(shí)現(xiàn)再優(yōu)化隧出，哈哈

class KthLargest {
    private int k;
    private List<Integer> list;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        list = new ArrayList<Integer>();
        for(int i:nums){
            list.add(i);
        }
    }    
    public int add(int val) {
        list.add(val);
        Collections.sort(list);
        return list.get(list.size()-k);   
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

不出所料的性能踏志，只超過(guò)百分之七的人。其實(shí)優(yōu)化點(diǎn)很多胀瞪，我這個(gè)版本也是為了測(cè)試我對(duì)題目的理解對(duì)不對(duì)狰贯。接下來(lái)我去真的實(shí)現(xiàn)了。
好了赏廓，進(jìn)化版出來(lái)了，依然排名二三十而已傍妒，完全數(shù)組實(shí)現(xiàn)了幔摸，直接貼代碼：

class KthLargest {
    private int[] arr;
    public KthLargest(int k, int[] nums) {
        arr = new int[k];
        Arrays.sort(nums);
        int j = k-1;
        int i = nums.length-1;
        if(j>i) arr[0] = Integer.MIN_VALUE;
        while(i>=0 && j>=0){
            arr[j] = nums[i];
            i--;
            j--;
        }
            
    }    
    public int add(int val) {
        if(val<=arr[0]) return arr[0];
        for(int i=arr.length-1;i>=0;i--){
            if(val>arr[i]){
                int temp = arr[i];
                arr[i] = val;
                val =temp;
            }
        } 
        return arr[0];
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLarges>t(k, nums);
 * int param_1 = obj.add(val);
 */

感覺(jué)唯一可能拖性能的也就是那個(gè)排序了，可是總不能我自己實(shí)現(xiàn)吧颤练？真的是腦殼痛既忆，我放棄優(yōu)化了，直接看人家性能好的怎么寫(xiě)的吧嗦玖。
看到了一個(gè)數(shù)據(jù)結(jié)構(gòu)：PriorityQueue患雇。
這個(gè)類(lèi)厲害了，自帶比較大小的隊(duì)列宇挫。
PriorityQueue使用跟普通隊(duì)列一樣苛吱，唯一區(qū)別是PriorityQueue會(huì)根據(jù)排序規(guī)則決定誰(shuí)在隊(duì)頭，誰(shuí)在隊(duì)尾器瘪。
有了這個(gè)屬性就不用自己比較了翠储，雖然還沒(méi)看源碼不知道人家怎么封裝的，但是看別人代碼用了這個(gè)類(lèi)幾乎就是一次搞定橡疼，我去寫(xiě)出來(lái)：

class KthLargest {
    private PriorityQueue<Integer> q;
    private int k;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        q = new PriorityQueue<Integer>(k);
        for(int i:nums){
            add(i);
        }            
    }    
    public int add(int val) {
        //如果還沒(méi)被填滿就順序往里填充元素
        //這種情況要么正在初始化援所，要么第一次調(diào)用add往里填充元素
        if(q.size() < k) {
            q.offer(val);   
        //如果已經(jīng)滿了，判斷第一個(gè)元素和val大小欣除，如果val較大才需要操作不談直接返回第一個(gè)就行             
        }else if(q.peek() < val) {
            q.poll();
            q.offer(val);
        }
        return q.peek();
    }
}
/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLarges>t(k, nums);
 * int param_1 = obj.add(val);
 */

順便看了一些 PriorityQueue類(lèi)的知識(shí)住拭，不過(guò)因?yàn)樵诩宜詻](méi)看源碼。先記下有空去看。覺(jué)得還是知道的少滔岳，早知道這個(gè)數(shù)據(jù)結(jié)構(gòu)還用廢那么久時(shí)間自己實(shí)現(xiàn)么~~

二分查找

題目：給定一個(gè) n 個(gè)元素有序的（升序）整型數(shù)組 nums 和一個(gè)目標(biāo)值 target 杠娱，寫(xiě)一個(gè)函數(shù)搜索 nums 中的 target，如果目標(biāo)值存在返回下標(biāo)澈蟆，否則返回 -1墨辛。

示例 1:
輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4
示例 2:
輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1
提示：
你可以假設(shè) nums 中的所有元素是不重復(fù)的。
n 將在 [1, 10000]之間趴俘。
nums 的每個(gè)元素都將在 [-9999, 9999]之間睹簇。

思路：這個(gè)題怕不是出錯(cuò)地方了吧？要是剛剛接觸算法可能還要想想寥闪，現(xiàn)在都用爛了好不好~~我去直接實(shí)現(xiàn)了太惠。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                right = mid-1;
            }else{
                left = mid+1;
            }    
        } 
        return -1;   
    }
}

就這樣了，反正也沒(méi)啥亮點(diǎn)疲憋，唯一算是坑的就是可能只有一個(gè)元素凿渊，所以left是可以等于right的。就是一個(gè)普通的二分法缚柳。

設(shè)計(jì)哈希集合

題目：不使用任何內(nèi)建的哈希表庫(kù)設(shè)計(jì)一個(gè)哈希集合埃脏。具體地說(shuō)，你的設(shè)計(jì)應(yīng)該包含以下的功能

add(value)：向哈希集合中插入一個(gè)值秋忙。
contains(value) ：返回哈希集合中是否存在這個(gè)值彩掐。
remove(value)：將給定值從哈希集合中刪除。如果哈希集合中沒(méi)有這個(gè)值灰追，什么也不做堵幽。

示例:
MyHashSet hashSet = new MyHashSet();
hashSet.add(1);
hashSet.add(2);
hashSet.contains(1); // 返回 true
hashSet.contains(3); // 返回 false (未找到)
hashSet.add(2);
hashSet.contains(2); // 返回 true
hashSet.remove(2);
hashSet.contains(2); // 返回 false (已經(jīng)被刪除)
注意：
所有的值都在 [0, 1000000]的范圍內(nèi)。
操作的總數(shù)目在[1, 10000]范圍內(nèi)弹澎。
不要使用內(nèi)建的哈希集合庫(kù)朴下。

思路:這道題怎么說(shuō)呢，我只能說(shuō)實(shí)現(xiàn)的方式很多苦蒿，但是性能是主要考慮因素殴胧。不然暴力實(shí)現(xiàn)感覺(jué)就跟投機(jī)取巧了似的。其實(shí)我覺(jué)得就是實(shí)現(xiàn)一個(gè)Set刽肠。我先想想怎么提高效率溃肪。靈機(jī)一動(dòng)，我決定用數(shù)組Ｒ粑濉惫撰！去寫(xiě)代碼了！
我現(xiàn)在愛(ài)死了我自己的靈機(jī)一動(dòng)躺涝。用數(shù)組實(shí)現(xiàn)了厨钻，數(shù)組下標(biāo)代表數(shù)字扼雏，貼代碼：

class MyHashSet {
    
    private int[] n;
    /** Initialize your data structure here. */
    public MyHashSet() {
        n = new int[1000001];
        n[0] = -1;
    }
    
    public void add(int key) {
        n[key] = key;
    }
    
    public void remove(int key) {
        n[key] = (key==0?-1:0);
    }
    
    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        return n[key]==key;
    }
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */

其實(shí)每個(gè)方法就是幾行代碼，非要說(shuō)缺點(diǎn)應(yīng)該就是每個(gè)set都要初始一個(gè)大容量的數(shù)組吧夯膀？我去看看排第一的代碼是怎么實(shí)現(xiàn)的诗充。
emmmmmmm....我們是一樣的思路，只不過(guò)我這是用數(shù)字代表有沒(méi)有诱建，人家是Boolean值代表的蝴蜓。我直接貼代碼：

class MyHashSet {
    boolean[] hash = new boolean[1000001];
    /** Initialize your data structure here. */
    public MyHashSet() {
    }
    public void add(int key) {
        hash[key] = true;
    }
    
    public void remove(int key) {
        hash[key] = false;;
    }
    
    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        return hash[key];
    }
}

思路一樣，大同小異而已~~~這道題就這么過(guò)俺猿！
雖然今天的目標(biāo)是五道題茎匠，但是講真這幾道都是送分題，時(shí)間還早押袍，再做一兩道诵冒。

設(shè)計(jì)哈希映射

題目：不使用任何內(nèi)建的哈希表庫(kù)設(shè)計(jì)一個(gè)哈希映射.具體地說(shuō)，你的設(shè)計(jì)應(yīng)該包含以下的功能

put(key, value)：向哈希映射中插入(鍵,值)的數(shù)值對(duì)谊惭。如果鍵對(duì)應(yīng)的值已經(jīng)存在汽馋，更新這個(gè)值。
get(key)：返回給定的鍵所對(duì)應(yīng)的值豹芯，如果映射中不包含這個(gè)鍵驱敲，返回-1。
remove(key)：如果映射中存在這個(gè)鍵癌佩，刪除這個(gè)數(shù)值對(duì)。

示例：
MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1); // 返回 1
hashMap.get(3); // 返回 -1 (未找到)
hashMap.put(2, 1); // 更新已有的值
hashMap.get(2); // 返回 1
hashMap.remove(2); // 刪除鍵為2的數(shù)據(jù)
hashMap.get(2); // 返回 -1 (未找到)
注意：
所有的值都在 [1, 1000000]的范圍內(nèi)便锨。
操作的總數(shù)目在[1, 10000]范圍內(nèi)。
不要使用內(nèi)建的哈希庫(kù)姚建。

思路：剛剛差點(diǎn)以為是進(jìn)錯(cuò)題了。仔細(xì)一看跟上面那道題不一樣吱殉。這道題是key-val對(duì)的存儲(chǔ)掸冤。但是我不慌啊友雳，思路可以直接復(fù)制，甚至我上一個(gè)用數(shù)字代表元素比人家用boolean代表元素的還要好用饺藤，而且我看題目這次的值在1-1000000之間，不就是為了避開(kāi)0省的挨個(gè)賦值嘛罗丰？嘿嘿，給我五分鐘去實(shí)現(xiàn)萌抵。
不是元镀，這個(gè)題玩賴鞍剂？住闯？澳淑？？量窘？都說(shuō)好了所有的值都在1-1000000之間氢拥，怎么還能put 0 呢蚌铜？過(guò)分了吧?太過(guò)分了！本來(lái)想直接返回的嫩海，看這樣還是處理一下吧叁怪。
好了，實(shí)現(xiàn)了：

class MyHashMap {
    private int[] num = new int[1000001];
    /** Initialize your data structure here. */
    public MyHashMap() {
        
    }
    
    /** value will always be non-negative. */
    public void put(int key, int value) {
        num[key] = key+value;
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        return num[key]==0?-1:num[key]-key;
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        num[key] = 0;
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */

還是老思路:數(shù)組下標(biāo)代表key涣觉，val本來(lái)想直接存的官册，但是因?yàn)榭梢詐ut 0 的騷操作难捌，所以我這里存key+val的和皂贩。這樣可以知道這個(gè)key到底有沒(méi)有明刷。至于獲取val用存的數(shù)字減去key就行了满粗。
性能不是很理想，我去看看被人怎么實(shí)現(xiàn)的挤聘。组去。
臥槽步淹，大佬用的鏈表實(shí)現(xiàn)的，键闺，厲害了澈驼，，挎塌，有點(diǎn)懵勃蜘，這么簡(jiǎn)單的題生生做的賊復(fù)雜假残。炉擅。谍失。算了算了，我還是不求甚解點(diǎn)吧快鱼。直接下一題吧纲岭。

轉(zhuǎn)換成小寫(xiě)字母

題目：實(shí)現(xiàn)函數(shù) ToLowerCase()线罕，該函數(shù)接收一個(gè)字符串參數(shù) str，并將該字符串中的大寫(xiě)字母轉(zhuǎn)換成小寫(xiě)字母喇闸，之后返回新的字符串燃乍。

示例 1：
輸入: "Hello"
輸出: "hello"
示例 2：
輸入: "here"
輸出: "here"
示例 3：
輸入: "LOVELY"
輸出: "lovely"

思路：這個(gè)題第一思路絕對(duì)是用char判斷宛琅，如果超過(guò)了a-z的數(shù)字范圍就處理成對(duì)應(yīng)小寫(xiě)的char.我還得去查查char對(duì)應(yīng)的數(shù)字是多少

image.png

class Solution {
    public String toLowerCase(String str) {
        char[] res = str.toCharArray();
        for(int i=0;i<res.length;i++){
            if(res[i]>='A'&& res[i]<='Z') res[i] = (char) (res[i]+32);
        }
        return new String(res);
    }
}

嗯嗯，這道題教會(huì)我代碼要嚴(yán)謹(jǐn)（個(gè)鬼？舔恰）桑嘶。逃顶。有進(jìn)步有進(jìn)步。繼續(xù)下一題霸褒。

1比特與2比特字符

題目：有兩種特殊字符盈蛮。第一種字符可以用一比特0來(lái)表示抖誉。第二種字符可以用兩比特(10 或 11)來(lái)表示。現(xiàn)給一個(gè)由若干比特組成的字符串旁理。問(wèn)最后一個(gè)字符是否必定為一個(gè)一比特字符我磁。給定的字符串總是由0結(jié)束夺艰。

示例 1:
輸入:
bits = [1, 0, 0]
輸出: True
解釋:
唯一的編碼方式是一個(gè)兩比特字符和一個(gè)一比特字符。所以最后一個(gè)字符是一比特字符。
示例 2:
輸入:
bits = [1, 1, 1, 0]
輸出: False
解釋:
唯一的編碼方式是兩比特字符和兩比特字符霞势。所以最后一個(gè)字符不是一比特字符。
注意:
1 <= len(bits) <= 1000.
bits[i] 總是0 或 1.

思路:哎草雕，這就不太好了啊固以，越是尋思做幾道就去玩游戲越是遇到簡(jiǎn)單的題幾分鐘刷一道憨琳。沉迷刷題不可自拔~~~~這道題感覺(jué)只需要判斷最后0前面是什么，如果是0則肯定是true菌湃。如果是1則判斷有幾個(gè)1.單數(shù)1說(shuō)明是false遍略，雙數(shù)1說(shuō)明是true绪杏。我去試試。感覺(jué)應(yīng)該就這么簡(jiǎn)單势似。
直接貼代碼：

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int count = 0;
        for(int i=bits.length-2;i>=0;i--){
            if(bits[i]==1){
                count++;
            }else{
                break;
            }
        }
        return count%2==0;
    }
}

比較簡(jiǎn)單叫编，只要明白怎么計(jì)算就行了霹抛。下一題杯拐。

字典中最長(zhǎng)的單詞

題目：給出一個(gè)字符串?dāng)?shù)組words組成的一本英語(yǔ)詞典。從中找出最長(zhǎng)的一個(gè)單詞朗兵，該單詞是由words詞典中其他單詞逐步添加一個(gè)字母組成顶滩。若其中有多個(gè)可行的答案礁鲁，則返回答案中字典序最小的單詞赁豆。若無(wú)答案魔种，則返回空字符串粉洼。

示例 1:
輸入:
words = ["w","wo","wor","worl", "world"]
輸出: "world"
解釋:
單詞"world"可由"w", "wo", "wor", 和 "worl"添加一個(gè)字母組成属韧。
示例 2:
輸入:
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
輸出: "apple"
解釋:
"apply"和"apple"都能由詞典中的單詞組成。但是"apple"得字典序小于"apply"去扣。
注意:
所有輸入的字符串都只包含小寫(xiě)字母樊破。
words數(shù)組長(zhǎng)度范圍為[1,1000]哲戚。
words[i]的長(zhǎng)度范圍為[1,30]。

思路：很好朋其，又遇到題目比較復(fù)雜的題了梅猿。理解了半天秒裕，才看明白示例而的banana就是搗亂的几蜻，因?yàn)闆](méi)有從第一個(gè)單詞開(kāi)始逐步添加一個(gè)字母組成。所以不用考慮颖低。然后可能有多個(gè)可行的方案弧烤，所以從最長(zhǎng)的開(kāi)始挨個(gè)判斷一時(shí)間也沒(méi)想出好的辦法。粱栖。首先分析這個(gè)若無(wú)答案返回空串脏毯。因?yàn)檫@個(gè)單詞到底是不是真的也不用考慮食店，所以哪怕有一個(gè)單詞也算是答案啊赏寇，除非數(shù)組是空的嗅定，但是他都說(shuō)了數(shù)組長(zhǎng)度范圍1-1000。奇了怪了,真的會(huì)有返回空的時(shí)候忙迁？哈哈碎乃，好了梅誓，先不吐槽了，繼續(xù)做題嵌言。
做完了摧茴，思路清晰明了簡(jiǎn)單快捷拥坛，就是性能略微差點(diǎn)：

class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> set = new HashSet<>();
        String res = "";
        for (String s : words) {
            //一個(gè)字母是一個(gè)單詞猜惋，但是不見(jiàn)得是最長(zhǎng)單詞，不過(guò)可能是別的單詞的底子缓窜，所以存進(jìn)set
            //如果是兩個(gè)單詞一定要保證第一個(gè)單詞是有的禾锤，三個(gè)要保證前兩個(gè)單詞是有的
            if (s.length() == 1 || set.contains(s.substring(0, s.length() - 1))) {
                //這有個(gè)坑，本來(lái)我覺(jué)得后面的一定比前面的長(zhǎng)倡鲸，直接賦值res的
                //后來(lái)報(bào)錯(cuò)了峭状。因?yàn)橐矔?huì)等于逼争。而等于要取前面的值
                res = s.length() > res.length() ? s : res;
                //添加進(jìn)set
                set.add(s);
            }
        }
        return res;
    }
}

中間關(guān)于賦值的坑我特意寫(xiě)了注釋?zhuān)f(wàn)要注意誓焦。第一遍提交我是res=s杂伟，然后錯(cuò)了！剩下的優(yōu)化幽钢。傅是。其實(shí)我覺(jué)得我性能可能差在1.數(shù)組的排序喧笔。 2.一直用contains判斷。尼变。嫌术。但是怎么優(yōu)化沒(méi)思路牌借。我直接看排行第一的代碼吧：
我不知道是不是我又沒(méi)理解題意或者說(shuō)什么膨报，排行前幾的代碼适荣！都復(fù)雜的不行弛矛！創(chuàng)建內(nèi)部類(lèi)比然，外部類(lèi)强法，遞歸加遞歸拟烫，循環(huán)加循環(huán)的迄本。嘉赎。。
大佬們?yōu)榱诉@個(gè)題寫(xiě)了幾十上百行代碼拇囊，我有點(diǎn)心虛啊寥袭。关霸。队寇。是不是一個(gè)解題方式凹亚病？窒舟？
真的思路NB辜纲，完全是字典的模式，每一個(gè)單詞26種選擇见剩，然后到第二個(gè)字母又是26種情況苍苞。狼纬。以此類(lèi)推疗琉，我只能說(shuō)set的contains性能是真的差！４粘堋Ｏ愫啤臼勉！這種判斷都比不過(guò)宴霸。。速缆。我甚至隱隱有沖動(dòng)有數(shù)組型數(shù)組型數(shù)組型....數(shù)組來(lái)存儲(chǔ)了艺糜！哎破停，算了算了尉剩，大佬解法真的有點(diǎn)復(fù)雜理茎，我還是靜靜的當(dāng)一個(gè)用現(xiàn)成api的咸魚(yú)吧。蚯撩。烛占。這道題也就到這里忆家。
今天的筆記就記到這里，如果稍微幫到你了記得點(diǎn)個(gè)喜歡點(diǎn)個(gè)關(guān)注揭芍！也祝大家周末愉快称杨，工作順順利利！每天進(jìn)步一點(diǎn)點(diǎn)旦装，唯有努力不欺人~~摊滔！