代码随想录day2|| 977. 有序数组的平方、209. 长度最小的子数组、59. 螺旋矩阵
977.有序数组的平方
209.长度最小的子数组
59. 螺旋矩阵 II
977、有序数组的平方
解题思路:
一、利用双指针
数组是有序的,但平方之后不一定有序了,那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间,此时可以使用双指针,left指向起始位置,right指向终止位置。定义一个新数组result,和A数组一样的大小,让k指向result数组终止位置。
如果A[left] * A[left] < A[right] * A[right] 那么result[k–] = A[right] * A[right]。
如果A[left] * A[left] >= A[right] * A[right] 那么result[k–] = A[left] * A[left];。
时间复杂度为O(n)
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
vector<int>s;
int k = A.size() - 1;
int left = 0;
vector<int> result(A.size(), 0);
int right = A.size()-1;
for(int i = 0, j = A.size() - 1; i <= j;){
if(A[i]*A[i] <= A[j]*A[j]){
result[k--] = A[j] * A[j];
j--;
}
else{
result[k--] = A[i]*A[i];
i++;
}
}
return result;
}
};
二、暴力法
//
// Created by hcy on 2023/4/7.
//时间复杂度:O(n + nlog n)
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
for (int i = 0; i < A.size(); i++) {
A[i] *= A[i];
}
sort(A.begin(), A.end()); // 快速排序
return A;
}
};
收获
对于非递减数组的问题,可以考虑使用双指针的方法来解决,时间复杂度为O(n)。
最后的时间复杂度为O(n),因为双指针只需要遍历整个数组一次,空间复杂度也为O(n),需要使用一个新数组来保存平方后的结果
209.长度最小的子数组
解题思路
一、滑动窗口:
1)先找到一个大于或等于s的连续串,在这个过程中滑窗向前扩张。
2)收缩滑窗,目的是找到满足条件且最短的窗
所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。主要用于处理连续的数组数据或者字符串数据,常用来提取数据中的子数组或者子串。
滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将时间复杂度为O(n2)的暴力解法降为O(n)。
时间复杂度:O(n) 空间复杂度:O(1)
int minSubArrayLen(int s, vector<int>& nums) {
//用双滑窗的方法 这里尽量清晰和精简思路
//开始滑
int len = nums.size();
int sums = 0; //表示目前窗内元素的和
int ans_len = INT_MAX;
int left = 0;
int right = 0;
while(!(right==len && sums<s)){
//第一步 确定双滑窗的区间 左闭右开
while(right<len && sums<s){ //没满足条件 开始扩张
sums += nums[right];
right++;
}
//加完了 要么满足条件 要么加到低都不满足条件
if(sums>=s){
int newlen = right-left;
if(ans_len>newlen) ans_len = newlen;
}
//更新sums
sums -= nums[left];
left++;
}
if(ans_len == INT_MAX) return 0;
return ans_len;
}
收获
整个思路很清晰,从初始化条件到最终求解都是一套整体的逻辑,不存在逻辑混乱的情况,所谓逻辑混乱就是本来是整体的逻辑现在却弄了好几套逻辑来表达,导致可能的情况太多,出错的机会就大。 但是还是存在一些无法完全说清的东西,本来也能说清,但是觉得没必要,这种东西交给临场逻辑去发挥
二、暴力法:
两个for循环,第一层for循环控制区间的起始位置,第二层for循环控制区间的终止位置。
把数组的所有区间情况都遍历出来,然后找到 >= target 的最小区间长度。
在这个区间里面不断搜索,把所有区间情况都枚举出来,然后判断 >= target 的最小长度是多少,最后返回这个最小长度。
// 时间复杂度:O(n^2) 空间复杂度:O(1)
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int result = INT32_MAX; // 最终的结果
int sum = 0; //
int subLength = 0; //子序列长度
for(int i = 0; i< n; i++){
for(int j = i; j < n; j++){
sum += nums[j];
if (sum >= target) { // 一旦发现子序列和超过了s,更新result
subLength = j - i + 1; // 取子序列的长度
result = result < subLength ? result : subLength;
break; // 因为我们是找符合条件最短的子序列,所以一旦符合条件就break
}
}
}
return result == INT32_MAX ? 0 : result;
}
};
59、 螺旋矩阵 II
解题思路:
- 需要设定边界值,碰到边界值即停止的同时转向
- 我的方法会将坐标溢出一个位置,故在转向的时候会多加一行代码调整回来
上->右->下->左 循环赋值
// 时间复杂度 O(n^2) 空间复杂度 O(1)
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> ans(n);
for (int i = 0; i < ans.size(); i++) //注意先设定好ans的size
ans[i].resize(n);
int num = n * n;
int i = 1;
int l = 0;
int r = n - 1;
int u = 0;
int d = n - 1;
while (i <= num) {
for (int j = l; j <= r && i <= num; i++, j++)
ans[u][j] = i;
u++;
for (int j = u; j <= d && i <= num; i++, j++)
ans[j][r] = i;
r--;
for (int j = r; j >= l && i <= num; i++, j--)
ans[d][j] = i;
d--;
for (int j = d; j >= u && i <= num; i++, j--)
ans[j][l] = i;
l++;
}
return ans;
}
};