Day2 数组、双指针
LeetCode 977.有序数组的平方【排序/双指针】
要将数组的每个元素平方后在按非递减的顺序,最简单的方法就是先将每个数平方,再将结果数组排序。
解法1:排序
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> ans;
for(int i=0;i<nums.size();i++) ans.push_back(nums[i]*nums[i]);
sort(ans.begin(),ans.end());
return ans;
}
};
这里有一个小小的问题,vector在初始化之前不能用下标访问,否则会报错,也就是如果写成ans[i]=nums[i]*nums[i]是会报错的:runtime error: reference binding to null pointer of type ‘int’。
解法2:双指针算法
双指针算法的想法是基于本题的条件,原数组本来就是按照非递减的顺序排好的,我们可以利用这一条件,这种情况下,数组两端的数的平方一定比它内侧的数的平方要大,所以我们利用这一点,用两个指针分别从原数组两端选择最大的数,将它的平方逆序排到结果数组中即可。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> ans(nums.size(),0);
int i=0,j=nums.size()-1,k=nums.size()-1;
while(i<=j){
if(nums[i]*nums[i]>nums[j]*nums[j]){
ans[k--]=nums[i]*nums[i];
i++;
}
else{
ans[k--]=nums[j]*nums[j];
j--;
}
}
return ans;
}
};
LeetCode 209.长度最小的子数组【滑动窗口】
第一想法当然是暴力算法,但时间复杂度是n2,太大了,这里就不考虑了,除非万不得已,否则还是动动脑子吧。
解法:滑动窗口
滑动窗口就是实现了用一遍循环解决了两遍循环的问题,我们不必再用两遍循环处理子数组的两端,而是利用题目的条件,只在循环中处理右边界,左边界在特殊情况下专门处理,这样就能省下很多时间。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int i=0,sum=0,len=0,res=INT32_MAX;
for(int j=0;j<nums.size();j++){
sum+=nums[j];
while(sum>=target){//部分和大于target时要用while不断右移左边界,保证窗口宽度最小
len=(j-i+1);
res=res<len?res:len;
sum-=nums[i++];
}
}
return res==INT32_MAX?0:res;
}
};
LeetCode 59.螺旋矩阵II【模拟】
看似简单的转圈圈,要处理的边界条件却不少,处理每一条边的时候该处理几个元素,如何保证不重复、不遗漏,都是很关键的问题。一杯茶一包烟,螺旋矩阵转一天。
解法1:直接模拟
如果你对自己的边界处理很有自信,那就像贪吃蛇一样出发就可以了,一直向前,然后自己的数字变大,直到碰到已经处理过的元素或者边界为止,然后转弯继续走,按右→下→左→上的顺序循环往复,直到数字走到n*n为止。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> ans(n,vector<int>(n,0));
int i=0,j=0,x=2;
ans[0][0]=1;
while(x<=n*n){
while(j<n-1 && ans[i][j+1]==0) ans[i][++j]=x++;//右
while(i<n-1 && ans[i+1][j]==0) ans[++i][j]=x++;//下
while(j>0 && ans[i][j-1]==0) ans[i][--j]=x++;//左
while(i>0 && ans[i-1][j]==0) ans[--i][j]=x++;//上
}
return ans;
}
};
解法2:详细模拟
如果直接模拟有一定困难,那么我们可以对每次转圈,走过的每一条边都进行一下详细的分析,先确定圈数,然后对每次循环都保证走过的每条边都是在合理范围内的,如果边长为奇数,那么特判中心元素即可,比较复杂,但很详细,容易理解。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> ans(n,vector<int>(n,0));
int startx=0,starty=0;//每圈循环的起始位置
int loop=n/2;//循环的圈数
int mid=n/2;//矩阵中间位置,用于在n为奇数时为最中间的格赋值
int cnt=1;//控制赋值的大小
int offset=1;//控制每一条边的长度
int i,j;
while(loop--){
i=startx,j=starty;
while(j<n-offset) ans[i][j++]=cnt++;
while(i<n-offset) ans[i++][j]=cnt++;
while(j>starty) ans[i][j--]=cnt++;
while(i>startx) ans[i--][j]=cnt++;
startx++;
starty++;
offset++;
}
if(n%2) ans[mid][mid]=cnt;
return ans;
}
};
今天有点难度哦。