LeetCode Day02 977&209&59

标签：977 遍历 nums int Day02 ++ 209 res 赋值

第一题是[977. 有序数组的平方]这题解题思路依旧可以用双指针，指针分别指向数组的头尾两端，然后对两端求乘积比较大小，把乘积值更大的存储到数组尾端，然后指针更新位置，代码如下。

public int[] sortedSquares(int[] nums) {
        //res用于存储平方和结果
        int[] res = new int[nums.length];
        //l指向nums最左端，r指向nums最右端
        int l = 0, r = nums.length - 1;
        //index指向res数组的尾端
        int index = nums.length - 1;
        for(int i = 0; i < nums.length; i ++){

            //如果最左端的平方和>=最右端所指数平方和，说明这个值就是有序数组中的最大值了，存到res的尾部
            //同时更新res数组的指针位置，最左端的第一个数比较完毕以后也需要向前挪一位
              if(nums[l] * nums[l] >= nums[r] * nums[r]){
                res[index --] = nums[l] * nums[l];
                l ++;
            } else{
                res[index --] = nums[r] * nums[r];
                r --;
            }
        }
        return res;
    }

  第二题是[209. 长度最小的子数组]leetcode.cn/problems/mi…这题主要运用滑动窗口的思想去解题。指针一路往右边遍历滑动的过程中，我们一边用sum求和把这个区间内的和加起来，一旦sum值>target目标值，说明我们已经有这个子数组了，但多出来的值我们需要把它从sum中减回去（此时就需要更新滑动窗口的左端）。 放上代码。

public int minSubArrayLen(int target, int[] nums) {
        int res = 1000000010;
        int sum = 0;
        int l = 0;
        int r = 0;
        for(; r < nums.length; r ++){
            sum += nums[r];
            while(sum >= target){
                res = Math.min(res, r-l+1);
                sum -= nums[l];
                l ++;
            }
        }

        return res == 1000000010 ? 0 : res;
    }

 

[59. 螺旋矩阵 II] leetcode.cn/problems/sp… 这题对我来说难了，一开始毫无思路，只会暴力，但是显而易见n只要一变大暴力做法是绝对不可解的。后来看了答案思路再写，边界问题没处理好频频出错，debug了好久终于过了。

首先我们的赋值方向是：从左往右、从上至下、从右往左、最后从下到上。依照这个顺序我们刚好走完这个螺旋矩阵的最外层圈。

难点一：我们需要走几次完整的圈才能把这个矩阵赋值完毕？（也就是跳出循环的条件是？）

如果把最外层格子都走完算作一圈的话，那么每n阶的螺旋矩阵应该要走n/2次才能赋值完。比如n=4，那么我们就需要走2次就可以遍历完整个矩阵，如果n是奇数呢？我们会发现当n=3、5、7……时，走完外面的圈，正方形中心位置那个数是没法遍历到的，这时候我们就需要另外做个奇数判断了。

难点二：边界问题的处理

我们使用左闭右开的处理思路，我们需要注意，每一行每一列的最后位那个数我们都是先不处理的。比如n=4的时候，第一行应该是[1,2,3,4]，那么我们遍历的时候只遍历数组下标0-2(也就是说只赋值[1,2,3])，这样一来从左往右第一步就遍历完了，接下来是从上至下遍历[4,5,6,7],同样的这里我们只赋值[4,5,6]，数字7我们留到从右往左作为头节点开始遍历。因此可以推断出，n=4时遍历第一圈的中断条件我们只需要到3（给数组下标0、1、2赋值，到3结束），等我们遍历完第一圈以后会发现，第二圈的中断条件只需要到2，原因是外层圈已经被我们遍历过一遍了。由此可以推出我们的边界条件应该是n-当前遍历的圈数。

 public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int loop = 0;
        int count = 1;
        int start = 0; // 每次循环的开始点(start, start)
        int i, j;  //循环的坐标(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 ++;
        }

        //如果n是奇数，因为count每次赋值完以后都是+1了的，此时直接把矩形中心值直接赋值就行
        if(n % 2 != 0){
            res[start][start] = count;
        }

        return res;
    }

 

标签：977,遍历,nums,int,Day02,++,209,res,赋值
From： https://www.cnblogs.com/LinawZ/p/17759929.html