題目1：快樂數

我們先來結合實例看一下判斷快樂數的整個過程：

結合題目可以知道，如果一個數是快樂數，那么這個數最終就會變成1，如果一個數不是快樂數，那么變化序列最終就會陷入循環。想一下，如果題目沒有告訴我們“如果一個數不是快樂數，最后會陷入死循環”這句話，我們應該如何來證明這個觀點？

這里就要用到小學學過的“鴿巢原理”（抽屜原理）來進行簡單的證明。

鴿巢原理：如果一共有n個鴿巢，有n+1只鴿子，那么一定存在至少一個鴿巢，這個鴿巢里面的格子數大于1.

我們知道n是一個整型類型而且n>0，那么n的取值范圍就在1~2^31-1,而2^31-1=2147483647，這個數一定小于9999999999，如果非快樂數的變化不是循環的，那么總有一次會變成最大的那一個數2147483647，而這個數小于9999999999，在經過題目所說的變化以后，一定會變成小于(9^2)*10=810的數x，所以這個數經過相應的又會進入新一輪的循環，所以我們一開始的假設（即非快樂數的變化不是循環的）是錯誤的，所以一個非快樂數，他經過相應的變化以后會進入一個循環的序列。

結合上圖和解釋，我們可以將序列的變化抽象為下面的圖：

如果看過數據結構之鏈表篇的兄弟對這一張圖一定很熟悉，這就是我們之前做的帶環的鏈表的那一道題（這道題可以參考：https://blog.csdn.net/pusue_the_sun/article/details/150438603?fromshare=blogdetail&sharetype=blogdetail&sharerId=150438603&sharerefer=PC&sharesource=pusue_the_sun&sharefrom=from_link）

在那一道題中我們所使用的思路是前后指針，同理這一道題我們也可以使用前后指針的思想。

我們先定義一個快指針和慢指針，初始時慢指針的值就等于n，而快指針的值就等于n經過一次變化以后所得到的值。然后每次讓慢指針經歷一次變化，快指針經過兩次變化，最后快慢指針一定都會進入成環的那一部分，那么最終快慢指針就一定會相遇，即它們兩個的值一定會相同（這個結論的分析過程見帶環的鏈表那一道題），接下來我們只需判斷當它們兩的值相同時，slow的值是1還是其他值，如果是1，那么就代表n是快樂數，反之就不是快樂數。

//快慢指針
//將一個數替換為他們個位置上的數字的平方和
int Func(int n)
{int m=n;int sum=0;while(m){int x=m%10;sum+=x*x;m/=10;}return sum;
}
bool isHappy(int n) 
{int slow=n;int fast=Func(n);while(fast!=slow){slow=Func(slow);fast=Func(fast);fast=Func(fast);}return slow==1;
}

題目2：盛最多水的容器

方法一：暴力求解。這道題我們當然可以使用雙層循環求任意兩個區間中容器的體積，然后比較得到最大的容積。但是，這個思路雖然好想，時間復雜度卻太高了，無法通過題解。

方法二：雙指針法。我們知道，對于任意一個區間，容器的體積是由寬度和高度兩部分決定的，根據木桶效應，一個區間容器的高度有較小的高度決定。假設我們一開始將寬度拉到最大，即包含整個區間（區間范圍是? [0,heightsize-1]? ）,算出這一部分的體積，然后再縮小寬度，依次去計算對應區間的體積并比較，然后就可以得到最大體積。我們應該如何縮小寬度才能達到找到最大體積的目的呢？我們知道，體積是由寬度和高度共同決定的，當我們縮小寬度時，如果還想讓體積變大，就一定要讓高度變大，所以對于區間的兩個端點，我們需要舍棄對應高度較小的那一個端點來縮小寬度。

結合上述思路我們來整理出這道題的算法步驟：

1.定義兩個指針right和left分別指向數組的最右邊和最左邊

2.計算left到right區間的容積

3.縮小區間范圍，如果left對應的高度小于right對應的高度，就讓left++；反之就讓right--

4.通過比較更新最大容積

現在我們就可以來寫代碼啦：

int maxArea(int* height, int heightSize) 
{int max=0;int left=0,right=heightSize-1;while(left<right){int h=height[left]<height[right]?height[left]:height[right];int v=h*(right-left);if(height[left]<height[right]){left++;}else{right--;}if(v>max){max=v;}}return max;
}

小結：這一小節我們主要通過兩個算法題對應用雙指針的解題思路進行了講解。小伙伴們一定要自己在草稿紙或者電腦上多畫一下圖以深入理解算法的思想。

歡迎小伙伴們在評論區提出問題和討論！！！