day2
977 有序数组的平方
题目链接：977.有序数组的平方
思路：
第一种，直接暴力排序，先对数组进行平方，再用sort()排序；
第二种，双指针法 从两边开始遍历找到最大的数依次向中间缩小。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
// 双指针法
// C++基础：定义数组注意事项
vector<int> result(nums.size(), 0);
int k = nums.size() - 1;
for( int i = 0 , j = nums.size()-1; i <= j; ){
if ( nums[i]*nums[i] > nums[j]*nums[j] ){
result[k--] = nums[i]*nums[i];
i++;
}
else{
result[k--] = nums[j]*nums[j];
j--;
}
}
return result;
//时间：O(n) n为数组长度
//空间：O(1)
// 暴力排序
// for ( int i = 0; i < nums.size(); i++){
// nums[i] *= nums[i];
// }
// sort(nums.begin(),nums.end());
// return nums;
// 时间：O(nlogn)
// 空间：O(logn)
}
};
209 长度最小的子数组
题目链接：209.长度最小的子数组
思路：
第一种：暴力法，直接两层for循环
第二种：滑动窗口，也可以说是双指针法，遍历数组移动尾指针，计算总和，当总和满足要求时，计算区间长度，同时更新最小区间数组，滑动窗口核心sum -= nums[i++]
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
//滑动窗口
int result = INT32_MAX;
int i = 0;
int sum = 0;
int length = 0;
for( int j = 0; j < nums.size(); j++){
sum += nums[j];
while (sum >= target){
length = j - i + 1;
result = min(result,length);
// 滑动窗口核心
sum -= nums[i++];
// i++; 简洁写法
}
}
return result == INT32_MAX ? 0 : result;
}
};
59 螺旋矩阵II
题目链接：59.螺旋矩阵II
思路：
把握循环不变量->每条边的规则 采用左闭右开规则，一共四个边，每个边的计算规则不同
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
// 定义二维数组 C++中定义二维数组
vector<vector<int>> num(n,vector<int>(n,0));
int startx = 0;
int starty = 0;
int loop = n / 2;
int offset = 1;
int count = 1;
int mid = n/2;
int i,j;
while ( loop-- ){
for ( j = starty; j < n - offset; j++){
num[startx][j] = count++;
}
for ( i = startx; i<n-offset;i++){
num[i][j] = count++;
}
for (;j > starty;j--){
num[i][j] = count++;
}
for (;i > startx;i--){
num[i][j] = count++;
}
startx++;
starty++;
offset++;
}
if ( n % 2 == 1){
num[mid][mid]=count;
//此时i,j都变为0
// num[i][j]=count;
}
return num;
}
};