代码随想录刷题-矩阵
977. 有序数组的平方
左右指针的经典应用
左右下标元素平方相比,大的放新数组右边,比较简单,不赘述
class Solution {
public:
vector<int> sortedSquares(vector<int> &nums) {
int len = nums.size();
vector<int> res(len, 0);
int j = len - 1;
int left = 0;
int right = len - 1;
while (left <= right) {
int leftValue = pow(nums[left], 2);
int rightValue = pow(nums[right], 2);
if (leftValue < rightValue) {
res[j--] = rightValue;
right--;
} else {
res[j--] = leftValue;
left++;
}
}
return res;
}
};
209. 长度最小的子数组
注意审题是大于等于目标值,不是等于目标值
滑动窗口的题
思路是先加上最右边的值,然后再循环判断是否大于等目标值,若大于等于则计算比较长度,然后减去左值让左下标往右移
最后返回
class Solution {
public:
int minSubArrayLen(int target, vector<int> &nums) {
int left = 0;
int right = 0;
int min = INT_MAX;
int sum = 0;
while (right < nums.size())
{
sum += nums[right];
while (sum >= target)
{
int len = right - left + 1;
min = min < len ? min : len;
sum -= nums[left++];
}
right++;
}
return min == INT_MAX ? 0 : min;
}
};
59. 螺旋矩阵 II
这一题主要是针对边界问题的探讨
先定圈数,在每一圈探讨每条行、边的值,然后再探讨中间值,看代码很容易看懂
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
int count = 1;
for (int round = 1; round <= n / 2; round++) {
for (int row = round - 1, column = round - 1; column < n - round; column++) {
res[row][column] = count++;
}
for (int row = round - 1, column = n - round; row < n - round; row++) {
res[row][column] = count++;
}
for (int row = n - round, column = n - round; column > round - 1; column--) {
res[row][column] = count++;
}
for (int row = n - round, column = round - 1; row > round - 1; row--) {
res[row][column] = count++;
}
}
if (n % 2 == 1) {
res[n / 2][n / 2] = count;
}
return res;
}
};