题目
要求
编写一个算法来判断一个数 n
是不是快乐数。
「快乐数」 定义为:
- 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1,那么这个数就是快乐数。
如果 n
是 快乐数 就返回 true
;不是,则返回 false
。
思路
这道题目我没有思路,该怎么说呢,数据归纳法,看到下面这组数据:
Digits | Largest | Next |
---|---|---|
1 | 9 | 81 |
2 | 99 | 162 |
3 | 999 | 243 |
4 | 9999 | 324 |
13 | 9999999999999 | 1053 |
可以看到的是无论多大的数字,最后经过计算总会回归到 3 位数,例如 9999 的下一个是 324,而 999 最后是 243,也就是说最后只有两种情况,一种是得到快乐数,最后结果是 1,另外一种就是无限循环,但是是在 243 以下循环,基于此,可以考虑使用递归的方法,看看结果如果是 1 或者之前出现过,那说明出现了环,就退出:
public boolean isHappy(int n) {
int[] arr = new int[244];
return myIsHappy(n, arr);
}
public boolean myIsHappy(int n, int[] arr) {
if (n == 1) {
return true;
}
if (n < 244 && arr[n] == 2) {
return false;
}
int sum = getNext(n);
if (sum < 244) {
arr[sum]++;
}
return myIsHappy(sum, arr);
}
public int getNext(int n) {
int sum = 0;
while (n > 0) {
int d = n % 10;
n /= 10;
sum += d * d;
}
return sum;
}
看到环,能想到啥,链表呀,这个可以看做是一个链表,要么结果为 1,要么是链表成环,可以使用一个数组做一个缓存,因为快慢指针肯定有计算过的,防止重复计算,代码如下:
public boolean isHappy(int n) {
// arr 加一层缓存,防止计算 next 的时候重复计算
int[] arr = new int[244];
int slow = n;
int fast = getNext(n, arr);
while (fast != 1 && fast != slow) {
slow = getNext(slow, arr);
fast = getNext(getNext(fast, arr), arr);
}
return fast == 1;
}
private int getNext(int n, int[] arr) {
if (n < 244 && arr[n] != 0) {
return arr[n];
}
int sum = 0;
while (n > 0) {
int d = n % 10;
n /= 10;
sum += d * d;
}
if (n < 244) {
arr[n] = sum;
}
return sum;
}
标签:getNext,arr,202,return,int,sum,244,快乐
From: https://www.cnblogs.com/wadmwz/p/17911862.html