一.移动零
算法思想 :
设置两个指针left,right,将数组分为三块[0,left]为不为0的元素,[left+1,right-1]为0元素,[right,num.size()-1]为未扫描的区域,判断right位置,不为0元素则与left+1位置元素交换,left++和right++;为0则只有right++,这样right扫描到最右侧时保证右侧全是0。
class Solution {
public:void moveZeroes(vector<int>& nums){int cur=0,dest=-1;while(cur<nums.size()){if(nums[cur]){swap(nums[cur],nums[++dest]);}cur++; }}
};
ps:数组分块扫描划分是快排的核心思想
二.快速排序
算法思想:
与移动0相似,不过这里移动指针时将数组分为四块,l,r是当前(子)数组的最左侧与右侧,用i,left,right三个指针,[l,left]为小于随机基准元素key的区域,[left+1,i-1]是key区域,[i,right-1]为未扫描区域,[right,r]为大于key的元素,移动时控制区间即可。
void qsort(vector<int>& nums,int l,int r)
{if(l>=r) return;int key=nums[rand()%(r-l+1)+l];int i=l,left=l-1,right=r+1;while(i<right){if(nums[i]<key){swap(nums[++left],nums[i]);i++;}else if(nums[i]>key){--right;swap(nums[right],nums[i]);}else{i++;}}qsort(nums,l,left);qsort(nums,right,r);
}
class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(NULL));qsort(nums,0,nums.size()-1);return nums;}
};
三.复写零
算法思想:
1.找到最后一个要复写的元素。
cur为扫描指针,dest为移动指针,初始cur为0,dest为-1;当dest移动到最后一个元素时,cur指向最后一个要复写的元素。 但这里dest可能会超出(说明cur此时指向0),所以要先判断边界位置。
2.“从后往前”复写元素。
是0就将cur位置元素赋值给dest位置和dest-1位置,然后dest-=2;非0就将cur直接赋给dest位置,dest-=1;然后都有cur--。
void duplicateZeros(vector<int>& nums){//先找到最后一个数int cur=0,dest=-1;int tmp = nums.size() - 1;while(dest < tmp){if (nums[cur] == 0){dest += 2;}else{dest += 1;}if (dest >= tmp) break;cur++;}//判断边界情况,如果超出,就事先处理if(dest>nums.size()-1){cur--;dest-=2;nums[nums.size()-1]=0;}//从后向前复写for(;cur>=0;cur--){if(nums[cur]==0){nums[dest]=nums[dest-1]=0;dest-=2;}else{nums[dest]=nums[cur];dest--;}}}
四.快乐数
算法思想:
快慢指针的思想,因为这里数字最后都会循环,只要看快指针最后在环里与满指针相遇时所在的元素是否为一即可。
int fx(int x)
{int sum=0;while(x){sum+=(x%10)*(x%10);x/=10;}return sum;
}class Solution {
public:bool isHappy(int n) {int fast=n,slow=n;while(1){slow=fx(slow);fast=fx(fast);fast=fx(fast);if(fast==slow){if(fast==1)return true;elsereturn false; }}}
};
五.盛最多水的容器
算法思想:
对撞指针,设置left,right指针分别向左右侧,记录盛水量,去除左/右移较小元素的位置(因为移动更大一侧不会改变最大值),记录最大值即可。
class Solution {
public:int maxArea(vector<int>& height) {if(height.size() <= 1) return 0;int res = 0;//保存答案int l = 0, r = height.size() - 1;//开始时,l指向最左边的挡板,r指向最右边的挡板while(l < r)//如果l,r之间还有挡板{res = max(min(height[l], height[r]) * (r - l), res);//计算盛水值if(height[l] <= height [r])//谁小谁以后就不用再考虑 l++;elser--;}return res;}
};
六 .有效三角形的个数
算法思想:
先将数组排序,利用单调性使用双指针解决 。如下图a,b,c三个指针,当left,right指向判断区间左右侧,当a+b>c时,说明a右侧的全部元素都和b,c符合,所以right--来继续判断其他组合情况,当a+b<c时,说明此时abc不符合,让left++,重新判断a+b与c。直到left==right时结束这次循环,将c--(重新选择最大数)判断剩下组合。时间复杂度O(N*N);
class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int sum=0;for(int i=nums.size()-1;i>1;i--){int left=0,right=i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){sum+=right-left;right--;}else{left++;}}}return sum;}
};
七.三数之和
算法思想:
先排序,利用单调性用双指针解决问题。即依旧a(left),b(right),c三个指针,c指向当次循环最大值(初始指向数组最大值),判断a+b+c与0的关系,如果a+b+c<0则a++,a+b+c>0则b--,直到找出等于0的组合并记录下来,注意要去重操作(防止相同数字组合在一起)。当次操作完成后c--即可两层循环,时间复杂度依旧是O(N*N)。
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;sort(nums.begin(),nums.end());for(int i=0;i<=nums.size()-3;i++){int left=i+1,right=nums.size()-1;while(left<right){if(nums[i]+nums[left]+nums[right]<0){left++;}else if(nums[i]+nums[left]+nums[right]>0){right--;}else{//记录 ret.push_back({nums[i],nums[left],nums[right]});//去重left++,right--;while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}}while(i<=nums.size()-4&&nums[i]==nums[i+1]) i++;}return ret;}
};
八.长度最小的子数组(滑动窗口)
算法解析:
2个指针,扫描(前窗口)指针,尾指针。滑动窗口的步骤:1.扫描元素入窗口。2.判断是否需要出窗口。3.窗口向前滑动。 //记录结果这一步可以根据情况来调整位置。
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums){int left=0,right=0,n=nums.size();int sum=0,len=INT_MAX;while(right<n){//入窗口sum+=nums[right];//判断while(sum>=target){//更新结果len=min(len,right-left+1);//出窗口sum-=nums[left++];}right++;}return len==INT_MAX?0:len;}
};