202. 快乐数

1. 题目

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

「快乐数」 定义为：

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

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

示例 1：

1
2
3
4
5
6
7
输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 02 = 1

示例 2：

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

提示：

  • 1 <= n <= 2^31 - 1

2. 思路

  • 初始化map哈希表用于后续判断整个计算过程中是否进入环形循环（因为存在无限循环后也达不到1的场景，此时会出现循环链，如数值2）
  • 循环遍历计算新的n值，直至n为1，则中断循环返回结果为true
  • 每次循环前都需要判断最新的n值是否已经存在于哈希表中，如果已经存在，则直接返回false
  • 并实时将当前最新的n值放置入哈希表中，同时按照题目规则计算出下一个n值

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean isHappy(int n) {
        var map = new HashMap<Integer, Integer>();

        while (n != 1) {
            if (map.containsKey(n)) {
                return false;
            }
            map.put(n, n);
            n = calculateNewValue(n);
        }

        return true;
    }

    private int calculateNewValue(int currentValue) {
        var newValue = 0;
        while (currentValue != 0) {
            var num = currentValue % 10;
            newValue += (num * num);
            currentValue /= 10;
        }
        return newValue;
    }
}

4. 复杂度

  • 时间复杂度：O(logn)
  • 空间复杂度：O(logn)

image-20230831222447864