代码随想录算法训练营Day02|977.有序数组的平方、209.长度最小的子数组、59. 螺旋矩阵 II
977.有序数组的平方
首先还是仔细审题，题目给出的数组为非递减顺序，平方生成的新数组也必须是非递减顺序。
题解如下：
①暴力解法
最简单必然是暴力解法，我们直接对数组进行原地修改，然后进行快速排序。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for(int i = 0; i < nums.size(); i++) {
nums[i] = nums[i] * nums[i];
}
sort(nums.begin(), nums.end());
return nums;
}
};
但该解法的时间复杂度为O(n+nlogn)，所以遇到大规模的输入会出现超时的情况。
快速排序的时间复杂度为O(nlogn)
②双指针法
主要思想是数组本身有序，所以平方后最大值只可能出现在数组的两端。于是我们同时判断左右两端平方后的数组大小，将数值较大的一边倒序插入返回的结果数组。
关于数组两端平方相等的情况，随便插入其中一端即满足非递减的数组要求。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int len = nums.size();
vector<int> res(len, 0);
int i = nums.size() - 1;
int left = 0, right = nums.size() - 1;
while (left <= right) {
if (nums[left] * nums[left] < nums[right] * nums[right]) {
res[i--] = nums[right] * nums[right];
right--;
}
else {
res[i--] = nums[left] * nums[left];
left++;
}
}
return res;
}
};
时间复杂度提升为O(n)。
209.长度最小的子数组
首先需要注意题干：
- 要求的是连续子数组：所以元素累加时中间不能断
- 给定数组并未强调排序：在设计滑动窗口时需要注意
①暴力解法
将每个下标依次作为连续子数组的起点进行遍历，找到满足条件的最小子数组长度。
注意最小数组长度的初始值设置为INT_MAX
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int res = INT_MAX;
for (int i = 0; i < nums.size(); i++) {
int sum = 0;
for (int j = i; j < nums.size(); j++) {
sum += nums[j];
if (sum >= target) {
int tmp = j - i + 1;
res = res > tmp ? tmp : res;
break;
}
}
}
return res == INT_MAX ? 0 : res;
}
};
暴力法因为算法复杂度为O(n*n)，遇到大规模的数据集会报错。
②滑动窗口法
滑动窗口的大致思想是在原数组上移动前后端点的同时，将累加和与目前值target进行比对，如果超出范围则将起点的坐标向前移动。我们需要注意目前长度需要初始化为INT_MAX，因为滑动过程中可能出现多个满足target的情况，而我们只需要取最小值即可，代码如下：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 注意子数组长度的初始值
int res = INT_MAX;
// 滑动窗口初始点不定时变化，所以单拎出来
int subLen = 0, i = 0, sum = 0;
for (int j = 0; j < nums.size(); j++) {
sum += nums[j];
while (sum >= target) {
subLen = j - i + 1;
res = res < subLen ? res : subLen;
sum -= nums[i++];
}
}
return res == INT_MAX ? 0 : res;
}
};
虽然代码形式为for循环与while循环的嵌套，但实际上实际复杂度为O(n)。因为从代码逻辑上考虑每个元素都在for循环中进入一次窗口，而在while循环中移出一次窗口，虽然会存在一个for循环内起点坐标多次移动的情况（指的是while循环），但整体来说所有元素都是一进一出。所以时间复杂度严格来说是O(n*2)。
59. 螺旋矩阵 II（⭐️高频）
不用想复杂了，这题重在代码逻辑而不是算法。
题干说明了数字的循环逻辑是：
- 从左往右
- 从上往下
- 从右往左
- 从下往上
而且每经历一圈，起始点的范围都会向内进行收缩。关键在于保证循环不变量统一，也就是四个for循环的边界均为左开右闭。
另外需要考虑奇偶边长的不同情况：虽然它们的循环次数都为n/2，但奇数边长的中心点需要单独拎出来进行赋值。
代码如下：
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
// 先讨论n=1的特殊情况，此时不需要进行循环
if (n == 1) {
vector<vector<int>> res(n, vector<int>(n, 1));
return res;
}
vector<vector<int>> res(n, vector<int>(n, 0));
int num = 1;
int offset = 0;
int loop = n / 2;
while (offset != loop) {
int i, j;
for (i = 0 + offset, j = 0 + offset; j < n - 1 - offset; j++) {
res[i][j] = num++;
}
for (i = 0 + offset, j = n - 1 - offset; i < n - 1 - offset; i++) {
res[i][j] = num++;
}
for (i = n - 1 - offset, j = n - 1 - offset; j > 0 + offset; j--) {
res[i][j] = num++;
}
for (i = n - 1 - offset, j = 0 + offset; i > 0 + offset; i--) {
res[i][j] = num++;
}
offset++;
}
// 单独给奇数边长的中心点赋值
if (n % 2)
res[n/2][n/2] = num;
return res;
}
};