算法之路(二)

🖊作者 : D. Star.
📘专栏 : 算法小能手
😆今日分享 : 你知道北极熊的皮肤是什么颜色的吗？（文章结尾有答案哦！）

力扣的209题

做题链接209

✔解题思路

先用左右指针（left , right），从最左边开始找，右指针先动

1. 利用单调性：当你找到第一个 >=target 时，右指针就不用再向右边找了，因为我们要找的是最短的子数组，再向右的子数组肯定是比第一次找到的长。
2. 移动左指针，在原来的和的基础上，减去前一个左指针的值（left=target 的子数组长度，如果比之前的子数组长度短，就覆盖。
3. 细节问题：符合长度的子数组 len 初始值赋多少？由于不清楚输入数组的长度，并且万一没有符合条件的子数组，返回的值就会出错。所以建议赋值整型的最大值 Integer.MAX_VALUES。

✔代码:

    public static int minSubArrayLen2(int target, int[] nums) {
        int n = nums.length,sum = 0,len = Integer.MAX_VALUE;
        for(int left = 0,right = 0;right<n;right++){
            sum+=nums[right];
            while (sum>=target){
                len = Math.min(len,right-left+1);
                sum-=nums[left++];
            }
        }
        return len == Integer.MAX_VALUE?0:len;
    }
1
2
3
4
5
6
7
8
9
10
11

✔总结:

1. 没注意到或者说是没有理解题目中的连续子数组 这个字眼,上来就sort()了
2. 我的做法是找到最大的数字，然后在他的左边和右边开始找长度最小的子数组，但是后来发现行不通。
3. 正确做法：用滑动窗口，“同向双指针”。

力扣的3题

做题链接：力扣3题

✔解题思路：

将字符串转化为字符数组。用数组代换Hash表。int[] hash = new int[128];//这里的128刚好囊括了所有阿斯克码值(0-127)。
先入窗口，然后判断，若符合判断，则出窗口，不符合则得出结果，最后循环更新结果。

✔代码：

    public static int lengthOfLongestSubstring2(String ss) {
        char[] s = ss.toCharArray();
        //用数组代换Hash表
        int[] hash = new int[128];//这里的128刚好囊括了所有阿斯克码值(0-127)
        int right = 0, left = 0, ret = 0;
        while (right < s.length) {
            hash[s[right]]++;//让s[right]所在的阿斯克码值+1----入窗口
            while (hash[s[right]] > 1) {//说明该字母已存在
                hash[s[left++]]--;//让s[left++]所在的阿斯克码值-1----窗口
            }
            ret = Math.max(ret,right-left+1);
            right++;
        }
        return ret;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

✔总结：

这题用到了Hash表的思想,用数组代替阿斯克码值,很巧妙。

力扣的1004题

做题链接：力扣1004题

✔解题思路：

1. right先进窗口，如果是1，跳过；如果是0，k–。
2. 判断k的值，如果k值<0，则遇0无法再翻牌子
3. 则出窗口，left++；遇到1，无视；遇到0，k++；
4. 得出结果，更新结果

✔代码：

       public static int longestOnes2(int[] nums, int k) {
        int n = nums.length, kk = k, left = 0, right = 0, len = 0;
        while (right < n) {
            //先进窗口
            if (nums[right] == 0) {
                kk--;
                right++;
            }
            else right++;
            //判断kk的值
            while (kk < 0) {
                if (nums[left++] == 0) kk++;
            }
            //计算长度
            len = Math.max(len, right - left);
        }
        return len;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

✔总结：

这题写的时候有点迷糊，没想到这种方法，老师刚讲的时候，还感觉挺懵的，但是细想也挺简单的，就像是求俩数之和一样，要使得k>=0才行。这题还是需要多复盘一下的！！！

力扣的1658题

做题链接力扣1658

✔做题思路：

重要思路：正难则反

1. 计算出整个数组sum 的值和target （代表窗口里的和sum-x）的值
2. 进窗口【并计算出窗口内tmp的值】
3. 判断tmp 和target 的关系【>则left++；<则right++；=则计算len】
4. 出窗口：就是上面的【>则left++】
5. 更新结果：就是上面的【=则计算len】

✔代码：

   public static int minOperations(int[] nums, int x) {
        //1. 计算出整个数组sum的值和target（代表窗口里面的和sum-x）的值
        int sum = 0;
        for (int i : nums) sum += i;
        int target = sum - x;
        //细节：
        //如果target<0（即x>sum），则直接返回-1
        if(target<0) return -1;
        //2. 进窗口
        int left = 0, right = 0, tmp = 0, len = -1;
        //这里长度len设为-1，有两个好处：
        // 1. 题目要求没有符合条件的就返回-1。
        // 2.最后可以判断，如果len是-1，则直接返回-1，否则返回num.length。
        while (right < nums.length) {
            tmp += nums[right];
            //3. 判断窗口里面的值
            while (tmp > target) {
                //大于target，[left++]
                //4. 出窗口
                tmp -= nums[left++];
            }
            if (tmp == target) {
                // 等于target，计算窗口长度
                //5. 更新长度
                len = Math.max(len, right - left+1);
            }
            // 小于target，right++
            //6. 进窗口
            right++;
        }
        if(len == -1) return len;
        return nums.length-len;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

✔总结：

这题刚开始的时候，理解错题目意思了，我上来就给数组排序，然后总有一些例子过不去，后来知道了题目的意思，是在原来的顺序上进行移动，但是无从下手。看了老师的解题步骤和思路，觉得很精妙！

答案：北极熊的皮肤是黑色的！我也是今天才知道…涨知识了~

---

感谢家人的阅读,不准确的地方 欢迎在评论区指正!