977-有序数组的平分-双指针法
思路
nums数组是由小到大排序,平方之后要么是个V型,要么还是由小到大,设立两个指针leftindex、rightindex指向平方后nums数组一头一尾,比较这一头一尾,另外建一个result数组(大小和nums一样),k指向result最后一个元素,将比较出来的较大值放在result数组第k个位置上,然后k–、leftindex++(或rightindex–),直到leftindex==rightindex,将nums[rightindex]放在result[0]
code
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for(int i=0;i<nums.size();i++){
nums[i]=nums[i]*nums[i];
}
int k=nums.size()-1;
vector<int> result(nums.size(),0);
int leftindex=0,rightindex=nums.size()-1;
while(leftindex<=rightindex){
if(nums[leftindex]>nums[rightindex]){
result[k]=nums[leftindex];
leftindex++;
k--;
}
else{
result[k]=nums[rightindex];
rightindex--;
k--;
}
}
return result;
}
};
209-长度最小的子数组-滑动窗口
思路
我的思路是外层while循环判断right是不是到达了边界,内层先是for循环找到当前left不能 继续sum+=sum[right]的情况:
有可能是 1:sum>=target,然后判断当前窗口长度now和min的大小
也有可能是2:right==nums.size(),应该break跳出while循环。
code
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
long long left=0,right=1;
long long min=INT32_MAX;
long long sum=nums[0];
while(right<=nums.size()){//right一直是下一个要+的元素,也就是sum目前的值是[left...right-1]的和
for(;sum<target&&right<nums.size();right++){
sum+=nums[right];
}
if(right==nums.size()&&sum<target)//right到了尾部,还是不满足条件,就退出while循环
{break;}
else if(sum>=target){//find a 连续子数组
long long now=right-left;
if(now<min){
min=now;
}
sum-=nums[left];
left++;
}
}
return min==INT32_MAX?0:min;
}
};
还有来自代码随想录的:
外层for循环,内层while循环,直接找到sum>=target&&right<nums.size()的情况,然后去计算now,和min比较,再缩小窗口。
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,每次更新 i(起始位置),并不断比较子序列是否符合条件
while (sum >= s) {
subLength = (j - i + 1); // 取子序列的长度
result = result < subLength ? result : subLength;
sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)
}
}
// 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列
return result == INT32_MAX ? 0 : result;
}
};
59-螺旋矩阵
思路
要填充的是一个边长为n的正方形,把未填充的边长为length的正方形的最外圈作为一次循环,按顺序分为四步操作:
1. i=startx,starty<=j<starty+length
2. startx<=i<startx+length,j=starty+length
3. i=startx+length,starty+length>=j>starty
4. startx+length>=i>startx,j=starty文章来源:https://www.toymoban.com/news/detail-441055.html
code
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int startx=0,starty=0;
int loop=n/2;
int length=n-1;//最开始一圈,每一步要遍历的长度
int num=1;//要填充的数
vector<vector<int>> squ(n,vector<int>(n,0));
while(loop--){
int i;
int j;
for(j=starty;j<starty+length;j++){
squ[startx][j]=num++;
}
for(i=startx;i<startx+length;i++){
squ[i][j]=num++;
}
for(j=starty+length;j>starty;j--){
squ[i][j]=num++;
}
for(i=startx+length;i>startx;i--){
squ[i][j]=num++;
}
startx++;
starty++;
length-=2;
}
if(n%2){
squ[n/2][n/2]=num;
}
return squ;
}
};
数组总结
文章来源地址https://www.toymoban.com/news/detail-441055.html
到了这里,关于算法DAY02的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!