代码随想录算法训练营 day 2 | 有序数组 长度最小子数组 螺旋矩阵
977 有序数组的平方
冒泡排序
暴力冒泡排序实现
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int size = nums.size();
int tmp;
for (int i = 0; i < size; i++)
nums[i] = nums[i] * nums[i];
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) { //时间复杂度O(n^2)
if (nums[i] > nums[j]) {
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
}
return nums;
}
};
点击查看代码
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int size = nums.size() - 1;
int slow = size - 1;
for (int i = 0, j = size - 1; i<=j; ) {
if (nums[i] * nums[i] <= nums[j] * nums[j]) {
nums[slow] = nums[j] * nums[j];
j--;
} else {
nums[slow] = nums[i] * nums[i];
i++;
}
slow--;
}
return nums;
}
};
209 最小子数组
循环暴力解法:O(n^3)超时
三层循环实现
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int size = nums.size();
int len = 1;
int ret = 0;
for (int len = 1; len <= size; len++) { // O(n^3)
for (int i = 0; i + len - 1 < size; i++) {
int localSum = 0;
for (int j = i; j <= i + len - 1; j++) {
localSum += nums[j];
if (localSum >= target) {
ret = len;
goto end_loop;
}
}
}
}
end_loop:
return ret;
}
};
滑动窗口思路:起始位置和终止位置如何确定
for两层循环分别确定起始和终止位置
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sublength = INT32_MAX; //这里容易设置为0
int size = nums.size();
for (int i = 0; i < size; i++) {
int sum = 0;
for (int j = i; j < size; j++) {
sum += nums[j];
if (sum >= target) {
sublength = (j - i + 1) < sublength ? (j - i + 1) : sublength; // sublength设置为零,则结果一直为0
break;
}
}
}
return sublength == INT32_MAX ? 0 : sublength;
}
};
滑动窗口:特殊的快慢双指针(先确定一个边界位置)
求最大和最小长度:缩小法
求最小值最大长度:放大法
以快慢指针的角度理解滑动窗口
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sublength = INT32_MAX;
int size = nums.size();
int sum = 0;
for (int i = 0; i < size; i++) { //多个慢指针:对每一个终止位置的最大区间进行缩小
sum += nums[i];
int j = 0; //这里设置为零,其实做了重复的工作,比如 1 + (2 + 3) + 4 + 5
int tmp = sum;
while (tmp >= target) {
sublength = (i - j + 1) < sublength ? (i - j + 1) : sublength; // sublength设置为零,则结果一直为0
tmp -= nums[j++]; //缩小法
}
}
return sublength == INT32_MAX ? 0 : sublength;
}
};
真正意义的滑动窗口
真正的滑动窗口实现
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sublength = INT32_MAX;
int size = nums.size();
int sum = 0;
int j = 0;
for (int i = 0; i < size; i++) { //多个慢指针:对每一个终止位置的最大区间进行缩小
sum += nums[i];
// int j = 0;
// int tmp = sum;
while (sum >= target) {
sublength = (i - j + 1) < sublength ? (i - j + 1) : sublength; // sublength设置为零,则结果一直为0
sum -= nums[j++]; //缩小法 《体现滑动》
}
}
return sublength == INT32_MAX ? 0 : sublength;
}
};
59 螺旋矩阵II
思路:四条路线,四个边界,每走一条路线,边界往里缩1
代码实现
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int u = 0, d = n - 1, l = 0, r = n - 1;
int sum = n * n;
vector<vector<int>> vec(n, vector<int>(n)); //初始化方式
int i = 1;
while (i <= sum) {
for (int j = l; j <= r; j++) { //判断条件易写错,比如l <= r
vec[u][j] = i++;
}
u++;
for (int k = u; k <= d; k++) {
vec[k][r] = i++;
}
r--;
for (int x = r; x >= l; x--) {
vec[d][x] = i++;
}
d--;
for (int y = d; y >= u; y--) {
vec[y][l] = i++;
}
l++;
}
return vec;
}
};
热门相关:佣兵之王都市行 1号婚令:早安,大总裁! 北宋闲王 惊艳人生 黑暗血时代