柚子快報(bào)激活碼778899分享：c++ 算法專(zhuān)題一: 雙指針
柚子快報(bào)激活碼778899分享：c++ 算法專(zhuān)題一: 雙指針
目錄
前言1. 移動(dòng)零（easy）2. 復(fù)寫(xiě)零（easy）3. 快樂(lè)數(shù)（medium）4. 盛水最多的容器（medium）5. 有效三角形的個(gè)數(shù)（medium）6. 和為 s 的兩個(gè)數(shù)字（easy）7. 三數(shù)之和（medium）8. 四數(shù)之和（medium)
前言
常見(jiàn)的雙指針有兩種形式，一種是對(duì)撞指針，一種是左右指針。
1. 對(duì)撞指針: ?般用于順序結(jié)構(gòu)中，也稱左右指針。
對(duì)撞指針從兩端向中間移動(dòng)。?個(gè)指針從最左端開(kāi)始，另?個(gè)從最右端開(kāi)始，然后逐漸往中間逼近。對(duì)撞指針的終止條件?般是兩個(gè)指針相遇或者錯(cuò)開(kāi)（也可能在循環(huán)內(nèi)部找到結(jié)果直接跳出循環(huán)），也就是： ? left == right （兩個(gè)指針指向同?個(gè)位置） ? left > right （兩個(gè)指針錯(cuò)開(kāi)）
2. 快慢指針：又稱為龜兔賽跑算法，其基本思想就是使用兩個(gè)移動(dòng)速度不同的指針在數(shù)組或鏈表等序列結(jié)構(gòu)上移動(dòng)。
這種方法對(duì)于處理環(huán)形鏈表或數(shù)組非常有用。
其實(shí)不單單是環(huán)形鏈表或者是數(shù)組，如果我們要研究的問(wèn)題出現(xiàn)循環(huán)往復(fù)的情況時(shí)，均可考慮使用快慢指針的思想。
快慢指針的實(shí)現(xiàn)方式有很多種，最常用的?種就是： ? 在一次循環(huán)中，每次讓慢的指針向后移動(dòng)?位，而快的指針往后移動(dòng)兩位，實(shí)現(xiàn)一快一慢。
1. 移動(dòng)零（easy）
題目鏈接:移動(dòng)零
思想
在本題中，我們可以用一個(gè) cur 指針來(lái)掃描整個(gè)數(shù)組，另一個(gè) dest 指針用來(lái)記錄非零數(shù)序列的最后一個(gè)位置。根據(jù) cur 在掃描的過(guò)程中，遇到的不同情況，分類(lèi)處理，實(shí)現(xiàn)數(shù)組的劃分。
class Solution {
public:
void moveZeroes(vector
for(int cur = 0, dest = -1;cur { if(nums[cur]!=0) { ++dest; swap(nums[dest],nums[cur]); } } } }; 2. 復(fù)寫(xiě)零（easy） 題目鏈接: 復(fù)寫(xiě)零 算法思路 如果從前向后進(jìn)行原地復(fù)寫(xiě)操作的話,由于0的出現(xiàn)會(huì)復(fù)寫(xiě)兩次,導(dǎo)致沒(méi)有復(fù)寫(xiě)的數(shù)被覆蓋掉,因此我們選擇從后往前的復(fù)寫(xiě)策略,但是從后往前復(fù)寫(xiě)的時(shí)候,我們需要找到最后一個(gè)復(fù)寫(xiě)的數(shù),因此我們的大體流程分為兩步: 先找到最后一個(gè)復(fù)寫(xiě)的數(shù);然后從后往前進(jìn)行復(fù)寫(xiě)操作. class Solution { public: void duplicateZeros(vector int cur = 0, dest = -1; while(cur < arr.size()) { if(arr[cur]) ++dest; else dest+=2; if(dest >= arr.size()-1) break; ++cur; } if(dest == arr.size()) { dest--; arr[dest--] = 0; cur--; } while(cur>=0) { if(arr[cur]) { arr[dest--] = arr[cur--]; }else { arr[dest--] = 0; arr[dest--] = 0; cur--; } } } }; 3. 快樂(lè)數(shù)（medium） 題目鏈接: 快樂(lè)數(shù) 算法思路 根據(jù)分析我們可以知道, 當(dāng)重復(fù)執(zhí)行x的時(shí)候, 數(shù)據(jù)就會(huì)陷入到一個(gè)循環(huán)中, 而快慢指針有一個(gè)特性,就是在一個(gè)圓圈中, 快指針總是會(huì)追上慢指針的,也就是說(shuō)他們會(huì)相遇在一個(gè)位置上, 如果相遇位置的值是1, 那么這個(gè)數(shù)一定是快樂(lè)數(shù), 如果相遇的位置不是1的話, 那么這個(gè)數(shù)就不是快樂(lè)數(shù). class Solution { public: int mutify(int n) { int ret = 0; while(n) { int ge = n % 10; ret += ge*ge; n/=10; } return ret; } bool isHappy(int n) { int fast = mutify(n), slow = n; while(fast != slow) { fast = mutify(mutify(fast)); slow = mutify(slow); } return fast==1; } }; 4. 盛水最多的容器（medium） 題目鏈接: 盛水最多的容器 算法思路 設(shè)置兩個(gè)指針left,right分別指向容器的左右兩個(gè)端點(diǎn),此時(shí)容器的容積v = (right - left) * min(hegiht[right] , height[left]). 容器的左邊界為height[left], 右邊界為height[right].如果此時(shí)我們固定一個(gè)邊界, 改變另一個(gè)邊界,水的容積會(huì)有如下變化形式: 容器的寬度一定變小.由于左邊界較小, 決定了水的高度,如果改變左邊界,新的水面高度不確定,但是一定不會(huì)超過(guò)右邊的柱子高度,因此容器的容積可能會(huì)增大.如果改變右邊界,無(wú)論右邊界移動(dòng)到哪里,新的水面的高度一定不會(huì)超過(guò)左邊界,也就是不會(huì)超過(guò)現(xiàn)在的水面高度,但是由于容器的寬度減小,因此容器的容積一定會(huì)變小. 由此我們可以left++跳過(guò),舍棄左邊界和它的組合情況,繼續(xù)下一個(gè)判斷, 不斷重復(fù), 就可以舍去大量不必要的枚舉過(guò)程,直到left和right相遇. class Solution { public: int maxArea(vector int left = 0, right = height.size()-1, ret = 0; while(left < right) { int v = min(height[left],height[right]) * (right - left); ret = max(v,ret); if(height[left] left++; else right--; } return ret; } }; 5. 有效三角形的個(gè)數(shù)（medium） 題目鏈接: 有效的三角形個(gè)數(shù) 算法思路 class Solution { public: int triangleNumber(vector sort(nums.begin(),nums.end()); int ret = 0; for(int i = nums.size()-1;i>=2;i--) { int left = 0,right = i-1; while(left { if(nums[left]+nums[right] <= nums[i]) { left++; } else { ret+=right - left; right--; } } } return ret; } }; 6. 和為 s 的兩個(gè)數(shù)字（easy） 題目鏈接: 查找總價(jià)格為目標(biāo)值的兩個(gè)商品 算法思路 class Solution { public: vector int left = 0, right = price.size()-1; while(left < right) { if(price[left]+price[right] > target) { right--; } else if(price[left]+price[right] { left++; } else { return {price[left],price[right]}; } } return {-1,-1}; } }; 7. 三數(shù)之和（medium） 題目鏈接: 三數(shù)之和 算法思路 class Solution { public: vector sort(nums.begin(),nums.end()); vector int n = nums.size(); for(int i = 0; i { int target = -nums[i]; int left = i+1,right = n-1; while(left { int sum = nums[left]+nums[right]; if(sum < target) left++; else if(sum > target) right--; else { vv.push_back({nums[left],nums[right],nums[i]}); left++,right--; while(left while(left } } i++; while(i } return vv; } }; 8. 四數(shù)之和（medium) 題目鏈接: 四數(shù)之和 算法思路 class Solution { public: vector sort(nums.begin(),nums.end()); vector int n = nums.size(); for(int i = 0; i < n ;) { for(int j = i+1;j { long long a = (long long)target - nums[i] - nums[j]; int left = j+1,right =n-1; while(left { int sum = nums[left] + nums[right]; if(sum else if(sum>a) right--; else { vv.push_back({nums[left],nums[right],nums[i],nums[j]}); left++,right--; //去重1 while(left while(left } } j++; //去重2 while(j } i++; while(i } return vv; } }; 完 柚子快報(bào)激活碼778899分享：c++ 算法專(zhuān)題一: 雙指針 文章來(lái)源
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
Costco科斯特優(yōu)選
