leetcode happy number

全栈程序员-站长 • 2021年9月10日下午9:00 • 未分类 • 阅读 79

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

有一些题一看我就觉得有些难，这就是一道。首先，我很不喜欢题目里定义了很多东西这样。于是乎，刚开始的思路就华丽丽地跑偏了，走到了总结规律上面。

是的，没错，我首先想到的就是有什么规律，什么规律会是一个happy number。。想了很多甚至连(a+b)2=a2+b2+2ab呀这种公式都试啊试的

后来就想着算了，按照这个走吧。

问题一：提取每一位，刚开始都忘记了怎么提取每一位。不过后来想到了。

问题二：怎样就判断不是happy number了，这也是一个卡住我的地方，我最开始想的是假如回到原点就不是happy number了，就是2计算了一堆最后又回到2,2显然不是happy number。

但是，没错，超时了。后来看了陆草纯的代码，其他搜了很多都是用set实现的，我明显更加喜欢map，陆草纯用map记录了哪些数字已经被计算过但是不是happy number的。这其实是一个循环。例如

2->4->16->37->58->89->145->20->2->4…开始循环，所以这个循环里的每个数都会进入一个圈圈。我们用map记录哪些已经被计算过，如果已经被计算过，我们又遇到它且它不为1，直接false说明我们进入一个循环。

因为一个happy number的数列里一定是只出现一次的。

 1 class Solution {
 2 public:
 3     int GetSum(int n){
 4         int c=0,sum=0;
 5          while(n!=0){
 6             c=n%10;
 7             n/=10;
 8             sum+=(c*c);
 9         }
10         return sum;
11     }
12         
13     bool isHappy(int n) {
14         if(n==1) return true;
15         unordered_map<int,bool> haveCalIt;
16         int sum=GetSum(n);
17         while(sum!=1){
18             if(haveCalIt[sum]==true) return false;
19             haveCalIt[sum]=true;
20             sum=GetSum(sum);
21             
22         }
23         return true;
24     }
25 };