Day2 数组的一些基本练习
- 前一阵子生病了，把这几天落下来的内容慢慢补
第一题 有序数组的平方 Lc 977
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
//使用双指针的思想完成此题，一开始我想的是直接暴力解，这有什么难的，直接平方然后sort，但是这样的话复杂度有ologn
//用双指针的话就是再开辟一个数组，然后两边比较，大的就放数组里面，思路很简单，就看代码熟练度怎么样
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int k =nums.size()-1;
vector<int> result(nums.size(),0);//这里的几个size我思考了很久，什么时候-1，什么时候不用-1，实际上就是开辟数组的时候需要那个多出来的位置，实际上变量写的时候就不用那个位置了。
for(int i=0,j=nums.size()-1;i<=j;){
if(nums[i]*nums[i]<nums[j]*nums[j]){
result[k--]=nums[j]*nums[j];
j--;
}else{
result[k--]=nums[i]*nums[i];
i++;
}
}
return result;
}
};
第二题 长度最小的子数组 Lc209
给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT32_MAX;
int sum=0;
int subL=0;
int i=0;
for(int j=0;j<nums.size();j++){
sum+=nums[j];
while(sum>=target){
subL = j-i+1;
result= min(result,subL);
sum -=nums[i]; //这里是滑动窗口的精髓，突出一个滑动，保证只需要遍历一次，前面那个i不用跟着动，跟着动的是sum。
i++;
}
}
return result == INT32_MAX ? 0: result;
}
};
第三题 螺旋矩阵 Lc59
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
主要是牢记左闭右开，把每一个段给分清楚，其他的代码写的都差不多。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res (n, vector<int> (n,0));
int startX=0,startY=0;
int count=1;
int loop=n/2; //控制圈数
int offset=1; //控制每次缩进去一个offset
int i,j; // 左闭右开
while(loop--){
for(j=startY;j<n-offset;j++){
res[startX][j]=count++;
}
for(i=startX;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++;
}
if(n%2){
res[n/2][n/2]=count;
}
return res;
}
};