Leetcode刷题Day2----数组

Leetcode刷题Day2----数组

1. 有序数组的平方（977）

• 题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
• 文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
• 视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep

最简单的办法，直接从两端比较，用if判断哪边的计算结果大，就给新数组放哪边的计算结果，并且移动该指针。以此反复。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] ints=new int[nums.length];
        int left=0;
        int right=nums.length-1;
        for(int i=ints.length-1;i>=0;i--){
            if(nums[left]*nums[left]>=nums[right]*nums[right]){
                ints[i]=nums[left]*nums[left];
                left++;
            }
            else {
                ints[i]=nums[right]*nums[right];
                right--;
            }    
        }
        return ints;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.长度最小的子数组（209）

• 题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
• 文章讲解：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html
• 视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE

for循环里的j控制的是终止位置，起始位置i是用指针的方式来控制：
For的作用是每次都加一个窗口（最右边的值），while的作用是在满足窗口里的值>= target的时候考虑是否需要减去最左边的一个窗口（最左边的值）。在while里需要逻辑判断：得到此时的窗口大小和以前的窗口大小的最小值！
技巧：要找最小值，就先给 result最大值：int result=Integer.MAX_VALUE;

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int i=0;
        int sum=0;
        int result=Integer.MAX_VALUE;
        for(int j=0;j<nums.length;j++){
            sum+=nums[j];
            while(sum>=target){
                int subLength=j-i+1;
                result=Math.min(result,subLength);
                sum-=nums[i];
                i++;
            }
        }
        return result==Integer.MAX_VALUE?0:result;    
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

相关题目推荐：904.水果成篮(opens new window) & 76.最小覆盖子串(opens new window)

3. 螺旋矩阵II（59）

• 题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
• 文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
• 视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/

class Solution {
    public int[][] generateMatrix(int n) {
        int l = 0, r = n - 1, t = 0, b = n - 1;
        int[][] ints = new int[n][n];
        int num = 1, cal = n * n;
        while(num <= cal){
            for(int i = l; i <= r; i++) ints[t][i] = num++; 
            t++;
            for(int i = t; i <= b; i++) ints[i][r] = num++; 
            r--;
            for(int i = r; i >= l; i--) ints[b][i] = num++; 
            b--;
            for(int i = b; i >= t; i--) ints[i][l] = num++; 
            l++;
        }
        return ints;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

类似题目：54.螺旋矩阵 & 剑指Offer 29.顺时针打印矩阵

4. 数组总结

1. 循环不变量：从头到尾的代码对数组规则的规定是一致的，常见的是左闭右闭和左闭右开（59. 螺旋矩阵II）
2. 双指针方法，两个指针分别具有不同的意义（代替两层for）
3. 滑动窗口方法 ，循环控制窗口的结束节点，另取一个指针做开始节点的控制