代码随想录打卡第二天, 新手自我记录一下刷题历程, 仅为自我打卡使用.
今天刷了三道主题, 第一道双指针和第三道模拟做出来了, 第二道写出了暴力解法但是提交leetcode超时了, 测试用例过了18/20, 看了carl哥答案以后自己重新补写了滑动窗口方法.
977. 有序数组的平方
简单题, 要求时间复杂度O(n), 考虑使用双指针.
观察到数组为有序数组, 可能有负数.
建立一个与输入等长的新数组作为容器, 双指针分别指向输入数组的两端, 不断比较指针所指的元素的平方值的大小, 将较大的一端放入新容器并移动指针位置.
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
vector<int> result(nums);
for (int i = result.size()-1; i >= 0; --i){
if (nums[left]*nums[left] >= nums[right]*nums[right]){
result[i] = nums[left]*nums[left];
left++;
}
else {
result[i] = nums[right]*nums[right];
right--;
}
}
return result;
}
};
209.长度最小的子数组
暴力解法时间复杂度O(n^2), 即对每个可能的起点都找一遍满足条件的最小子数组长度.
据说leetcode更新数据以前是能过的.
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int min_len = nums.size() + 1;
for (int i = 0; i < nums.size(); ++i){
int sum = 0;
int len = nums.size() + 1;
for (int j = i; j < nums.size(); ++j){
sum += nums[j];
if (sum >= target){
len = j - i + 1;
break;
}
}
if (len < min_len){
min_len = len;
}
}
if (min_len != nums.size() + 1){
return min_len;
}
else{
return 0;
}
}
};
滑窗: 一个for循环, 每个元素进入和退出窗口时各操作一次, 时间复杂度O(2n) = O(n)
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int min_len = nums.size() + 1;
int sum = 0;
int sub_len = nums.size() + 1;
// start i, end j
int i = 0;
for (int j = 0; j < nums.size(); ++j){
sum += nums[j];
while (sum >= target){
sub_len = j - i + 1;
sum -= nums[i];
i++;
}
if (sub_len < min_len){
min_len = sub_len;
}
}
if (min_len != nums.size() + 1){
return min_len;
}
else {
return 0;
}
}
};
59.螺旋矩阵II
循环不变量, 写的时候思路和标准答案稍有一点点区别, 想的是在每条新边上走几步, 代码看起来比答案乱一点.
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> result(n, vector<int>(n, 0));
int start_idx = 0;
int num = 1;
int count = 0;
for (int i = n; i > 0; i-=2){
for (int j = start_idx; j < start_idx + i - 1; ++j){
result[start_idx][j] = num;
num++;
}
for (int j = start_idx; j < start_idx + i - 1; ++j){
result[j][i-1+start_idx] = num;
num++;
}
for (int j = start_idx; j < start_idx + i - 1; ++j){
result[i-1+start_idx][i+2*count-1-j] = num;
num++;
}
for (int j = start_idx; j < start_idx + i - 1; ++j){
result[i+2*count-1-j][start_idx] = num;
num++;
}
start_idx++;
count++;
}
if (n % 2 == 1){
result[n/2][n/2] = num;
}
return result;
}
};
另外看leetcode网站大神题解中有一种上下左右移边界的题解做法感觉更助于理解, 更有美感.
数组部分的主干题目刷完啦! 撒花!文章来源:https://www.toymoban.com/news/detail-454801.html
明天开始链表!文章来源地址https://www.toymoban.com/news/detail-454801.html
到了这里,关于[自我记录]随想录刷题第二天 | 977.有序数组的平方,209.长度最小的子数组,59.螺旋矩阵II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!