前言
雙指針
常見的雙指針有兩種形式，一種是對撞指針，?種是左右指針。
對撞指針：一般用于順序結(jié)構中，也稱左右指針。
- 對撞指針從兩端向中間移動。一個指針從最左端開始，另?個從最右端開始，然后逐漸往中間逼
近。 - 對撞指針的終止條件一般是兩個指針相遇或者錯開（也可能在循環(huán)內(nèi)部找到結(jié)果直接跳出循
環(huán)），也就是： -
- left == right （兩個指針指向同一個位置）
-
- left > right （兩個指針錯開）
快慢指針：又稱為龜兔賽跑算法，其基本思想就是使用兩個移動速度不同的指針在數(shù)組或鏈表等序列
結(jié)構上移動。
這種方法對于處理環(huán)形鏈表或數(shù)組非常有用。
其實不單單是環(huán)形鏈表或者是數(shù)組，如果我們要研究的問題出現(xiàn)循環(huán)往復的情況時，均可考慮使用快
慢指針的思想。
快慢指針的實現(xiàn)方式有很多種，最常用的?種就是：
- 在一次循環(huán)中，每次讓慢的指針向后移動一位，而快的指針往后移動兩位，實現(xiàn)一快一慢。
1. 快樂數(shù)（medium）
題目描述：
編寫一個算法來判斷一個數(shù) n 是不是快樂數(shù)。
「快樂數(shù)」 定義為：
對于一個正整數(shù)，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和。
然后重復這個過程直到這個數(shù)變?yōu)?1，也可能是 無限循環(huán) 但始終變不到 1。
如果這個過程 結(jié)果為 1，那么這個數(shù)就是快樂數(shù)。
如果 n 是 快樂數(shù) 就返回 true ；不是，則返回 false 。
示例 1：
輸入：n = 19
輸出：true
解釋：
12 + 92 = 82
82 + 22 = 68
62 + 82= 100
12 + 02+ 02 = 1
示例 2：
輸入：n = 2
輸出：false
提示：
1 <= n <= 231 - 1
2. 解法
思路：
可以把題目中的兩種情況當成一種情況來看，就是一直在死循環(huán)
- 對于情況一：?直在 1 中死循環(huán)
- 對于情況二：在歷史的數(shù)據(jù)中死循環(huán)，但始終變不到 1
為什么會死循環(huán)？
題目所給數(shù)據(jù)范圍是小于整型（int）的最大值 231-1=2147483647,這里我們們不難發(fā)現(xiàn)最大值的位數(shù)是 10，那么我們可以用一個十位數(shù)的最大值來變換，即 9999999999，那么它經(jīng)過變換得到的值就是 92 * 10 = 810 ，那么經(jīng)過所有變換的結(jié)果就會在區(qū)間 [1, 810] 之間；
根據(jù)【鴿巢原理】，?個數(shù)變化 811 次之內(nèi)，必然會在一個循環(huán)中有重復。
因此，可以?「快慢指針」來解決。
解題方法:
- ProductSum 函數(shù)：
- 這個函數(shù)計算一個整數(shù)的每個位上數(shù)字的平方和。
- 通過不斷地對整數(shù)取模 10 來獲取其最后一位數(shù)字，然后將其平方并累加到 sum 變量中。
- 每次迭代，整數(shù)都通過整除 10 來移除最后一位數(shù)字。
- 當整數(shù)變?yōu)?0 時，函數(shù)返回累加的和 sum。
- isHappy 函數(shù)：
- 使用“快慢指針”技術來檢測循環(huán)。
- slow 和 fast 初始時都指向 n。
- slow 每次移動一步，即計算當前數(shù)字的平方和。
- fast 每次移動兩步，即連續(xù)計算兩次平方和。
- 如果 n 是一個快樂數(shù)，slow 和 fast 最終都會達到 1。
- 如果 n 進入循環(huán)，slow 和 fast 會在循環(huán)中的某個點相遇（即它們的值相等）。
- 如果 slow 和 fast 相等且等于 1，則 n 是快樂數(shù)。
- 算法中使用了 do-while 循環(huán)而不是 while 循環(huán)，以確保至少執(zhí)行一次循環(huán)體（即至少計算一次ProductSum），即使 slow 和 fast 初始時就相等。
復雜度
時間復雜度: O(logN)
空間復雜度: O(1)
C++算法代碼：
class Solution {
public:
int ProductSum(int n)
{
int sum = 0;
while(n)
{
int temp = n % 10;
sum += temp*temp;
n /= 10;
}
return sum;
}
bool isHappy(int n) {
int slow = n,fast = n;
// 快慢指針，找環(huán)的相遇位置
do
{
slow = ProductSum(slow);
fast = ProductSum(ProductSum(fast));
}while(slow != fast);
// 如果相遇時是 1 就是快樂數(shù)
return slow == 1;
}
};
java算法代碼：
class Solution
{
public int bitSum(int n) // 返回 n 這個數(shù)每?位上的平?和
{
int sum = 0;
while (n != 0)
{
int t = n % 10;
sum += t * t;
n /= 10;
}
return sum;
}
public boolean isHappy(int n)
{
int slow = n, fast = bitSum(n);
while (slow != fast)
{
slow = bitSum(slow);
fast = bitSum(bitSum(fast));
}
return slow == 1;
}
}
3. 盛水最多的容器（medium）
題目描述：
給定一個長度為 n 的整數(shù)數(shù)組 height 。有 n 條垂線，第 i 條線的兩個端點是 (i, 0) 和 (i, height[i]) 。
找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。
返回容器可以儲存的最大水量。
說明：你不能傾斜容器。
示例 1：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
解釋：圖中垂直線代表輸入數(shù)組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。
示例 2：
輸入：height = [1,1]
輸出：1
提示：
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
4. 解法
解法一（暴力求解)(會超時):
算法思路:
枚舉出能構成的所有容器，找出其中容積最大的值。
容器容積的計算方式:
設兩指針 i , j，分別指向水槽板的最左端以及最右端，此時容器的寬度為j - i
容器的高度由兩板中的短板決定，因此可得容積公式︰v = (j - i) * min(height[il, height[j])
算法代碼：
class Solution {
public:
int maxArea(vector<int>& height) {
int n = height.size();
int ret = 0;
// 兩層 for 枚舉出所有可能出現(xiàn)的情況
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// 計算容積，找出最?的那?個
ret = max(ret, min(height[i], height[j]) * (j - i));
}
}
return ret;
}
};
解法二（對撞指針）：
算法思路：
設兩個指針 left , right 分別指向容器的左右兩個端點,此時容器的容積 : v = (right - left) * min( height[right], height[left])
容器的左邊界為height[left],右邊界為 height[right] 。
為了方便敘述,我們假設「左邊邊界」小于「右邊邊界」. 如果此時我們固定一個邊界,改變另一個邊界,水的容積會有如下變化形式：
- 容器的寬度?定變小
- 由于左邊界較小,決定了?的?度.如果改變左邊界,新的水面高度不確定,但是?定不會超過右邊的柱子高度,因此容器的容積可能會增大.
- 如果改變右邊界,無論右邊界移動到哪里,新的水面的高度?定不會超過左邊界,也就是不會超過現(xiàn)在的水面高度,但是由于容器的寬度減小,因此容器的容積?定會變小的.
- 由此可見,左邊界和其余邊界的組合情況都可以舍去.所以我們可以 left++ 跳過這個邊界,繼續(xù)去判斷下?個左右邊界.
當我們不斷重復上述過程,每次都可以舍去?量不必要的枚舉過程,直到 left 與 right 相 遇.期間產(chǎn)生的所有的容積里面的最大值,就是最終答案.
C++ 算法代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-842776.html
class Solution
{
public:
int maxArea(vector<int>& height)
{
int left = 0, right = height.size() - 1, ret = 0;
while (left < right)
{
int v = min(height[left], height[right]) * (right - left);
ret = max(ret, v);
// 移動指針
if (height[left] < height[right]) left++;
else right--;
}
return ret;
}
};
Java 算法代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-842776.html
class Solution
{
public int maxArea(int[] height)
{
int left = 0, right = height.length - 1, ret = 0;
while (left < right)
{
int v = Math.min(height[left], height[right]) * (right - left);
ret = Math.max(ret, v);
if (height[left] < height[right]) left++;
else right--;
}
return ret;
}
}
到了這里，關于【算法專題--雙指針算法】leecode-202. 快樂數(shù)(medium)、leecode-11. 盛最多水的容器(medium)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
