【算法刷题day2】Leetcode:977. 有序数组的平方、209. 长度最小的子数组、59. 螺旋矩阵 II

草稿图网站
java的Deque

Leetcode 977. 有序数组的平方

题目：977. 有序数组的平方

解题思路

双指针+绝对值对比

代码

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0, right = nums.length - 1;
        int[] res = new int[nums.length];
        for(int i = right; i >= 0; i--){
            if (Math.abs(nums[left]) > Math.abs(nums[right])){
                res[i] = nums[left] * nums[left];
                left++;
            }else{
                res[i] = nums[right] * nums[right];
                right--;
            }
        }
        return res;
    }
}

总结

暂无

Leetcode 209. 长度最小的子数组

题目：209. 长度最小的子数组
解析：代码随想录的解析

解题思路

滑动窗口，不够划到够。
记录。
一个一个划到不够。

代码

class Solution {
	public int minSubArrayLen(int target, int[] nums) {
		int slowIdx = 0, fastIdx = 0;
		int curSum = 0, res = Integer.MAX_VALUE;
		while (slowIdx < nums.length || curSum >= target){
			//fastIdx移动，直到curSum大于等于target，记录此时的right - left
			while (fastIdx < nums.length && curSum < target){
				curSum += nums[fastIdx++];
			}
			//记录长度
			if (curSum >= target){
				res = Math.min(res, fastIdx - slowIdx);
			}else{
				break;
			}

			//slowIdx移动，直到curSum小于target
			if (slowIdx < nums.length && curSum >= target){
				curSum -= nums[slowIdx++];
			}
		}
		return res == Integer.MAX_VALUE ? 0 : res;
	}
}

总结

代码冗余。
外循环为right走完，内循环left每走一步比一次。

class Solution {
	public int minSubArrayLen(int target, int[] nums) {
		int left = 0;
		int sum = 0, res = Integer.MAX_VALUE;
        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;
	}
}

Leetcode 59. 螺旋矩阵 II

题目：59. 螺旋矩阵 II
解析：代码随想录的解析

解题思路

四个循环，一层一层往里走

代码

class Solution {
	public int[][] generateMatrix(int n) {
		int[][] res = new int[n][n];
		int val = 1;
		for (int i = 0, j = 0, k = 0; k < n/2; k++){
			//(0,0->n-2),(1,1-n-3)...
			for (j = k; j < n - k - 1; j++){
				res[i][j] = val++;
			}
			//i不变，j变为n-k-1

			//(0->n-2,n-1),(1->n-3,n-2)...
			for(i = k; i < n - k - 1; i++){
				res[i][j] = val++;
			}
			//j不变，i变为n-k-1

			//(n-1,n-1->1),(n-2,n-2->2)...
			for(; j > k; j--){
				res[i][j] = val++;
			}
			//i不变，j变为k

			//(n-1->1,0),(n-2->2,1)...
			for(; i > k; i--){
				res[i][j] = val++;
			}
			//j不变，i变为k
			i += 1;//新的一圈在之前的里面一层，所以i要加1
		}
		if (n % 2 != 0)
			res[n/2][n/2] = n*n;
		return res;
	}
}

总结

靠调试看出来i+=1，不然没反应过来