代码随想录算法训练营day2_代码随想录算法训练营 day2

代码随想录算法训练营day1| 977.有序数组的平方 、209.长度最小的子数组、59.螺旋矩阵II

977.有序数组的平方
思路:本题使用双指针，对于数组而言是有序的，但是平方过后是不一定是有序的，我们新建一个跟数组长度一样的新数组res保存结果，对于正数而言，排序的数组平方后仍是有序，所以我们需要比较最左边的元素的平方和最右边的元素的平方，将平方大的放在res数组中的最后一个位置，然后将其对应的下标移动一位，当left和right重合在一起的时候，nuns数组遍历完毕

Code

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

209.长度最小的子数组
思路:本题使用滑动窗口解决，滑动窗口的本质就是双指针，对于数组而言，从左到右遍历求和sum，当sum >= target时记录下此时的子数组长度，此时右指针固定，当我们减去左指针的值，如果仍然满足sum >= target更新子数组的长度，left继续移动，直到条件不满足，当数组遍历完毕，找到长度最小的子数组。

Code

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

59.螺旋矩阵II

Code

class Solution {
    public int[][] generateMatrix(int n) {
        int loop = 0;
        int[][] res = new int[n][n];
        int start = 0; //每次循环的开始点
        int count = 1; //填充数字
        int i,j;

        while (loop++ < n / 2) {
            //上侧从左到右
            for (j = start; j < n - loop; j++) {
                res[start][j] = count++;
            }
            //右侧从上到下
            for (i = start; i < n - loop; i++) {
                res[i][j] = count++;
            }

            //下侧从右到左
            for (;j >= loop; j--) {
                res[i][j] = count++;
            }

            //左侧从上到下
            for (;i >= loop; i--) {
                res[i][j] = count++;
            }

            start++;

        }

        if (n % 2 == 1) {
            res[start][start] = count;
        }

        return res;
    }
}
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
34
35
36
37
38
39