题目要求
实现一个算法来判断一个数字是否开心。一个开心数字是指将数字的各个位上的数求平方和，如果这个数字最终能够计算至1，那么这个数字就是一个开心数字。如果这个数字一直在某个圈中循环，那么这就不是一个开心数字。题目中也给了19这个例子。
思路一：hashset
利用set的特性，我们可以将已经遍历过的值存入其中，如果遇到重复的值就跳出循环并判断重复的值是否为1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public boolean isHappy(int n) {
Set<Integer> hasLoop = new HashSet<Integer>();
while(hasLoop.add(n)){
n = divideAndAdd(n);
}
return hasLoop.contains(1);
}
public int divideAndAdd(int n){
int result = 0;
while(n!=0){
result += Math.pow((n%10), 2);
n /= 10;
}
return result;
}
|
思路二：FLoyd Cycle detection
之前有一道题目，是说如何判断一个链表中是否带环。可以参考我的这篇博客。这里的本质其实和找环是一样的。既然题目中已经告诉我们这样的计算一定会进入一个环，那么我们只需要判断这个环的点中是不是只有1，就可以知道这个数字是不是开心数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int digitSquareSum(int n) {
int sum = 0, tmp;
while (n!=0) {
tmp = n % 10;
sum += tmp * tmp;
n /= 10;
}
return sum;
}
boolean isHappy2(int n) {
int slow, fast;
slow = fast = n;
do {
slow = digitSquareSum(slow);
fast = digitSquareSum(fast);
fast = digitSquareSum(fast);
} while(slow != fast);
if (slow == 1) return true;
else return false;
}
|