跳转至

LeetCode: 202.快乐数

1、题目表述

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

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

示例:

输入: 19
输出: true
解释: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
1^2+9^2=82\\ 8^2+2^2=68\\ 6^2+8^2=100\\ 1^2+0^2+0^2=1

2、解题思路

​ 首先,我们来判断一个数快不快乐,如果不能够得到一,就会一直计算下去,

首先,我们知道,一个一位数,最大是9,两位,99,三位,999

位数 最大值 最大值下一个数
1 9 81
2 99 162
3 999 243
4 9999 324
5 99999 405
6 999999 486
7 9999999 567

13位 1053

​ 我们可以看到,当位数超过3的时候,也就是数字超过1000,下一个数字相比位数的增加,增加很缓慢,远远小于当前值,并且,大于1000的数,超过13位的时候,最大才超过1053,也就是说,所有的数字,经过几次变换,肯定会变换到小于1000的数,小于1000的最大就是243,最终,任何一个数,变换几次以后,都不会大于243

2.1 缓存法

​ 一种思路,我们将小于243的欢乐数缓存起来,将这个数进行变换,如果数值小于243了,就与缓存数组中的数进行判断,如果不匹配,返回假,匹配则返回真

​ 实际上,只需要162个就够用了

int countPowNumber(int n) {
    int result = 0;
    while (n / 10 > 0 || n % 10 > 0) {
        result += (n % 10) * (n % 10);
        n /= 10;
    }
    return result;
}

bool isHappy(int n) {
    bool cycle = true;
    int result = n;
    int *buff = (int *) malloc(sizeof(int) * 163);

    for (int i = 0; i < 163; i++) {
        buff[i] = 0;
    }

    while (cycle) {
        if (result >= 163) {
            result = countPowNumber(result);
        } else if (result == 1) {
            cycle = false;
        } else {
            if (buff[result] == 0) {
                buff[result]++;
                result = countPowNumber(result);
            } else {
                cycle = false;
            }
        }
    }

    free(buff);
    if (result == 1) {
        return true;
    } else {
        return false;
    }


}

2.2 重复判断法

​ 我们知道,数字可能性就是0~9,平方值分别是

数字 平方
0 0
1 1
2 4
3 9
4 16
5 25
6 36
7 49
8 64
9 81

​ 根据之前的分析,当数值大于1000,每次增加1位,位数的平方和最多增加81,因此,最终大于1000的数都会慢慢变小,变成1000以内的数,而1000以内的数,最大的是243

​ 因此,也就是3位中,哪些组合肯定不能变成快乐数呢?

​ 根据快乐数的说法,如果平方加起来是1,10,100,就是平方数

​ 我们就在这里面找出,一旦出现,就肯定不是平方数的那个数,最少一个,最多3个数(考虑243)

1肯定可以

判断10以内的数,加起来能不能变成10

0,1,9都可以,4不可以

判断100以内的数

36+64是可以的

由于平方数可以多次计算,因此,下一次加起来能够得到 1,10, 13,31,13,68,86,也是平方数

那么哪个数字的平方数加起来能够得到呢(最多加3次)

我们发现,

1+9 = 10,表示1,3的组合都是可以的

1+9+0=10,表示1,3,0的组合都是可以的

4+9 = 13,表示2,3的组合都是可以的

4+9 +0 = 13,表示2,3,0的组合都是可以的

16+16+36 = 68, 表示 4,4,6,的组合是可以的

36+16+16 = 68,6,4,4,的组合都可以

49+16+1 = 68, 7,4,1的组合都可以

64+4+0 = 68 , 表示2,8,0的组合都是可以的

25+25+36 = 86,表示5,5,6的组合都可以

49+36+1 = 86,表示7,6,1的组合都可以

不过,能够得到这些数的也都是可以的

根据一般结论,如果出现4,肯定不是快乐数,也可以这样判断