leetcode 202. 快乐数

leetcode 202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

分析

题⽬告诉我们，，死的⽅式有两种： ▪ 情况⼀：⼀直在 1 中死循环，即 1 -> 1 -> 1 -> 1...... ▪ 情况⼆：在历史的数据中死循环，但始终变不到 1 由于上述两种情况只会出现⼀种，因此，只要我们能确定循环是在「情况⼀」中进⾏，还是在「情况⼆」中进⾏，就能得到结果。

简单证明： a. 经过⼀次变化之后的最⼤值 9^2 * 10 = 810 ( 2^31-1=2147483647 。选⼀个更⼤的最⼤ 9999999999 )，也就是变化的区间在 [1, 810] 之间； b. 根据「鸽巢原理」，⼀个数变化 811 次之后，必然会形成⼀个循环； c. 因此，变化的过程最终会⾛到⼀个圈⾥⾯，因此可以⽤「快慢指针」来解决。

方法一：快慢指针

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

    int getSum(int num) {   //获取 数值各个位上的数字的平方和
        int sum = 0;
        while(num) {
            int x = num % 10;
            sum += x * x;
            num /= 10;
        }
        return sum;
    }
};

方法二：哈希表

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1) {
            n = getSum(n);
            if(n == 1) {	//⼀直在 1 中死循环
                return true;
            }
            if(set.count(n)) {	//在历史的数据中死循环
                return false;
            }
            set.insert(n);
        }
    }

    int getSum(int num) {
        int sum = 0;
        while(num) {
            int x = num % 10;
            sum += x * x;
            num /= 10;
        }
        return sum;
    }
};