LeetCode 202: 快乐数

[guodongxiaren]

https://leetcode-cn.com/problems/happy-number

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

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

如果 n 是快乐数就返回 True ；不是，则返回 False 。

 

示例：

输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

[guodongxiaren]

最直观的写法，动用了STL容器unordered_set。

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

    }
};

[guodongxiaren]

如果不用容器的话，可以用快慢指针的思路！ 这个比用容器还快！

class Solution {
public:
    bool isHappy(int n) {
        auto square = [](int n) {
            int res = 0;
            while (n) {
                res += (n%10) * (n%10);
                n /= 10;
            }
            return res;
        };
        int slow = n;
        int fast = n;
        do {
            slow = square(slow);
            fast = square(square(fast));
        } while (slow != fast);

        return slow == 1;
    }
};

小技巧

如果一个循环过程，第一次比较特殊，而后面不特殊，则可以使用do...while(0)。 比如这个题的循环过程，一开始两个slow和fast必定相同。如果用普通while就是加额外条件判断。