前言
哈希结构，第三题。
记录 十五【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
示例 2：
输入：n = 2
输出：false
提示：
1 <= n <= 2^31 - 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; } //这个逻辑可以正确求解。
代码实现（测试通过）
class Solution {
public:bool isHappy(int n) {unordered_map<int,int> map;//无序、不重复。顺序不重要，但是不能重复while(1){int sum = test(n);if(sum == 1 ){ //如果sum等于1，说明是，立即返回truereturn 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;}
};
中间错误（弯路）
可能从示例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;}
};
三、代码随想录学习
学习内容
参考用的结构是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）理解好题目，快乐数进入无限循环，有重复sum，说明sum曾经在这个集合中出现过，返回false。只要sum等于1就返回true，所以先判断sum等于1吗？再判断能否成功insert？；
（3）发现顺序没有那么重要，所以可以无序，但是不重复，选定哈希结构unordered_set或unordered_map。
(欢迎指正，转载表明出处)
