Math-Easy

Abstract：数论相关，说是数论其实也不是数论，简单逻辑判断而已

202. Happy Number

解法一：std::unordered_set

如果不是1，转换成下一个数这好办，问题是什么数永远不可能是happy number呢，当然是无限循环的时候，什么时候无限循环，如果出现了以前出现过的数，那么我们判断是循环，这也是最简单的一种做法

class Solution {
public:
    bool isHappy(int n) {
        // if(n == 0) return false;
        unordered_set<int> set;
        while(n != 1){
            if(set.find(n) != set.end())
                return false;
            set.insert(n);
            int sum = 0;
            while(n > 0){
                int val = n % 10;
                sum += val * val;
                n /= 10;
            }
            n = sum;
        }
        return true;
    }
};

解法二：快慢指针

链表题里就是这么玩的，在这里当然也可以

• 如果存在循环，那么说明存在环，也就是快指针一定会追上慢指针
• 如果不存在循环，那么最后slow 和 fast 都会变成1同样跳出循环

最后如果slow == fast == 1就是happy number，否则不是

class Solution {
public:
    bool isHappy(int n) {
        int slow = n, fast = n;
        do {
            slow = getNext(slow);
            fast = getNext(fast);
            fast = getNext(fast);
        } while(slow != fast);
        return slow == 1;
    }

    int getNext(int n){
        int sum = 0;
        while(n > 0){
            int val = n % 10;
            sum += val * val;
            n /= 10;
        }
        return sum;
    }
};