0x01.に質問

アルゴリズムを記述して,1つの数nが快楽数であるか否かを判断する.
「快楽数」は、正の整数に対して、その数を各位置の数字の二乗和に置き換えるたびに、この数が1になるまで繰り返し、無限ループである可能性がありますが、常に1にならないまで繰り返します.1に変えることができれば、この数が快楽数です.nが快楽数であればTrueに戻る.いいえ、Falseを返します.
例:
入力:19出力:true解釈:1^2+9^2=82 8^2+2^2=68 6^2+8^2=100 1^2+0^2+0^2+0^2=1

public boolean isHappy(int n)

0x02.解決策

問題を読んで、問題の要点を発見します:

は、1つの数を判断し、一連の「その数を各位置の数字の二乗和に置き換える」操作を経て、1になることができるかどうかを判断する.

問題は実は簡単で、この過程の変換を絶えずシミュレートすればいいだけですが、中にはいくつかの問題があります.
もしそれが永遠に1にならないならば、それはどのように変換しますか?
1つの考えは、ますます大きくなり、ますます大きくなり、最後には全体の範囲を超えますが、具体的な例を見てみましょう.

の3桁がこの操作で得られる最大の数字は999—>243で、4桁は9999—>324です.

さらに全体型に近い大数999999999999—>1053を見てみましょう.

実際には,整数型を超える範囲ではなく,小さな範囲で変換されることが分かったが,この小さな範囲での変換は2つのケースしかない.

は最後に1になりました.

は絶えず循環している.

1つ目は私たちが必要としていることです.私たちは循環が現れたかどうかを判断するだけでいいです.もし循環が現れて、まだ1が得られていないなら、説明してから1を得ることはできません.
ループが発生したかどうかをどのように判断しますか?簡単で、今回得られた数がすでに現れたかどうかを判断するだけでいい.では、ハッシュテーブルを使用して、毎回得られた数を格納することができます.次に得られた数がすでに現れた場合、falseに直接戻ります.

class Solution {
    private int next(int n){
        int ans=0;
        while(n>0){
            int d=n%10;
            n/=10;
            ans+=d*d;
        }
        return ans;
    }
    public boolean isHappy(int n) {
        Set<Integer> hash=new HashSet<>();
        while(n!=1&&!hash.contains(n)){
            hash.add(n);
            n=next(n);
        }
        return n==1;
    }
}

この方法は最も簡単で,最も直接的である.
実は、ループが発生しているかどうかを判断するには、チェーンテーブルがループになっているかどうかを判断するのと同じ方法があります.

0x03.解決コード-スナップポインタ

class Solution {
    private int next(int n){
        int ans=0;
        while(n>0){
            int d=n%10;
            n/=10;
            ans+=d*d;
        }
        return ans;
    }
    public boolean isHappy(int n) {
        int slow=n;
        int fast=next(n);
        while(fast!=1&&fast!=slow){
            slow=next(slow);
            fast=next(next(fast));
        }
        return fast==1;
    }
}

ATFWUS --Writing By 2020–04-30