廊坊建站服务,wordpress分类做首页,网页qq登录保护功能,龙岗网络推广方式文章目录 1.算法思想2.移动零3.复写零方法一方法二 4.快乐数5.盛水最多的容器方法一#xff08;暴力求解#xff09;方法二#xff08;左右指针#xff09; 6.有效三角形的个数方法一#xff08;暴力求解#xff09;方法二#xff08;左右指针#xff09; 7.两数之和8.… 文章目录 1.算法思想2.移动零3.复写零方法一方法二 4.快乐数5.盛水最多的容器方法一暴力求解方法二左右指针 6.有效三角形的个数方法一暴力求解方法二左右指针 7.两数之和8.三数之和9.四数之和 1.算法思想
常见的双指针有两种形式⼀种是左右指针⼀种是快慢指针。
左右指针⼀般用于有序的结构中也称左右指针。
左右指针从两端向中间移动。⼀个指针从最左端开始另⼀个从最右端开始然后逐渐往中间逼近。左右指针的终⽌条件⼀般是两个指针相遇或者错开也可能在循环内部找到结果直接跳出循环也就是 left right 两个指针指向同⼀个位置 left right (两个指针错开
快慢指针⼜称为龟兔赛跑算法其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。 这种方法对于处理环形链表或数组非常有用。 其实不单单是环形链表或者是数组如果研究的问题出现循环往复的情况时均可考虑使用快慢指针的思想。 快慢指针的实现⽅式有很多种最常用的⼀种就是
在⼀次循环中每次让慢的指针向后移动⼀位而快的指针往后移动两位实现⼀快⼀慢。
废话不多说我们来做题。
2.移动零 leetcode 283.移动零
题目要求我们将数组中的0全部移动到数组的末尾并且其它元素的相对顺序不变而且不允许开辟额外的数组。 那我们应该如何来解决这一题呢 算法思路 在本题中我们可以⽤⼀个cur 指针来扫描整个数组另⼀个dest 指针⽤来记录⾮零数序列的最后⼀个位置。 根据cur 在扫描的过程中遇到的不同情况分类处理实现数组的划分。 在cur遍历期间使[0, dest] 的元素全部都是⾮零元素[dest 1, cur - 1] 的元素全是零。 最初我们不知道非零序列的位置所以将dest置为-1cur置为0。cur进行扫描在扫描过程中
若cur对应元素不为0cur后移若cur对应元素为0dest先后移然后再交换cur与dest最后cur再后移。 class Solution {
public:void moveZeroes(vectorint nums) {int dest -1;int cur 0;int n nums.size();while(cur n){//cur不为0交换if(nums[cur] ! 0){dest;swap(nums[dest],nums[cur]);}//cur为0,继续后移cur;}}
};这样咱们就过啦。
3.复写零 leetcode 1089.复写零
方法一
先统计数组中0的个数计算复写后数组的大小使用reserve为数组重新开新的空间在新空间上直接进行复写不存在数组越界问题在复写完成后再使用对数组进行缩容使其空间保持原状。
class Solution {
public:void duplicateZeros(vectorint arr) {int count 0;int n arr.size();int cur 0;while(cur n){if(arr[cur] 0)count;cur;}//开辟新空间arr.reserve(ncount);//此时cur n,cur--;//重新指向最后一个元素int dest ncount-1;while(cur 0){if(arr[cur]){//不是0无需复写arr[dest--] arr[cur--];}else{//复写0arr[dest--] 0;arr[dest--] 0;cur--;}}arr.reserve(n);//恢复数组原状}
};简单分析一下复杂度只遍历了数组时间复杂度为O(N)由于使用了reserve开辟了新空间空间复杂度O(N)
方法二
能不能在O(1)的空间复杂度下完成该题呢
我们可以使用两个指针cur指向最后一个要写的元素dest指向数组的最后一个位置。
若cur为0复写0dest移动两次若cur不为0复写dest移动一次
那现在的问题就是如何找最后一个要复写的位置。 通过模拟我们可以发现cur 0 ,dest -1让cur与dest同时走若cur不为0则都移动一次若cur为0cur移动一次dest移动两次直到dest走到数组的末尾此时cur位置就是最后一个要写的位置 public:void duplicateZeros(vectorint arr) {int cur 0;int dest -1;int n arr.size();while(dest n-1){if(arr[cur] 0)dest 2;elsedest;cur;}}for( ; cur 0; cur--){if(arr[cur])arr[dest--] arr[cur];else{arr[dest--] 0;arr[dest--] 0;}}}
};此时我们发现程序没过情况又没想全 class Solution {
public:void duplicateZeros(vectorint arr) {int cur 0;int dest -1;int n arr.size();while(cur n){if(arr[cur] 0)dest 2;elsedest;//防止越界if(dest n-1)break;cur;}//已经越界修正if(dest n){arr[n-1] 0;dest-2;cur--;}//从后向前复写for( ; cur 0; cur--){if(arr[cur])arr[dest--] arr[cur];else{arr[dest--] 0;arr[dest--] 0;}}}
};此时该代码地时间复杂度为O(N)空间复杂度为O(1)
4.快乐数 leetcode 202.快乐数
根据题意通过画图我们可以发现这就是一种循环往复地题目。此时我们就可以考虑双指针算法。 看到这个环形是不是会想起链表那里有一个判断环形链表的题目这两题很相似。
我们可以知道当重复执行x的时候数据会陷⼊到⼀个「循环」之中。 而「快慢指针」有⼀个特性就是在⼀个圆圈中快指针总是会追上慢指针的证明参考链表部分也就是说他们总会相遇在⼀个位置上。如果相遇位置的值是1那么这个数⼀定是快乐数如果相遇位置不是1的话那么就不是快乐数。
class Solution {
public:int Sum(int n){int sum 0;while(n){sum (n%10)*(n%10);n/10;}return sum;}bool isHappy(int n) {int slow n;int fast Sum(n);//让fast先走一步while(fast ! slow){slow Sum(slow);fast Sum(Sum(fast));}//当二者相等时若为1则是快乐数否则则不是return slow 1;}
};5.盛水最多的容器 leetcode 11.盛水最多的容器 首先我们要明白这个容器的容量是两个柱子之间的距离×两柱中较矮的一个 所以此题我们可以利用双指针寻找两柱中组成的容器中最大的一个即可。
方法一暴力求解
枚举出能构成的所有容器找出其中容积最大的值。 容器容积的计算⽅式 设两指针分别指向水槽板的最左端以及最右端此时容器的宽度为j - i 由于容器的⾼度由两板中的短板决定因此可得容积公式v (j - i) * min( height[i], height[j]
class Solution {
public:int maxArea(vectorint height) {int v 0;int n height.size();for(int i0; in; i){for(int j i1; jn; j){v max(v,((j-i)*min(height[i],height[j])));}}return v;}
};方法二左右指针
观察暴力解法以后我们可以发现一个规律 当使用最开始的左右区间算出来一个V1后我们没必要使用这两个区间中较小的一个去和其它数枚举因为枚举出来的结果一定是小于V1的。 所以可以按照以下步骤
先根据当前两柱计算V舍去两柱子中较小的一个根据新的柱子再计算体积tmpV max(V,tmp)
class Solution {
public:int maxArea(vectorint height) {int v 0;int left 0;int right height.size()-1;while(left right){//先计算当前两柱组成的大小int tmp (right-left) * min(height[left],height[right]);v max(v,tmp);if(height[left] height[right])left;elseright--;}return v;}
};6.有效三角形的个数 leetcode 611.有效三角形的个数
我们都知道组成三角形的条件是任意两边之和大于第三边。
方法一暴力求解
但是使用这个条件只想到一个暴力解法虽然说是暴⼒求解但是还是想优化⼀下 判断三⻆形的优化
如果能构成三⻆形需要满⾜任意两边之和要大于第三边。但是实际上只需让较小的两条边之和大于第三边即可。因此我们可以先将原数组排序然后从小到大枚举三元组一方面省去枚举的数量另一方面方便判断是否能构成三⻆形。
class Solution {
public:int triangleNumber(vectorint nums) {int n nums.size();sort(nums.begin(),nums.end());int count 0;for(int i0; in; i){for(int ji1; jn; j){for(int k j1; kn; k){if(nums[i] nums[j] nums[k])count;}}}return count;}
};方法二左右指针
将数组排序以后我们可以发现如果我们固定最右侧数为第三条边就只需使用左右指针找另外两条即可。 而且如果最左侧的数和右侧数加起来已经大于第三边了那么左侧和右侧之间的数一定大于第三边无需再枚举。 class Solution {
public:int triangleNumber(vectorint nums) {//先按照升序排序sort(nums.begin(),nums.end());int max nums.size() - 1;int ret 0;//至少要存在3条边while(max 2){int left 0;int right max - 1;while(left right){if(nums[left] nums[right] nums[max]){ret right - left;right--;}elseleft;}max--;}return ret;}
};7.两数之和 leetcode 179.和为target的两个数
由于该数组是升序的那么我们可以直接使用双指针计算左右指针之和
若和小于target左指针右移若和大于target右指针左移 class Solution {
public:vectorint twoSum(vectorint price, int target) {vectorint ret;int left 0;int right price.size()-1;while(left right){if(price[left]price[right] target)left;else if(price[left] price[right] target)right--;else{break;}}return {price[left],price[right]};}
};8.三数之和 leetcode 15.三数之和
这一题和上一题两数之和的解法非常类似唯一的不同点就是该题不允许有重复的三元组。
先排序固定一个数aim使用两数之和法找和为 - aim 的两个数即可 不漏 找到一个数以后left,right- -继续找 去重 left 与right均需要去重如果left后任然和之前的相同那就继续right同理仍需要 - -aim去重如果aim移动后仍然和上一个相等那就继续移动 class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ret;sort(nums.begin(),nums.end());int n nums.size();int i 0;while(i n){if(nums[i] 0)//若num对应的都已经大于0那么left 与right就更大和不可能为0了break;int aim -nums[i];//固定一个数取其相反数int left i1;int right n-1;while(left right){int sum nums[left] nums[right];if(sum aim)right--;else if(sum aim)left;else{ret.push_back({nums[i],nums[left],nums[right]});//避免遗漏继续找left;right--;//left,right去重while(left right nums[left] nums[left-1])left;while(left right nums[right] nums[right1])right--;}}i;while(i n nums[i] nums[i-1])i;}return ret;}
};9.四数之和 leetcode 18.四数之和 该题是在三数之和的基础之上的变形。
仍然还是采用上面的做法
先排序固定一个数a利用三数之和固定一个数b,找和为target - nums[a] - nums[b]的数 不漏 找到一个数以后leftright- -继续找 去重 left 与right均需要去重如果left后任然和之前的相同那就继续right同理仍需要 - -b去重如果b移动后仍然和上一个相等那就继续移动a去重如果a移动后仍然和上一个相等那就继续移动
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {sort(nums.begin(),nums.end());vectorvectorint ret;int n nums.size();int a 0;while(a n){int b a1;while(b n){long long aim (long long)target -nums[a] - nums[b];int left b1;int right n-1;while(left right){if(nums[left] nums[right] aim)left;else if(nums[left] nums[right] aim)right--;else{ret.push_back({nums[a],nums[b],nums[left],nums[right]});left;right--;while(left right nums[left] nums[left-1])left;while(left right nums[right] nums[right1])right--;}}b;while(b n nums[b] nums[b-1])b;}a;while(a n nums[a] nums[a-1])a;}return ret;}
};
