題目大意
編寫一個算法來判斷一個數(shù)是不是“快樂數(shù)”。
一個“快樂數(shù)”定義為：對于一個正整數(shù)，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和，然后重復這個過程直到這個數(shù)變?yōu)?1，也可能是無限循環(huán)但始終變不到 1拳恋。如果可以變?yōu)?1，那么這個數(shù)就是快樂數(shù)宴树。
示例:
輸入: 19
輸出: true
解釋:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
思路
如果不是快樂數(shù)晶疼，所得的數(shù)字會出現(xiàn)循環(huán)翠霍。第一個方法是用HashMap存儲已經(jīng)出現(xiàn)過的數(shù)字零如，這樣可以方便地找到循環(huán)。第二個方法是利用快慢指針完成一輪循環(huán)辕翰。
代碼一：HashMap
private int count(int n) {
int res = 0;
while(n>0)
{
res+= (n%10) * (n%10);
n/=10;
}
return res;
}
public boolean isHappy(int n) {
//<結(jié)果,原數(shù)>
boolean flag = false;
HashMap<Integer,Integer> map = new HashMap<>();
while(!flag) {
int res = count(n);
if(res == 1) return true;
if(map.containsKey(res)) return false;
else
{
map.put(res,n);
n = res;
}
}
return flag;
}
運行時間5ms壁榕，擊敗67.31%赎瞎。
代碼二：快慢指針
循環(huán)問題牌里，快指針一次走兩步，慢指針一次一步务甥， 達到一輪循環(huán)敞临。注意快指針的起點要比慢指針前态辛。
private int count(int n) {
int res = 0;
while(n>0)
{
res+= (n%10) * (n%10);
n/=10;
}
return res;
}
public boolean isHappy(int n) {
int fast = count(n), slow = n;
while(fast!=slow) {
slow = count(slow);
fast = count(fast);
fast = count(fast);
}
return slow == 1;
}
運行時間2ms奏黑，99.12%熟史。
