977. 有序数组平方【简单】
LeetCode 官方题解
暴力排序
思路:先平方,再排序
1 2 3 4 5 6 7 8 9 10
| class Solution { public: vector<int> sortedSquares(vector<int>& nums) { for(int i = 0; i < nums.size(); i++) { nums[i] *= nums[i]; } sort(nums.begin(), nums.end()); return nums; } };
|
【C++】sort函数使用方法 : sort 函数是快排的改良版,结合了堆排序等排序方法。
双指针
- 思路
- 个人理解:
- 定义两个指针:队首指针、队尾指针
- 定义一个与原数组相同大小的空数组
- 队首指针遍历,同时与队尾指针比较平方后大小,大的那一个放到空数组的队尾
- 放到队尾这里也需要定义一个指针用于记录位置信息,如下面代码的 right_result
(所以为啥不叫三指针法)
- 指针重合即停止 (这个判断条件有误,应该是 left <= right,否则会进入死循环)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| #include <vector> #include <cmath> using namespace std;
class Solution { public: vector<int> sortedSquares(vector<int>& nums) { int left = 0; int right = nums.size() - 1; int right_result = right; vector<int> result(nums.size(), 0); while (left <= right) { int left_square = nums[left] * nums[left]; int right_square = nums[right] * nums[right]; if (left_square > right_square) { result[right_result] = left_square; left++; } else { result[right_result] = right_square; right--; } right_result--; } return result; } };
|
1
| vector<int> result(nums.size(), 0);
|
上述代码:创建并初始化了一个名为 result 的 vector 类型的对象,vector 是一个构造函数,可以接受两个参数:
- size:表示vector的大小
- value:表示vector中每个元素的初始大小
下面详细解释上述代码的含义:
- vector:
vector<int>
是 C++ 标准库中的一个模板类,用于表示一个动态数组。vector
是一个模板类,<int>
表示这个 vector
将存储 int
类型的元素。
- result:
result
是这个 vector<int>
对象的名称。它是一个变量名,表示我们将使用这个名称来引用这个 vector
对象
- nums.size():
nums
是一个 vector<int>
类型的对象。nums.size()
返回 nums
中元素的个数,即 nums
的大小。这个大小是一个无符号整数类型(通常是 size_t
)。
209. 长度最小的子数组【中等】
代码随想录
个人思路(暴力解)
我的思路应该就是暴力解……
- 定义外循环用于遍历整个数组
- 内循环用于把 i 与后面的元素想加,直到出现 >= target的情况,或者遍历完
- 定义一个 int 类型变量 result = 0,用于记录最小连续子数组的长度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int result = 0; 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) { result = j - i + 1; continue; } } } return result; } };
|
很遗憾,我的代码错了,GPT给出的问题如下:
- 条件判断错误:你在内部循环中检查
sum == target
,但题目要求的是总和大于等于 target
。
- 结果更新错误:你没有正确更新
result
。你需要在找到满足条件的子数组时更新 result
,并且应该保留最小的长度。
- 效率问题:你的算法是一个 O(n2)O(n2) 的暴力解法,对于较大的输入数组会导致超时。
修改后的代码如下,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int result = 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) { result = min(result, j - i + 1); break; } } } return result == INT_MAX ? 0 : result; } };
|
修改说明:
- 条件判断修正:
- 将
if (sum == target)
修改为 if (sum >= target)
,以满足题目要求。
- 更新结果:
- 在找到符合条件的子数组时,使用
result = min(result, j - i + 1)
来更新最小长度。
- 跳出内层循环:
- 一旦找到一个符合条件的子数组,立即跳出内层循环,因为在当前起点
i
继续寻找更长的子数组是没有意义的。
- 返回结果:
- 如果
result
没有被更新,说明没有找到符合条件的子数组,返回 0。
- 否则返回
result
。
思路应该是没什么问题了,很不幸,超时了,leetcode给了一个超级离谱的测试样例。
三元运算符
1
| condition ? value_if_true : value_if_false
|
- condition:这是一个布尔表达式,计算结果要么是
true
,要么是 false
。
- value_if_true:如果
condition
为 true
,则返回这个值。
- value_if_false:如果
condition
为 false
,则返回这个值。
滑动窗口
所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。
在本题中实现滑动窗口,主要确定如下三点:
窗口内是什么?
- 窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
如何移动窗口的起始位置?
如何移动窗口的结束位置?
- 窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int result = INT32_MAX; int sum = 0; int i = 0; int subLength = 0; for (int j = 0; j < nums.size(); j++) { sum += nums[j]; while (sum >= s) { subLength = (j - i + 1); result = result < subLength ? result : subLength; sum -= nums[i++]; } } return result == INT32_MAX ? 0 : result; } };
|
59. 螺旋矩阵II【中等】
视频讲解
这题……毫无思路,可见我对多维矩阵的理解极弱。
题解也看不懂,感觉就是硬套啊,这就是模拟的精髓吗?
据说这还是高频考题?看来得背下来了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> res(n, vector<int>(n, 0)); int startx = 0, starty = 0; int loop = n / 2; int mid = n / 2; int count = 1; int offset = 1; int i,j; while (loop --) { i = startx; j = starty;
for (j; j < n - offset; j++) { res[i][j] = count++; } for (i; i < n - offset; i++) { res[i][j] = count++; } for (; j > starty; j--) { res[i][j] = count++; } for (; i > startx; i--) { res[i][j] = count++; }
startx++; starty++;
offset += 1; }
if (n % 2) { res[mid][mid] = count; } return res; } };
|