算法力扣刷题记录 十五【202. 快乐数】

前言

哈希结构，第三题。
记录 十五【202. 快乐数】
继续。

---

一、题目阅读

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

「快乐数」 定义为：

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

示例 1：

输入：n = 19
输出：true
解释：
1^2 + 9 ^2 = 82
8^2 + 2 ^2 = 68
6 ^2 + 8 ^2 = 100
1 ^2 + 0 ^2 + 0 ^2 = 1
1
2
3
4
5
6
7

示例 2：

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

提示：

1 <= n <= 2^31 - 1
1

---

二、第一次尝试

思路

• 定义一个函数，每次调用函数进行数字求和。
• 看这个sum有没有存在过？如果等于1，立即return true；
• 如果存在过，说明无限循环。return false。
• 没有存在过，而且不等于1，把sum插入到集合里。
• 解决怎么计算sum？

  int test(int m){
      int result = 0;
      while(m%10){	//错误地方：如果个位是0，无法进入循环，比如100,240等
          result += (m%10) * (m%10);
          m = (m - m%10)/10;
      }
      return result;
  }
  
  //改进
  int test(int m){
      int result = 0;
      while((m%10 == 0)&&(m/10 != 0)){	//把数字末尾的0全部删掉
         m = m/10;
       }
      while(m%10){	//在进入求和
          result += (m%10) * (m%10);
          m = (m - m%10)/10;
      }
      return result;
  }
  //这个逻辑可以正确求解。
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23

代码实现（测试通过）

class Solution {
public:
    bool isHappy(int n) {
        unordered_map<int,int> map;//无序、不重复。顺序不重要，但是不能重复
        while(1){
            int sum = test(n);
            if(sum == 1 ){	//如果sum等于1，说明是，立即返回true
                return true;
            }
            if((map.insert({n,sum})).second == false){	//如果插入不成功，返回false陷入无限循环
                return false;
            }
            n = sum;
        }
    }

    int test(int m){	//求和
        int result = 0;
        while((m%10 == 0)&&(m/10 != 0)){	//把数字末尾的0全部删掉
           m = m/10;
         }
        while(m%10){	//在进入求和
            result += (m%10) * (m%10);
            m = (m - m%10)/10;
        }
        return result;
    }
};
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

中间错误（弯路）

可能从示例2发现：返回false，当某个时刻sum > 1 && sum < 10，之后平方数值会越来越大，（偷换概念，不是当前数求平方），所以错误。
有些用例不能通过

class Solution {
public:
    bool isHappy(int n) {
        unordered_map<int,int> map;//无序、不重复
        while(1){
            int sum = test(n);
            if(sum == 1 || (map.insert({n,sum})).second == false){
                return true;
            }
            if( 1 < sum && sum < 10){	//1 < sum <10这样写是错的，看成(1 < sum) < 10，始终成立。
                return false;
            }
            n = sum;
        }
    }

    int test(int m){
        int result = 0;
        while((m%10 == 0)&&(m/10 != 0)){	//把数字末尾的0全部删掉
           m = m/10;
         }
        while(m%10){	//在进入求和
            result += (m%10) * (m%10);
            m = (m - m%10)/10;
        }
        return result;
    }
};
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

---

三、代码随想录学习

学习内容

参考用的结构是unordered_set，无序，不重复。只记录sum。
个人用unordered_map，无序，不重复。但记录<n,sum>，n是输入的数。

求和改进，更简单：

	int test(int m){
	        int result = 0;
	        while(m){		//区别一
	            result += (m%10) * (m%10);
	            m = m /10;		//区别二
	        }
	        return result;
	    }
1
2
3
4
5
6
7
8

---

总结：

（1）学习怎么获取每个位置上的数字。

（2）理解好题目，快乐数进入无限循环，有重复sum，说明sum曾经在这个集合中出现过，返回false。只要sum等于1就返回true，所以先判断sum等于1吗？再判断能否成功insert？；

（3）发现顺序没有那么重要，所以可以无序，但是不重复，选定哈希结构unordered_set或unordered_map。

(欢迎指正，转载表明出处)