移動零問題

https://leetcode.cn/problems/move-zeroes/submissions/

1.題目解析

必須在原數組進行修改，不可以新建一個數組

非零元素相對順序不變

2.算法原理

【數組劃分】【數組分塊】

這一類題會給我們一個數組，讓我們劃分區間，比如說這題，最后會劃分為兩個區間，前一段是非零元素，后一段是零，一般我們只要看到這樣的特性，腦海里就應該想到用雙指針算法來解決（利用數組下標充當指針）

定義兩個指針：

兩個指針的作用：

cur ：從左往后掃描數組，遍歷數組。

dest : 已處理的區間內，非零元素的最后一個位置

如何做到：

cur從前往后遍歷的過程中：

1.遇到0元素：cur++；

2.遇到非零元素：

交換

相關知識：快速排序

雙指針的思想其實就是快排的核心思想

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]);}}}
};

?

復寫零問題

https://leetcode.cn/problems/duplicate-zeros/

1.題目解析

長度固定：不能越界

在原始數組進行操作

2.算法原理：

解法：雙指針算法 先根據異地操作，然后優化成雙指針下的“就地操作”

根據異地操作，得出先模擬一遍復寫的操作，然后從后向前進行覆蓋，從前往后會發生覆蓋多的值。

總結：

1.先找到最后一個復寫的數

用雙指針模擬一遍 cur=0，dest=-1；

先判斷cur位置的值，決定dest向后移動幾步，判斷dest是否已經到了最后的位置，cur++；

2.從后向前進行操作

特例：數組越界

所以要加上一個步驟：處理越界

3.解題代碼：

class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur=0,dest=-1,n=arr.size();//先模擬while(cur<n){if(arr[cur]) dest++;else         dest+=2;if(dest>=n-1) break;cur++;}//判斷邊界if(dest==n){arr[n-1]=0;dest-=2;cur--;}//從后向前while(cur>=0){if(arr[cur]==0){arr[dest--]=0;arr[dest--]=0;cur--;}else arr[dest--]=arr[cur--];}}
};

?

快樂數問題

https://leetcode.cn/problems/happy-number/

1.題目解析

一直替換

分為兩種情況：

變成一

無限循環

兩種情況

2.算法原理

有沒有發現，一直平方到最后，一定會成環

解法：快慢雙指針

1.定義快慢雙指針

2.慢指針每次向后移動一步，快指針每次走兩步

3.判斷相遇的時候的值即可

雙指針只是一種思想，不需要一定定義雙指針，在這個題中快指針就是平方兩次，慢指針平方一次

為什么會一定會重復

證明方法：

鴿巢原理（抽屜原理）：

n個巢穴 n+1個鴿子-->至少有一個巢穴里面的鴿子數量大于1

3.解題代碼

class Solution {
public:int Sum(int n){int sum=0;while(n){int g=n%10;sum+=g*g;n/=10;}return sum;}bool isHappy(int n) {int slow=n,fast=Sum(n);while(slow!=fast){slow=Sum(slow);fast=Sum(Sum(fast));}return slow==1;}
};

盛水最多的容器

https://leetcode.cn/problems/container-with-most-water/

1.題目解析

只能水平放置，也就是找最大的矩形

2.算法原理

解法一：暴力枚舉：雙重循環

優點：想法簡單

缺點：時間復雜度過高

解法二：頭尾雙指針：

v=h*w

寬度一直在減小，而高度有兩種情況，變大或變小，在寬度一直在變小的情況下，我們高度必須選擇更高的

3.解題代碼

class Solution {
public:int maxArea(vector<int>& height) {int left=0,right=height.size()-1;int v=-1;while(left<right){int tv=min(height[left],height[right])*(right-left);v=max(tv,v);if(height[left]>height[right])  right--;else                            left++;}return v;}
};

和為s的兩個數字問題

1.題目解析

有序數組

隨意輸出一對

2.算法原理

解法一：暴力枚舉 雙重循環 n^2復雜度

解法二：利用單調性，使用雙指針算法解決問題

首尾相加

判斷數值，如果大于目標值，right--反之left++，因為數組是有序的

3.解題代碼

vector<int> twosum(vector &nums,int t)
{int left =0,right=nums.size()-1;while(left<right){int sum=nums[left]+nums[right];if(sum>t) right--;else if(sum<t) left++;else return {num[left],nums[right]};}//照顧編譯器return {-1,-1};
}

有效三角形個數

https://leetcode.cn/problems/valid-triangle-number/

1.題目解析

相同的不算一個

2.講解算法原理

補充數學知識：給我們三個數，判斷是否能構成三角形

我們僅需要一個公式，就能判斷是否能構成三角形：

如果我們已經知道三個數的大小順序，只需要a+b>c（c是最大的數）

優化：先對整個數組排序

解法一：暴力枚舉

for(i=0;i<n;i++)

for(j=i+1;j<n;j++)for(k=j+1;k<n;k++)check(i,j,k)

解法二：利用單調性，使用雙指針算法來解決問題

①先固定最大的數

②在最大的數的左區間里，使用雙指針算法，快速統計

3.解題代碼

class Solution {
public:int triangleNumber(vector<int>& nums) {int n=nums.size();int ret=0;sort(nums.begin(),nums.end());for(int i=n-1;i>=2;i--){int left=0,right=i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){ret+=right-left;right--;}else{left++;}}}return ret;}
};

三數之和問題

https://leetcode.cn/problems/3sum/

1.題目解析

三個數的下標不同

答案不可重復（去重）

有可能沒有答案

2.算法原理

解法一：先排序+暴力枚舉+利用set去重o(n^3)

解法二：排序+雙指針：

找到右邊區間兩數之和為左邊數字的相反即可

1.排序

2.固定一個數a

3.在該數后邊的區間，利用雙指針的算法，快速找到和為-a的兩個數

處理細節問題：

1.去重：

找到一種結果之后，left和right指針要跳過重復元素。

當使用完一次雙指針算法之后，i也要跳過重復元素（避免越界）

2.不漏：

找到一種結果后，不要“停”，縮小區間，繼續尋找

3。解題代碼

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> ret;int n=nums.size();for(int i=0;i<n;){if(nums[i]>0) break;int left=i+1,right=n-1,t=-nums[i];while(left<right){int sum=nums[left]+nums[right];if(sum<t) left++;else if(sum>t) 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--;}}i++;while(i<n&&nums[i]==nums[i-1]) i++;}return ret;}
};

四數之和

https://leetcode.cn/problems/4sum/

1.題目解析

三數之和的進階版本，基本算法原理和三數之和大差不差

2.算法原理

解法一：排序＋暴力枚舉

四個循環，絕對超時

解法二：排序＋雙指針

1.依次固定一個數i

2.在i后面的區間內，利用三數之和找到三個數，讓他們三個的和等于target-i；

{

1.依次固定一個j

2.在j后邊的區間里，利用“雙指針找到兩個數，使得這兩個數之和等于target-i-j”

}

處理細節問題：

不重，不漏

3.解題代碼：

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;//1.排序sort(nums.begin(),nums.end());//2.利用雙指針解決問題int n=nums.size();for(int i=0;i<n;){//利用三數之和for(int j=i+1;j<n;){int left=j+1,right=n-1;long long aim=(long long)target-nums[i]-nums[j];while(left<right){int sum=nums[left]+nums[right];if(sum<aim) left++;else if(sum>aim) right--;else{ret.push_back({nums[i],nums[j],nums[left++],nums[right--]});//去重1while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}}//去重2j++;while(j<n&&nums[j]==nums[j-1]) j++;			}//去重3i++;while(i<n&&nums[i]==nums[i-1]) i++;}  return ret;}
};

覺得有幫助的慣用老爺麻煩點點關注！！！