977.有序数组的平方
题目链接
https://leetcode.cn/problems/squares-of-a-sorted-array/description/
// 第一次答案
class Solution {
public int[] sortedSquares(int[] nums) {
int[] result = new int[nums.length];
int left = 0;
int right = nums.length - 1;
int index = nums.length - 1;
while(left <= right) {
int dbLeft = nums[left] * nums[left];
int dbRight = nums[right] * nums[right];
if (dbLeft < dbRight) {
result[index--] = dbRight;
right--;
} else if(dbLeft > dbRight) {
result[index--] = dbLeft;
left++;
} else {
if (left == right) {
result[index--] = dbLeft;
} else {
result[index--] = dbLeft;
result[index--] = dbLeft;
}
left++;
right--;
}
}
return result;
}
}
问题：
- 对比了答案发现了问题，我这个代码多写了好多逻辑，条件判断里的边界条件都列进去了，其实是包含关系。
（num[right] 平方 >= num[left]平方） - 逻辑有点混乱，新数组应该每次放进去一个值，这个逻辑不应发生变化，不管是不是有重复的值，每次移动一个位置，下次比较完可以再放进去。
- 主要应该处理负数平方后位置发生的变化。
改进之后的答案：
// 第二次修改了边界条件之后的答案
class Solution {
public int[] sortedSquares(int[] nums) {
int[] result = new int[nums.length];
int left = 0;
int right = nums.length - 1;
int index = nums.length - 1;
while(left <= right) {
int dbLeft = nums[left] * nums[left];
int dbRight = nums[right] * nums[right];
if(dbLeft > dbRight) {
result[index--] = dbLeft;
left++;
} else {
result[index--] = dbRight;
right--;
}
}
return result;
}
}
题后感：题目其实很简单，但是边界想不清楚会多加挺多冗余逻辑
209.长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/description/
这道题……嗯……只想到暴力解法，完全没思路，直接上看完题解之后的答案吧
方法关键词：滑动窗口，也叫双指针法
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int result = Integer.MAX_VALUE;
int left = 0;
int right = 0;
int sum = 0;
for(right = 0;right < nums.length; right++) {
sum += nums[right];
while(sum >= target) {
int curlen = right - left + 1;
if (curlen < result) {
result = curlen;
}
sum -= nums[left++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
题后感：窗口怎么滑动需要好好想想，先控制窗口右边界，当滑到窗口内的和满足条件了，控制左窗口右移动一格，因为其实这个时候如果你不移动左窗口，右窗口右移后窗口内和也一定比刚才大、长度比刚才长，左侧不动的情况下没有必要再继续比下去了，所以左侧右移一格。如此循环判断。
59.螺旋矩阵II
https://leetcode.cn/problems/spiral-matrix-ii/description/
class Solution {
public int[][] generateMatrix(int n) {
int loop = n / 2;
int data = 1;
int[][] result = new int[n][n];
for(int i = 0; i < loop; i++) {
int startx = i;
int starty = i;
int x = 0;
int y = 0;
// 上边
for(y = starty; y < n - (i + 1); y++) {
result[startx][y] = data++;
}
// 右边
for(x = startx; x < n - (i + 1); x++) {
result[x][y] = data++;
}
// 下边
for(; y >= i + 1; y--) {
result[x][y] = data++;
}
// 左边
for(;x >= i + 1; x--) {
result[x][y] = data++;
}
}
if (n % 2 == 1) {
int index = n / 2;
result[index][index] = n * n;
}
return result;
}
}
题后感：
- 题目很简单，但是逻辑写起来就错
- 循环不变量很重要，一定要想清楚是开区间还是闭区间，如果是作闭右闭必然会有问题
- 看讲解视频的时候觉得很清楚，但是自己写的时候还是会错，所以又按照自己的思路捋了一遍逻辑
1.首先，确定循环几圈，等于n/2
2.其次，确定每次循环的逻辑，每次起点的坐标和当前第几圈的关系是确定的，起点确定后每次循环的4个边的循环逻辑就能判断出来了
3.针对每次循环的4个边：
上边，从左至右，x坐标不变，y递增，不包括右上角的点；
右边，从上至下，x左边递增，y不变，不包括右下角的点；
下边，从右至左，x坐标不变，y递减，不包括左下角的点；
左边，从下至上，x坐标递减，y不变，不包括左下角的点。
4.不要忘记判断奇数n的情况，这个判断放在循环之外最后加上即可
