快樂數

• 方法一：用哈希表來記錄
• 方法二、雙指針

題目：編寫一個算法來判斷一個數 n 是不是快樂數。

「快樂數」定義為：

對于一個正整數，每一次將該數替換為它每個位置上的數字的平方和。
然后重復這個過程直到這個數變為 1，也可能是 無限循環 但始終變不到 1。
如果 可以變為 1，那么這個數就是快樂數。
如果 n 是快樂數就返回 true ；不是，則返回 false 。

思路：如果數是不快樂的數，那么就會進入循環當中。所以我們記錄每一個數，如果有重復那么就返回FALSE；

性質：不是快樂數的數稱為不快樂數（unhappy number），所有不快樂數的數位平方和計算，最後都會進入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循環中

方法一：用哈希表來記錄

代碼：

bool isHappy(int n) {long long t = n;unordered_map<int,int>key;key.insert(pair<int,int>(n,1));while(1){t = 0;while(n) //分解位數{int temp = n%10;n/=10;t += temp * temp;}n= t;if(n==1){return true;}if(key.count(t))return false;key.insert(pair<int,int>(t,1));} } 也可以用 vector 代碼： bool isHappy(int n) {long long t = n;vector<int>cnt;cnt.push_back(n);while(1){t = 0;while(n){int temp = n%10;n/=10;t += temp * temp;}n= t;if(n==1){return true;}if(find(cnt.begin(), cnt.end(), t) != cnt.end())return false;cnt.push_back(t);}}

方法二、雙指針

方法二：雙指針 /參考英文網站熱評第一。這題可以用快慢指針的思想去做，有點類似于檢測是否為環形鏈表那道題//如果給定的數字最后會一直循環重復，那么快的指針（值）一定會追上慢的指針（值），也就是//兩者一定會相等。如果沒有循環重復，那么最后快慢指針也會相等，且都等于1。 代碼； public boolean isHappy(int n) {int fast=n;int slow=n;do{slow=squareSum(slow);fast=squareSum(fast);fast=squareSum(fast);}while(slow!=fast);if(fast==1)return true;else return false;}private int squareSum(int m){int squaresum=0;while(m!=0){squaresum+=(m%10)*(m%10);m/=10;}return squaresum; }

總結

以上是生活随笔為你收集整理的快乐数（双指针，哈希表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。