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

题目链接: 977.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

看到题目的第一想法：

第一次错误想法：看到题后，题目中的例子是有正有负的，那么最小值就是在中间，但这种想法是错误的，因为题目说的是非递减顺序的排序整数，可能全为负数，或者全为正数，这样的话，平方后的最小值就不是在中间了，那就是在两侧了。
但就是因为有这种错误想法，让我想到了正确的思路。
之后AC的想法：这道题要用双指针没有错，该数组左右两侧平方后有一个是整个数组的最大值。
思路：设置left指针指向数组开头即left=0，设置right指针指向数组尾部，即left=nums.length；然后比较两指针的平方后的大小，将较大的值存放入结果数组result的末尾。（如果left指向的数组的平方大，将该数存放入result末尾，然后指向result末尾的指针减去一，left指针向右移动增加一，若right同理）

package com.second.day2;public class SortedSquares_977 {public int[] sortedSquares(int[] nums) {int right = nums.length - 1;int left = 0;int[] result = new int[nums.length];int index = nums.length - 1;while(left <= right) {int r_value = nums[right] * nums[right];int l_value = nums[left] * nums[left];if(r_value <= l_value) {result[index--] = l_value;left++;}else {result[index--] = r_value;right--;}}return result;}
}

看完代码随想录之后的想法：

与代码随想录的想法一直，但我说表达的还不够明白，写博客还是有必要的，说出自己的想法，慢慢提高自己的表达能力。

自己实现过程中遇到哪些困难：

刚开始思路错误，然后第一次只通过了既有正数又有负数的用例，思路正确后就写出来了。

题目链接: 209. 长度最小的子数组

看到题目的第一想法：

用滑动窗口，利用左右指针限制住滑动窗口的大小。左右指针刚开始指向nums[0],如果左右指针区间内的数的和没大于等于target就需要移动右节点，继续扩展窗口大小，如果左右指针区间内的数的和大于等于target了就需要移动左节点，尽可能的缩小窗口的大小。期间记下窗口最小的窗口大小，只到遍历完整个数组。

package com.second.day2;public class MinSubArrayLen_209 {public int minSubArrayLen(int target, int[] nums) {int left = 0;  //left为窗口的左指针int sum = 0;   //sum为窗口区间内的和int result = Integer.MAX_VALUE;   //存储最小窗口大小for(int i = 0; i < nums.length; i++) {//这里的i就是窗口的右指针sum += nums[i];if(sum < target) {continue;}else {//当窗口区间内的和大于target，需要尽可能的缩小窗口while(sum >= target) {sum -= nums[left];left++;}//上述代码后sum已经小于target了，不符合sum要大于target，窗口左指针需要向左移位，确保sum>=targetsum += nums[--left];//更新targetif(result > (i - left + 1)) {result = i - left + 1;}}}//result没更新过，说明不存在符合条件的子数组，返回0return result != Integer.MAX_VALUE ? result : 0;}
}

看完代码随想录之后的想法：

和卡哥的思路差不多，卡哥实现的代码比我精简，

自己实现过程中遇到哪些困难：

本题我没出现什么困难，困难就是一定要坚持，克服懒惰心理。

题目链接: 59. 螺旋矩阵 II

看到题目的第一想法：

第一想法是，我做过，我做过不知一遍，第一次做的时候还是刚接触编程，用c写，只能说自己太菜了。
这道题就是遍历顺序，控制好边界，n*n的数组能遍历n/2的轮次，为什么这么说呢？假设n为3，它能遍历的轮次就是3/2为1，刚开始向右写1，2再向下写3，4再向左写5，6再向上写7，8.能够完整的走完右，下，左，上就为一轮次。然后最中间的值单独处理写入9.就这样一遍遍遍历即可。

package com.second.day2;public class GenerateMatrix_59 {public int[][] generateMatrix(int n) {int left = 0;      //目前整个还未遍历到的左边框int right = n - 1; //目前整个还未遍历到的右边框int up = 0;        //目前整个还未遍历到的上边框int down = n - 1;  //目前整个还未遍历到的下边框int[][] ans = new int[n][n];int count = 0;     //一次写入的数int round = 0;     //轮次while(round != n / 2) {//往右for(int i = left; i < right; i++) {count += 1;ans[up][i] = count;}//往下for(int i = up; i < down; i++) {count += 1;ans[i][right] = count;}//往左for(int i = right; i > left; i--) {count += 1;ans[down][i] = count;}//往上for(int i = down; i > up; i--) {count += 1;ans[i][left] = count;}//一轮次过后，数组缩小一圈,轮次加一left++;right--;up++;down--;round++;}//奇数数组单独处理if(n % 2 != 0) {count += 1;ans[n / 2][n / 2] = count;}return ans;}public static void main(String[] args) {GenerateMatrix_59 demo = new GenerateMatrix_59();for (int[] matrix : demo.generateMatrix(6)) {for (int i : matrix) {System.out.print(i + " ");}System.out.println();}}
}

看完代码随想录之后的想法：

思路一样的，代码不一样。

自己实现过程中遇到哪些困难：

也没遇到太大的问题，勤能补拙。

今日收获，记录一下自己的学习时长：

今天写了四个题：
45. 跳跃游戏 II，977.有序数组的平方 ， 209.长度最小的子数组
，59. 螺旋矩阵 II
代码：1.5h
博客：1h
45. 跳跃游戏 II并不是此次训练营的内容，是我自己多加的，以后到贪心算法的时候也许会遇到吧。