leetcode_202. 快乐数

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

「快乐数」定义为：

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

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

 1 int getsum(int n) {
 2     int sum = 0;
 3     while(n != 0) {
 4         sum += (n%10) * (n%10);
 5         n = n / 10;
 6     }
 7     return sum;
 8 }
 9 
10 
11 bool isHappy(int n){
12     int *hash = (int *)malloc(sizeof(int) * 1000) ;
13     memset(hash, 0, sizeof(int) * 1000);
14 
15     int flag = 0;
16     n = getsum(n); // 这里先算一步是关键， 要不然 1000个内存肯定不够，数据是 2的31次方 -1
17     while(n != 1) {
18         if(hash[n] == 1) {
19             flag = 1;
20             return false;
21         }
22         hash[n]++;
23         n = getsum(n);         
24     }
25     return true;
26 }

方法2 ：

用 ut_hash 不用考虑 malloc 的内存大小

 1 typedef struct {
 2     int key;
 3     UT_hash_handle hh;
 4 }Hash;
 5 
 6 Hash *users = NULL;
 7 
 8 int GetSums(int n) {
 9      int sum = 0;
10      while(n != 0) {
11         sum += (n%10) * (n%10);
12         n = n / 10;
13      }
14      return sum;
15 }
16 
17 bool isHappy(int n) {
18     users = NULL;
19     int res = 0;
20     while(n != 1) {
21         res = GetSums(n);
22         Hash *tmp = NULL;
23         HASH_FIND_INT(users, &res, tmp);
24         if(tmp) {
25             return false;
26         } else {
27             tmp = (Hash *)calloc(1, sizeof(Hash));
28             tmp->key = res;
29             HASH_ADD_INT(users, key, tmp);
30         }
31         n = res;
32     }
33     Hash *cur = NULL;
34     Hash *tmp = NULL;
35     HASH_ITER(hh, users, cur, tmp) {
36         if(cur) {
37             HASH_DEL(users, cur);
38             free(cur);
39         }
40     }
41     return true;
42 }

方法3 ：龟兔赛跑

int getsum(int n) {
    int num = 0;
    while(n != 0){
        num = num + (n%10) * (n%10);
        n = n / 10;
    }
    return num;
}


bool isHappy(int n){
    int slow = getsum(n);
    int fast = getsum(n);
    fast = getsum(fast);

    while(slow != fast) {
        slow = getsum(slow);
        fast = getsum(fast);
        fast = getsum(fast);
    }

    if(slow == 1) {
        return true;
    }else {
        return false;
    }

}

16算法

leetcode_202. 快乐数

相关

标签