LeetCode_49_HappyNumber


1. question: 快乐数(简单)

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

「快乐数」 定义为:

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

如果 n 是 快乐数 就返回 true ;不是,则返回 false 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/happy-number

示例 1:

1
2
3
4
5
6
7
输入:n = 19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2:

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

提示:

1
1 <= n <= 231 - 1

2. answers

这道题的难点在于如何确定它不是快乐数,难道要一直循环下去吗?显然不是,既然是无限循环(这里应该和无限不循环小数的无限不循环区分开来,也就是保证不会出现无限不循环),必然存在过程中的某个数。那么如何判断过程中存在当前数呢?显然用到了包含、匹配。采用哈希表来做。

将计算过程中出现的数保存在哈希表中,如果后续又出现了这个数,那么必定是无限循环了,不是快乐数。代码如下所示:

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
26
27
28
29
30
31
public class Solution_0046 {

public static boolean isHappy(int n) {

HashSet<Integer> hashSet = new HashSet<>();
int temp;

while(!hashSet.contains(n)) {
hashSet.add(n);

temp = n;
n = 0;
while(temp != 0) {
n += Math.pow(temp % 10, 2);
temp = temp / 10;
}

if(n == 1)
return true;
}

// 循环结束,说明必定包含某个中间过程的数,因此会无线循环下去
return false;
}

public static void main(String[] args) {
System.out.println();

System.out.println(isHappy(2));
}
}

3. 备注

参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)代码随想录 (programmercarl.com)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录