Leetcode 快乐数

算法思想：

这段代码的目的是判断一个正整数是否是 快乐数（Happy Number）。根据题目要求，快乐数定义如下：

1. 对于一个正整数，不断将它每个位上的数字替换为这些数字平方和。
2. 重复这个过程，如果最终结果为1，则说明是快乐数。
3. 如果无限循环且始终不能变为1，则不是快乐数。

代码解析：

1. 使用哈希集合检测循环

• 目的：避免进入无限循环。
• 我们用一个 Set<Integer>（哈希集合）来记录过程中出现过的数字。如果某个数字重复出现，说明进入了循环，最终不可能变为1。

2. 主函数逻辑 (isHappy)

Set<Integer> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
    seen.add(n);
    n = getNext(n);
}
return n == 1;

• seen 集合：用来存储每次迭代中已经处理过的数字。
• 循环条件：
  • 如果 n == 1，则直接返回 true，表示是快乐数。
  • 如果 n 在集合中已经出现过，说明进入循环，直接返回 false。
• 核心逻辑：通过不断计算下一步数字（平方和），判断数字序列是否最终会收敛到1。

3. 辅助函数 (getNext)

private static int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;  // 取当前数字的最后一位
        sum += digit * digit;  // 计算该位数字的平方并累加
        n /= 10;  // 去掉最后一位
    }
    return sum;
}

• 功能：计算当前数字 n 的各个位数字的平方和。
• 步骤：
  1. 取个位：通过 n % 10 提取数字的最后一位。
  2. 计算平方和：将每一位的平方加到 sum 中。
  3. 去掉已处理位：通过 n /= 10 删除数字的最后一位。
  4. 循环直到数字处理完毕。

示例运行（以 n = 19 为例）：

初始状态：

• n = 19
• seen = {}

迭代过程：

1. 第一次迭代：

   • getNext(19) 计算：( 1^2 + 9^2 = 1 + 81 = 82 )
   • 更新：n = 82，seen = {19}

2. 第二次迭代：

   • getNext(82) 计算：( 8^2 + 2^2 = 64 + 4 = 68 )
   • 更新：n = 68，seen = {19, 82}

3. 第三次迭代：

   • getNext(68) 计算：( 6^2 + 8^2 = 36 + 64 = 100 )
   • 更新：n = 100，seen = {19, 82, 68}

4. 第四次迭代：

   • getNext(100) 计算：( 1^2 + 0^2 + 0^2 = 1 + 0 + 0 = 1 )
   • 更新：n = 1

结束：

• 因为 n = 1，返回 true，表示 19 是快乐数。

算法复杂度分析：

1. 时间复杂度：

   • 每次调用 getNext 需要处理数字的每一位，耗时 ( O(\log n) )。
   • 在最坏情况下（例如循环中的数字），需要处理的数字数量是有限的。
   • 综合时间复杂度为 ( O(\log n) )。

2. 空间复杂度：

   • 使用了一个 Set 存储数字序列，最多存储循环中的数字。
   • 空间复杂度为 ( O(\log n) )。

java 实现

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();

        while(n != 1 && !set.contains(n)) {//n如果等于1就没有必要再循环了, set如果包含了n,也没必要循环了
            set.add(n);
            n = getNext(n);
        }
        return n == 1;
        
    }

    private int getNext(int n) {
        int sum = 0;
        while(n > 0) {
            int digit = n % 10; // 取当前数字的最后一位
            sum += digit * digit;// 计算该位数字的平方并累加
            n /= 10; //去掉最后一位
        }
        return sum;
    }
}

为什么这一部分条件是且而不是或while (n != 1 && !seen.contains(n))？

完全正确！

你总结得很到位，这个 while 条件其实是通过对“停止条件”的取反得到的。

停止条件

停止循环的条件是：

n == 1 || seen.contains(n)

• n == 1：当前数字已经变成 1，说明是快乐数，不需要继续循环。
• seen.contains(n)：当前数字已经出现过，说明进入了循环，不可能是快乐数，也不需要继续循环。

对停止条件取反

对停止条件取反，得到 while 的判断条件：

!(n == 1 || seen.contains(n))

根据逻辑运算的 德摩根定律（De Morgan’s Law）：

!(A || B) 等价于 !A && !B

所以：

!(n == 1 || seen.contains(n)) 等价于 n != 1 && !seen.contains(n)

这就是 while 循环的条件：

while (n != 1 && !seen.contains(n))

总结

• 停止条件：n == 1 || seen.contains(n)，满足这个条件就应该终止循环。
• 运行条件：取停止条件的反，即 n != 1 && !seen.contains(n)，只有在这两个条件都不满足时才继续循环。

通过这种逻辑转换，我们得到了正确的 while 条件，让程序在逻辑上更清晰，避免冗余判断。