whlit's blog

Appearance

快乐数 ​

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

「快乐数」 定义为：

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

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

示例 1：

  • 输入：n = 19
  • 输出：true
  • 解释：

12+92=82

82+22=68

62+82=100

12+02+02=1

示例 2：

  • 输入：n = 2
  • 输出：false

提示：

1<=n<=231−1

leetcode 原题链接

这道题是一道标记为简单的算法题，不过其中有一些特殊的点存在。

方法一：哈希集合测循环 ​

位数最大值平方和
1981
299162
3999243
49999324
.........
109999999999810
.........
1399999999999991053
.........

从中我们可以找出规律，4位及4位以上的数，平方和的位数必定是小于原数的位数的，当位数降到3时，3位数的平方和的最大值为243也是3位数，所以后续的计算的值必定都在243以内，所以最终的结果就是要么是1，要么陷入循环中，也就是本题的结果了。

所以解决本题的方法就是判断循环，如果循环，那么就返回 false，否则就返回 true。

java
public boolean isHappy(int n) {
    Set<Integer> set = new HashSet<>();
    // n == 1 时，说明是快乐数
    // set里包含n时，说明循环了
    while (n != 1 && !set.contains(n)) {
        set.add(n);
        n = getNext(n);
    }
    return n == 1;
}
public int getNext(int n) {
    int next = 0;
    while (n > 0) {
        int d = n % 10;
        n = n / 10;
        next += d * d;
    }
    return next;
}

方法二：快慢指针 ​

判断循环的另一种方法是快慢指针法，也就是设置两个指针，一个指针一次移动一位，另一个指针一次移动两位。当存在循环时，两个指针必定会相遇，因为他们的移动速度相差一位，每一次移动都相当于两个指针离得更近了一步。

java
public boolean isHappy(int n) {
    int slow = n;
    int fast = getNext(n);
    // n == 1 时，说明是快乐数
    // 当快指针和慢指针相遇时，说明存在循环
    while (fast != 1 && slow != fast) {
        // 慢指针一次循环计算一次
        slow = getNext(slow);
        // 快指针一次循环计算两次
        fast = getNext(getNext(fast));
    }
    return fast == 1;
}
public int getNext(int n) {
    int next = 0;
    while (n > 0) {
        int d = n % 10;
        n = n / 10;
        next += d * d;
    }
    return next;
}

总结 ​

这道题有意思的一点是要判断出每次计算的值不会无限的增大，剩下的就是判断循环了。