1、移动零
1.1 题目解析
可以发现,这道题的本质就是通过某一个标准,将数组划分成不同区间(数组划分、数组分块),此时可以用到双指针算法
1.2 算法原理讲解
1.3 代码实现
class Solution {
public:void moveZeroes(vector<int>& nums) {for(int cur = 0,dest = -1;cur<nums.size();cur++)if(nums[cur])swap(nums[++dest],nums[cur]);}
};
2、复写零
2.1 解法一
利用顺序表,可以定义一个指针cur遍历数组的前n-1个元素,当cur指向的元素是0时,将cur后面所有元素都向后移动一位,在cur+1的位置赋值为0,当cur指向的元素是非0时,cur++
class Solution {
public:void duplicateZeros(vector<int>& arr) {for(int cur = 0;cur<arr.size()-1;cur++){if(arr[cur]==0){int dest = arr.size()-2;while(dest>=cur){arr[dest+1]=arr[dest];dest--;}cur++;}}}
};
2.2 解法二
操作数组中元素的题,一般也会用到双指针
若可以异地操作
可以发现,此时最后一个复制的元素是4
此时当cur指向的值是非0时,dest赋值为cur,并向前移动一位,当cur指向的值是0时,dest将前面两个位置都赋值为0
但问题是,如何找到cur开始的位置呢?
总结:1. 先找到最后一个需要复写的数(双指针算法)
先判断cur的值,决定dest一次走几步(注意起始时cur=0,dest=-1)
dest走完后,判断一下是否结束,若未结束,cur++
2. 从后向前完成复写操作(双指针法)
class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur = 0,dest = -1,n = arr.size();for(cur = 0;cur<=n;cur++)//找到最后一个需要复写的数{if(arr[cur]){dest++;}else{dest+=2;}if(dest>=n-1) break;}if(dest==n)//若最后一个需要复写的数是0{arr[n-1] = 0;dest-=2;cur--;}while(cur>=0)//从后向前复写数组{if(arr[cur]){arr[dest--] = arr[cur--];}else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};
3、快乐数
3.1 题目解析
3.2 算法原理讲解
当是快乐数变成1后,再一直平方,任然会一直是1,所以可以将第一种情况也抽象成有环,这样子就可以定义快慢指针了(与链表中的快慢指针类似),因为两种情况都有环,所以快慢指针一定会相遇,只需要判断相遇时是否是1即可。
注意:这里的指针是用数来当指针
3.3 代码实现
class Solution {
public:int Square(int n){int sum = 0;while(n){int x = n%10;sum+=(x*x);n/=10;}return sum;}bool isHappy(int n) {int slow = n,fast = n;do{slow = Square(slow);fast = Square(fast);fast = Square(fast);}while(slow!=fast);return slow==1;}
};
4、盛最多水的容器
4.1 算法原理讲解
这道题是可以暴力枚举的,两层循环,但是这样子会超时
正确的做法是定义一个指针在最左端,一个指针在最右端,计算出当前的体积,然后让高度小的那个往里面走,再次计算体积,与先前的体积取大的,直到两指针相遇。
4.2 代码实现
class Solution {
public:int maxArea(vector<int>& height) {int i = 0,j = height.size()-1,V = 0;while(i<j){V = height[i]<height[j]?max(V,(j-i)*height[i++]):max(V,(j-i)*height[j--]);}return V;}
};
5、有效三角形个数
由题意可知,这道题是允许出现重复的
当我们判断一个数组中的3项能否组成一个三角形时,若这个数组无序,则需要判断3次,但若这个数组有序,则只需要判断较小的2项之和是否大于第3项即可,并且这样做的时间复杂度也会更低
以暴力枚举为例,若判断3次,则3*N^3,排序+判断一次,则N^3+N*logN
5.1 代码原理讲解
这样使用双指针算法能让时间复杂度从暴力枚举减小一个量级
5.2 代码实现
class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int n = nums.size(),ans = 0;for(int c = nums.size()-1;c>=2;c--){int a = 0,b = c-1;while(a < b){if(nums[a]+nums[b]>nums[c]){ans += b - a;b--;}else{a++;}}}return ans;}
};
6、查找总价格为目标值的两个商品
此题暴力枚举也是会超时的,可以将数组排成有序,然后利用第5题中的方法解决
class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {sort(price.begin(),price.end());int left = 0,right = price.size() - 1;while(left < right){if(price[left] + price[right] > target)right--;else if(price[left] + price[right] < target)left++;else break;}vector<int> v{price[left],price[right]};return v;}
};
7、三数之和
这道题是不能出现重复的,所以要注意去重
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> vv;if(nums.size() < 3) return vv;sort(nums.begin(),nums.end());for(int i = nums.size() - 1;i>=2;){int left = 0,right = i - 1;while(left < right){if(nums[left] + nums[right] + nums[i] > 0)right--;else if(nums[left] + nums[right] + nums[i] < 0)left++;else{vv.push_back({nums[left],nums[right],nums[i]});// 匿名对象// 更新left和right,要去重int flag1 = nums[left++],flag2 = nums[right--];while(left < right && nums[left] == flag1) left++;while(left < right && nums[right] == flag2) right--;}}// 更新i,要去重int flag = nums[i--];while(i >= 2 && nums[i] == flag) i--;}return vv;}
};
8、四数之和
这道题是不能出现重复的,所以要注意去重
注意,这道题的数据范围较大,四个数相加会发生越界
此时超过了int的范围,前两个相加是没问题的,当第3个加上去的时候就出错了,此时可以让他们类型转换成long long,这样会发生整型提升
只要不是转换最后面的那个就可以,因为 + 是从左向右操作的
class Solution {
public:typedef long long ll;vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> vv;if(nums.size() < 3) return vv;sort(nums.begin(),nums.end());for(int i = nums.size() - 1;i>=3;){for(int j = i - 1;j>=2;){int left = 0,right = j - 1;while(left < right){if((ll)nums[left] + (ll)nums[right] + nums[j] + nums[i] > target)right--;else if((ll)nums[left] + (ll)nums[right] + nums[j] + nums[i] < target)left++;else{vv.push_back({nums[left],nums[right],nums[j],nums[i]});int flag1 = nums[left++] , flag2 = nums[right--];while(left < right && nums[left] == flag1) left++;while(left < right && nums[right] == flag2) right--;}}int flag = nums[j];while(j >= 2 && nums[j] == flag) j--;}int flag = nums[i];while(i >= 3 && nums[i] == flag) i--;}return vv;}
};