題號202
編寫一個算法來判斷一個數?n?是不是快樂數。
「快樂數」?定義為：
- 對于一個正整數，每一次將該數替換為它每個位置上的數字的平方和。
- 然后重復這個過程直到這個數變為 1，也可能是?無限循環?但始終變不到 1。
- 如果這個過程?結果為?1，那么這個數就是快樂數。
如果?n?是?快樂數?就返回?true?；不是，則返回?false?。
我的失敗寫法
/*class Solution {public boolean isHappy(int n) {String numstr=String.valueOf(n);//用自帶函數將其轉換為字符串int ans=0;while(ans!=1){ans=0;for(int i=0;i<numstr.length();i++){ans+=(numstr.charAt(i)-'0')*(numstr.charAt(i)-'0');}numstr=String.valueOf(ans);if(ans==1)return true;}return false;//缺點是遇到循環無法跳出}
}*/改進后
class Solution {public boolean isHappy(int n) {String numstr=String.valueOf(n);int ans=0;Set<Integer> set=new HashSet<Integer>();//用哈希集合來記錄while(ans!=1){ans=0;for(int i=0;i<numstr.length();i++){ans+=(numstr.charAt(i)-'0')*(numstr.charAt(i)-'0');}numstr=String.valueOf(ans);if(!set.contains(ans))//如果集合中不存在該數，則添加set.add(ans);else//若存在，說明已經有循環，則為無限循環，返回falsereturn false; }return true;}
}改進的關鍵在于，知道如何判斷出現了無限循環：即產生了已經出現過的數字
再改進版
class Solution {public boolean isHappy(int n) { Set<Integer> set=new HashSet<Integer>();while(getResult(n)!=1){if(set.contains(getResult(n)))return false;else{set.add(getResult(n));n=getResult(n);}}return true;}public int getResult(int n){int sum=0;while(n!=0){int a=n%10;//對10取模 得出個位的數字n/=10;//n除以10 自動更新為去除掉個位sum+=a*a;}return sum;}
}此時改進了對于求每個數字平方和的算法：不必每一位均記錄下來，數位分離的方法，可采用先對10求模再除以10更新自身的方法。
快慢指針法
class Solution {public boolean isHappy(int n) {int slow=n;int fast=getNext(n);while(fast!=1){slow=getNext(slow);fast=getNext(getNext(fast));if(slow==fast)return false;}return true;}public int getNext(int n){int sum=0;while(n!=0){int a=n%10;//對10取模 得出個位的數字n/=10;//n除以10 自動更新為去除掉個位sum+=a*a;}return sum;}
}即在上一個解法中搞清楚這題關鍵是要判斷有沒有循環后，我們的任務就成了熟悉的判斷是否有循環，DAY 31 leetcode 142--鏈表.環形鏈表-CSDN博客在這一篇中我們已經學習過在鏈表里面處理循環問題，而判斷是否有環更簡單，只需要fast指針和slow指針相遇即可（fast一次走兩步，slow一次走一步）而此題中，通過反復調用?getNext(n)?得到的鏈是一個隱式的鏈表。可以使用這種方法。
)
