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; } }
双指针
第一步：创建新数组
第二步：创建新数组的指针（放在最后一位，用于放值）
第三步：创建老数组的指针（前后各一个）
第四步：平方后比较，大的搬家，小的待命
第五步：返回
注意点：
1、循环的条件要有等于情况，要不然比较完还会剩一个
2、判断的时候记得考虑等于的情况
class Solution { public int[] sortedSquares(int[] nums) { // 创建一个新数组 int[] newNums = new int[nums.length]; // 创建前后两个指针 int left = 0; int right = nums.length - 1; // 创建新数组的指针，指向最后的下标 int key = newNums.length - 1; while (left <= right) { if (nums[left] * nums[left] < nums[right] * nums[right]) { // 大的被选中 newNums[key] = nums[right] * nums[right]; // 被选中的移坐标 right--; // 新数组移下标 key--; } else if (nums[left] * nums[left] >= nums[right] * nums[right]) { // 大的被选中 newNums[key] = nums[left] * nums[left]; // 被选中的移坐标 left++; // 新数组移下标 key--; } } return newNums; } }
209.长度最小的子数组
题目链接：力扣
思路
暴力解法：首先我们会想到的就是以两层循环进行遍历，取到合适的数组
滑动窗口：想象一下推拉窗户，只不过这个滑动窗口的移动靠指针，大小靠里面的数值和，检索开始，右边的指针进行收割，把后面的数收割到窗口中，满足条件就进行判断，判断完成后就利用左边的指针推动窗口（注意判断是用while还是用if）
长度最小的子数组
暴力解法
第一步：外层循环开始，从第一个值进行判断
第二步：内层循环从外层循环下标开始的位置往后进行收割
第三步：满足条件的获得长度，跳出循环
第四步：外层循环再进一步，从第二个开始
第五步：以此循环，最终求到最小值
class Solution { public int minSubArrayLen(int target, int[] nums) { // 设置取数的值 int result = Integer.MAX_VALUE; // 设置子数组的值 int sum; for (int i = 0; i < nums.length ; i++) { sum = 0; for (int j = i ; j < nums.length ; j++) { sum += nums[j]; if (sum >= target) { int len = j - i + 1; result = len < result ? len : result; break; } } } return result == Integer.MAX_VALUE ? 0 : result; } }
滑动窗口
第一步：准备两个指针（代表的是窗口左右的两个指针，左指针控制窗口的整体移动，右指针在前面奋勇收割）
第二步：判断子数组的值的和，如果满足条件就取长度，与已有的长的进行比较
第三步：左指针控制窗口向前移动
第四步：返回之后的结果
注意点：判断和的时候是使用if还是while？
if只能减去前面一个多的元素，不能判断窗口前是不是右多个元素不满足条件，比如现在有个目标值是7，数组窗口内的数字有 1 ，1，1，1，50，那么当窗口时54的时候满足条件，但是if判断只能减去第一个1，后面的3个都减不掉，最小的满足长度的数组没有获取到
Tip：感觉双指针两层循环的一种更高效的替代
class Solution { public int minSubArrayLen(int target, int[] nums) { // 设置一个比较值，与获取到的子数组长度进行比较 int result = Integer.MAX_VALUE; // 设置两个指针来圈子数组 int left = 0; int sum = 0; for (int right = 0 ; right < nums.length ; right++) { sum += nums[right]; while (sum >= target) { // 记录满足条件的子数组的长度 int len = right - left + 1; // 将获取到的长度进行比较存储 result = result > len ? len : result; // 移动窗口，将左指针向前进一位,同时left指针指向的数字也要从这个窗口中减去 sum -= nums[left++]; } } return result == Integer.MAX_VALUE ? 0 : result; } }
59.螺旋矩阵II
题目链接：力扣
思路：
这个题目不涉及什么算法，要求的是对代码的掌握程度，最忌的就是转多了，或者转少了，这样就乱了，所以一定要遵循循环不变量的原则进行遍历，确保每一个都能填上
1、怎么转，转几圈，转圈的条件怎么判断
2、转的时候，边界条件怎么设置（循环不变量）坚持一个原则处理每一条边，因为是个循环，所以使用左闭右开的原则来处理每一条边
3、n为奇数的情况怎么处理
螺旋矩阵II
模拟循环
while 循环是转了几圈 转了n/2圈 循环中的判断条件 从第0圈开始
这里面的offset和loop可以合成一个变量loop
startX和startY可以合成一个变量start
class Solution { public int[][] generateMatrix(int n) { // 创建二维数组 int[][] nums = new int[n][n]; // 二维数组的起始位置 // int[i][j] // int[startX][startY] int startX = 0; int startY = 0; // 每次循环控制边界（左闭右开） int offset = 1; // 放进数组的数 int count = 1; // 因为有四个循环，将i和j设置为全局变量 int i,j; // 要转的圈数 int loop = 0; while (loop++ < n/2) { // 从左到右 for (j = startY ; j < n - offset ; j++) { nums[startX][j] = count++; } // 从上到下 for (i = startX ; i < n - offset ; i++) { nums[i][j] = count++; } // 从右到左 for ( ; j > startY ; j--) { nums[i][j] = count++; } // 从下到上 for ( ; i > startX ; i--) { nums[i][j] = count++; } // 起始位置移动 startX++; startY++; // 控制边界量增加 offset++; } if (n % 2 == 1) { nums[startX][startY] = count; } return nums; } }
