代码随想录算法训练营第二天 | LeetCode 977(有序数组的平方) LeetCode 209(长度最小的子数组) LeetCode 59(螺旋矩阵II)

977：有序数组的平方

方法一：暴力方法
直接原地平方后，直接调用数组排序
方法二：双指针前后遍历，构造结果数组，保证有序

方法一

class Solution {
    public int[] sortedSquares(int[] nums) {
        for(int i  = 0; i < nums.length; i++) {
            nums[i]  = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

方法二

class Solution {
    public int[] sortedSquares(int[] nums) {
        //定义左右指针 左闭右闭
        int left = 0;
        int right = nums.length - 1;
        //构造结果数组
        int[] res = new int[nums.length];
        int index = nums.length - 1;
        while(left <= right){
            int left2 =  nums[left] * nums[left];
            int right2 = nums[right] * nums[right];
            //根据左右指针索引目标值大小 插入结果数组
            if(left2 < right2){
                res[index--] = right2;
                right--;
            }else if(left2 >= right2){
                res[index--] = left2;
                left++;
            }
        }
        return res;
    }
}

209：长度最小的子数组

LeetCode 209(长度最小的子数组)
思路：

滑动窗口
如何实现滑动窗口：
1.窗口内是什么
2.如何移动窗口的起始位置
3.如何移动窗口的结束位置

方法一

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 滑动窗口数值之和
        int sum = 0;
        int result = Integer.MAX_VALUE;
        int length = 0;
        // 滑动窗口起始位置和终点位置
        int pre = 0,behind = 0;
        while(pre < nums.length){
            sum += nums[pre];
            //根据子序列是否符合条件来 不断更新起始位置
            while(sum >= target){
                //计算子序列长度
                length = pre - behind + 1;
                result = Math.min(result, length);
                //更新起始位置
                sum -= nums[behind++];
            }
            pre++;
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

59：螺旋矩阵II

LeetCode 59(螺旋矩阵II)
思路:

坚持循环不变量原则
模拟其螺旋规则
1.填充上行从左到右
2.填充右列从上到下
3.填充下行从右到左
4.填充左列从下到上
所以需要考虑怎么循环循环起点和终点

方法一

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int loopCount = 0;
        int count = 1;
        int startPoint = 0;
        int i,j;
        //均遵循左闭右开
        while(loopCount < (n >> 1)) {
            loopCount++;
            //上侧 从左到右
            for(j = startPoint; j < n - loopCount; j++) {
                result[startPoint][j] = count++;
            }
            //右侧 从上到下
            for(i = startPoint; i < n - loopCount; i++) {
                result[i][j] = count++;
            }
            //下侧 从右到左
            for(; j >= loopCount; j--) {
                result[i][j] = count++;
            }
            //左侧 从下到上
            for(;i >= loopCount; i--){
                result[i][j] = count++;
            }
            startPoint++;
        }
        //n为奇数时需要单独给矩阵中心赋值
        if(n % 2 == 1){
            result[startPoint][startPoint] = count;
        }
        return result;
    }
}