刷leetCode算法题+解析（三十六）

周末周末，今天的目标五道题就好~~~加油！

数组的度

题目：给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1:
输入: [1, 2, 2, 3, 1]
输出: 2
解释:
输入数组的度是2，因为元素1和2的出现频数最大，均为2.
连续子数组里面拥有相同度的有如下所示:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2]的长度为2，所以返回2.
示例 2:
输入: [1,2,2,3,1,4,2]
输出: 6
注意:
nums.length 在1到50,000区间范围内。
nums[i] 是一个在0到49,999范围内的整数。

思路：讲真，我现在觉得难的不是题目本身或者思路，而且阅读理解的水平。读了两遍题目大概觉得所谓的数组的度：就是数组中最多元素的个数。这道题我理解的就是找到数组中包含最多元素个数的子串。比如 1 1 1 1 2 3 4 5 这个子串就是前面四个1.再比如1 01 2 1 3 1 4 1这个子串就是全串。我不知道我说明白没有，反正我自己明白了。我去尝试写代码了。
说一下思路：最笨的就是先获取出现次数最多的元素值。然后判断第一次出现和最后一次出现的位置，然后截取字串。但是我目前的想要是要借助map来判断。尝试去写了。
写完回来了，首先这道题我的思路没问题，但是真写出来有点麻烦。其次性能超过百分之八十多，没达到我心里预期。但是我已经想好改进的办法了，一会儿去试试，先把第一版本的代码贴上来：

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);
            }
        }
        //数组中没有重复元素，每一个子串都是度
        if(index==0) return 1;
        int res = 50001;
        for(int x = 0;x<index;x++){
            List<Integer> list = map.get(val[x]);
            //最后一次出现的下标减去第一次出现的下标+1就是字串的长度
            int temp = list.get(list.size()-1)-list.get(0)+1;
            res = res<temp?res:temp;
        }
        return res;
    }
}

写的比较墨迹，我改进一下的。改进完了性能和消耗都更好了我能说什么？我也很绝望啊！！！
看了第一的代码，不能不说这些数据结构中，数组是最简单方便快捷的处理方式了，性能不行用数组快成为真理了。这个性能第一的代码用的数组处理。我这里map的key是数字本身，value是list，用list的长度判断次数，用list中的int记录下标。而人家是用了三个数组，下标代表元素来处理的！
说不会有点过了，但是处理起来比较绕。而且没有我上面的直观，可是性能真的是好太多！我执行下来31ms，人家用2ms。也不是很难，只不过一来是我没想到那么做而已。接下来附上代码：

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]]++;
            //这里如果这个元素第一次出现则在first数组中存储，是第一次出现的下标
            if (temp[nums[i]] == 1) {
                first[nums[i]] = i;
            }
            //肯定是越往后数字越大， 所以这个last中不断替换，存储的就是最后一次出现的下标
            last[nums[i]] = i;
            //这个遍历是记录出现次数最多的次数个数
            maxTime = Math.max(maxTime, temp[nums[i]]);
        }
        int result = nums.length;
        for (int i = 0; i < max + 1; i++) {
            //只有本身是次数最多的元素才有必要判断，
            if (temp[i] == maxTime) {
                result = Math.min(result, last[i] - first[i] + 1);
            }
        }
        return result;
    }
}

好了，我自己理了一遍思路，想法都写在注释上了，这道题其实不难，感觉考点是性能，下一题吧。

二叉搜索树中的搜索

题目：给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

题目截图

思路：这道理怎么说呢，感觉简单的离谱啊？？是我想简单了么？因为是二叉搜索树，所以遵循左小右大的原则，我现在的理解就是根据条件遍历。。我去试试有没有坑吧。
试完了，完全没坑，三分钟搞定，性能超过百分百，确定他就是一道小白题！直接上代码:

/**
 * 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;
    }
}

哈哈，我都是顺序刷的简单的题目，知道我周末不太愿意刷题所以给我凑题数的么？希望接下来的几道题都这么简单~~~

数据流中的第K大元素

题目：设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第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
说明:
你可以假设 nums 的长度≥ k-1 且k ≥ 1。

思路：先说题目，看了两遍，认真看了给的demo，才算是明白了是什么意思。首先这个add不是一次性操作，而是add一次同一个对象的数组里就一直多这么一个元素了。其实这个题我感觉是实现简单，但是性能好的实现比较难，不然一个Arrays.sort就搞定了没什么意义了。我去尝试写代码了。
咳咳，反正第一版代码我用贼无脑的形式实现了，起码先实现再优化，哈哈

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);
 */

不出所料的性能，只超过百分之七的人。其实优化点很多，我这个版本也是为了测试我对题目的理解对不对。接下来我去真的实现了。
好了，进化版出来了，依然排名二三十而已，完全数组实现了，直接贴代码：

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);
 */

感觉唯一可能拖性能的也就是那个排序了，可是总不能我自己实现吧？真的是脑壳痛，我放弃优化了，直接看人家性能好的怎么写的吧。
看到了一个数据结构：PriorityQueue。
这个类厉害了，自带比较大小的队列。
PriorityQueue使用跟普通队列一样，唯一区别是PriorityQueue会根据排序规则决定谁在队头，谁在队尾。
有了这个属性就不用自己比较了，虽然还没看源码不知道人家怎么封装的，但是看别人代码用了这个类几乎就是一次搞定，我去写出来：

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) {
        //如果还没被填满就顺序往里填充元素
        //这种情况要么正在初始化，要么第一次调用add往里填充元素
        if(q.size() < k) {
            q.offer(val);   
        //如果已经满了，判断第一个元素和val大小，如果val较大才需要操作不谈直接返回第一个就行             
        }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类的知识，不过因为在家所以没看源码。先记下有空去看。觉得还是知道的少，早知道这个数据结构还用废那么久时间自己实现么~~

二分查找

题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

思路：这个题怕不是出错地方了吧？要是刚刚接触算法可能还要想想，现在都用烂了好不好~~我去直接实现了。

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;   
    }
}

就这样了，反正也没啥亮点，唯一算是坑的就是可能只有一个元素，所以left是可以等于right的。就是一个普通的二分法。

设计哈希集合

题目：不使用任何内建的哈希表库设计一个哈希集合。具体地说，你的设计应该包含以下的功能

add(value)：向哈希集合中插入一个值。
contains(value) ：返回哈希集合中是否存在这个值。
remove(value)：将给定值从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例:
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 (已经被删除)
注意：
所有的值都在 [0, 1000000]的范围内。
操作的总数目在[1, 10000]范围内。
不要使用内建的哈希集合库。

思路:这道题怎么说呢，我只能说实现的方式很多，但是性能是主要考虑因素。不然暴力实现感觉就跟投机取巧了似的。其实我觉得就是实现一个Set。我先想想怎么提高效率。灵机一动，我决定用数组！！去写代码了！
我现在爱死了我自己的灵机一动。用数组实现了，数组下标代表数字，贴代码：

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);
 */

其实每个方法就是几行代码，非要说缺点应该就是每个set都要初始一个大容量的数组吧？我去看看排第一的代码是怎么实现的。
emmmmmmm....我们是一样的思路，只不过我这是用数字代表有没有，人家是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];
    }
}

思路一样，大同小异而已~~~这道题就这么过！
虽然今天的目标是五道题，但是讲真这几道都是送分题，时间还早，再做一两道。

设计哈希映射

题目：不使用任何内建的哈希表库设计一个哈希映射.具体地说，你的设计应该包含以下的功能

put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。
get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。
remove(key)：如果映射中存在这个键，删除这个数值对。

示例：
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的数据
hashMap.get(2); // 返回 -1 (未找到)
注意：
所有的值都在 [1, 1000000]的范围内。
操作的总数目在[1, 10000]范围内。
不要使用内建的哈希库。

思路：刚刚差点以为是进错题了。仔细一看跟上面那道题不一样。这道题是key-val对的存储。但是我不慌啊，思路可以直接复制，甚至我上一个用数字代表元素比人家用boolean代表元素的还要好用，而且我看题目这次的值在1-1000000之间，不就是为了避开0省的挨个赋值嘛？嘿嘿，给我五分钟去实现。
不是，这个题玩赖啊？？？？？都说好了所有的值都在1-1000000之间，怎么还能put 0 呢？过分了吧?太过分了！本来想直接返回的，看这样还是处理一下吧。
好了，实现了：

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);
 */

还是老思路:数组下标代表key，val本来想直接存的，但是因为可以put 0 的骚操作，所以我这里存key+val的和。这样可以知道这个key到底有没有。至于获取val用存的数字减去key就行了。
性能不是很理想，我去看看被人怎么实现的。。
卧槽，大佬用的链表实现的，，厉害了，，，有点懵，这么简单的题生生做的贼复杂。。。算了算了，我还是不求甚解点吧。直接下一题吧。

转换成小写字母

题目：实现函数 ToLowerCase()，该函数接收一个字符串参数 str，并将该字符串中的大写字母转换成小写字母，之后返回新的字符串。

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

思路：这个题第一思路绝对是用char判断，如果超过了a-z的数字范围就处理成对应小写的char.我还得去查查char对应的数字是多少

image.png
大写变小写+32。我去实现啦：
!!!这个题有毒吧，既然字符串中可能有不是字母的元素为啥示例不弄一个出来？？？示例都是字母，结果提交了测试案例给我出特殊符号了？合适么?
行了，做出来了，直接性能超过百分百，一道送分题。一开始我以为不是大写就是小写，所以只判断小于'a'就行了，后来发现还有乱七八糟的符号，所以判断变成了大于'A'小于'Z'。

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);
    }
}

嗯嗯，这道题教会我代码要严谨（个鬼！）。。有进步有进步。继续下一题。

1比特与2比特字符

题目：有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。

示例 1:
输入:
bits = [1, 0, 0]
输出: True
解释:
唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。
示例 2:
输入:
bits = [1, 1, 1, 0]
输出: False
解释:
唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。
注意:
1 <= len(bits) <= 1000.
bits[i] 总是0 或 1.

思路:哎，这就不太好了啊，越是寻思做几道就去玩游戏越是遇到简单的题几分钟刷一道。沉迷刷题不可自拔~~~~这道题感觉只需要判断最后0前面是什么，如果是0则肯定是true。如果是1则判断有几个1.单数1说明是false，双数1说明是true。我去试试。感觉应该就这么简单。
直接贴代码：

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;
    }
}

比较简单，只要明白怎么计算就行了。下一题。

字典中最长的单词

题目：给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。

示例 1:
输入:
words = ["w","wo","wor","worl", "world"]
输出: "world"
解释:
单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。
示例 2:
输入:
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输出: "apple"
解释:
"apply"和"apple"都能由词典中的单词组成。但是"apple"得字典序小于"apply"。
注意:
所有输入的字符串都只包含小写字母。
words数组长度范围为[1,1000]。
words[i]的长度范围为[1,30]。

思路：很好，又遇到题目比较复杂的题了。理解了半天，才看明白示例而的banana就是捣乱的，因为没有从第一个单词开始逐步添加一个字母组成。所以不用考虑。然后可能有多个可行的方案，所以从最长的开始挨个判断一时间也没想出好的办法。。首先分析这个若无答案返回空串。因为这个单词到底是不是真的也不用考虑，所以哪怕有一个单词也算是答案啊，除非数组是空的，但是他都说了数组长度范围1-1000。奇了怪了,真的会有返回空的时候？哈哈，好了，先不吐槽了，继续做题。
做完了，思路清晰明了简单快捷，就是性能略微差点：

class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> set = new HashSet<>();
        String res = "";
        for (String s : words) {
            //一个字母是一个单词，但是不见得是最长单词，不过可能是别的单词的底子，所以存进set
            //如果是两个单词一定要保证第一个单词是有的，三个要保证前两个单词是有的
            if (s.length() == 1 || set.contains(s.substring(0, s.length() - 1))) {
                //这有个坑，本来我觉得后面的一定比前面的长，直接赋值res的
                //后来报错了。因为也会等于。而等于要取前面的值
                res = s.length() > res.length() ? s : res;
                //添加进set
                set.add(s);
            }
        }
        return res;
    }
}

中间关于赋值的坑我特意写了注释，千万要注意。第一遍提交我是res=s，然后错了！剩下的优化。。其实我觉得我性能可能差在1.数组的排序。 2.一直用contains判断。。。但是怎么优化没思路。我直接看排行第一的代码吧：
我不知道是不是我又没理解题意或者说什么，排行前几的代码！都复杂的不行！创建内部类，外部类，递归加递归，循环加循环的。。。
大佬们为了这个题写了几十上百行代码，我有点心虚啊。。。是不是一个解题方式啊？？
真的思路NB，完全是字典的模式，每一个单词26种选择，然后到第二个字母又是26种情况。。以此类推，我只能说set的contains性能是真的差！！！！这种判断都比不过。。。我甚至隐隐有冲动有数组型数组型数组型....数组来存储了！哎，算了算了，大佬解法真的有点复杂，我还是静静的当一个用现成api的咸鱼吧。。。这道题也就到这里。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注！也祝大家周末愉快，工作顺顺利利！每天进步一点点，唯有努力不欺人~~！