数组，977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II
977.有序数组的平方
自己审题思路
首先想到暴力解法：将数组元素都平方后进行排序。但是想到这道题的初衷应该不是这样。
之后想到两边大中间小，将两边放到数组最后，中间放置数组前面。
自己写的时候卡在怎么放置平方后的数，其实建立一个新数组就好。
看完代码随想录题解后的收获
1、从两边遍历数组，使用双指针；
2、返回一个数组，第一时间应想到建立一个新的数组。
双指针代码：
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int k = nums.size() - 1;
vector<int> result(nums.size(),0);
for ( int i = 0, j = nums.size() - 1; i <= j;) {// i <= j，双指针重合后最后一个元素也需要处理（奇数个元素）
if (nums[i]*nums[i] < nums[j]*nums[j]) {
result[k--] = nums[j]*nums[j];
j--;//放入新数组后前移
} else {
result[k--] = nums[i]*nums[i];
i++;//放入新数组后后移
}
}
return result;
}
};
参考详解
209.长度最小的子数组
自己审题思路
第一时间只想到了暴力解法，两层for循环(一层用来遍历数组，一层用来找最小数组)。
暴力解法代码实现(超时)
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = __INT32_MAX__;
int sublen = 0;
int sum;
for (int i = 0; i < nums.size(); i++) {
sum = 0;
for (int j = i;j < nums.size(); j++) {
sum += nums[j];
if (sum >= target) {
sublen = j - i + 1;
result = result < sublen ? result : sublen;
break;
}
}
}
return result < __INT32_MAX__ ? result : 0;
}
};
看完代码随想录题解后的收获
1、学习滑动窗口思想
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = __INT32_MAX__;
int sum = 0;
int sublen = 0;
int i = 0;
for (int j = i; j < nums.size(); j++) {
sum += nums[j];
while (sum >= target) {// 这里使用while而不是if，每次更新 i（起始位置），并不断比较子序列是否符合条件
sublen = j - i + 1;
result = result < sublen ? result : sublen;
sum -= nums[i];// 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
i++;
}
}
return result < __INT32_MAX__ ? result : 0;
}
};
while (sum >= target) 这里使用 while是因为要不断更新起始位置，假设输入数组是[1,1,1,1,100],target = 100，
则sum加到104后需要不断缩小范围（得到最小数组[100]），而不是只if判断一次。
参考详解
59.螺旋矩阵II
自己审题思路
拿到题有一定的思路，但是在处理边界问题是有点头晕；
并且在构建vector二维数组那卡了下，体现出我对C++语法不熟悉
看完代码随想录题解后的收获
数组问题，边界处理是个难点，左闭右开比较适合我的思路，以后尽量使用左闭右开区间；
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> ans(n, vector<int>(n, 0));
int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
int loop = n / 2; // 每个圈循环几次，例如n为奇数3，那么loop = 1 只是循环一圈，矩阵中间的值需要单独处理
int mid = n / 2; // 矩阵中间的位置，例如：n为3， 中间的位置就是(1，1)，n为5，中间位置为(2, 2)
int count = 1; // 用来给矩阵中每一个空格赋值
int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位
while (loop--) {
i = startx;
j = starty;
for (; j < n - offset; j++) {
ans[startx][j] = count++;
}
for (; i < n - offset; i++) {
ans[i][j] = count++;
}
for (; j > starty; j--) {
ans[i][j] = count++;
}
for (; i > startx; i--) {
ans[i][j] = count++;
}
// 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
startx++;
starty++;
// offset 控制每一圈里每一条边遍历的长度
offset++;
}
if (n%2 == 1) ans[mid][mid] = count++; // // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
return ans;
}
};
参考详解
今日感想：
速度还是太慢！
