美文网首页java学习之路算法提高之LeetCode刷题
刷leetCode算法题+解析(三十六)

刷leetCode算法题+解析(三十六)

作者: 唯有努力不欺人丶 | 来源:发表于2019-12-28 21:24 被阅读0次

    周末周末,今天的目标五道题就好~~~加油!

    数组的度

    题目:给定一个非空且只包含非负数的整数数组 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的咸鱼吧。。。这道题也就到这里。
    今天的笔记就记到这里,如果稍微帮到你了记得点个喜欢点个关注!也祝大家周末愉快,工作顺顺利利!每天进步一点点,唯有努力不欺人~~!

    相关文章

      网友评论

        本文标题:刷leetCode算法题+解析(三十六)

        本文链接:https://www.haomeiwen.com/subject/avpsoctx.html