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
- 12 + 92 = 82
- 82 + 22 = 68
- 62 + 82 = 100
- 12 + 02 + 02 = 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 };
转载于:https://www.cnblogs.com/LUO77/p/4978375.html
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/109244.html原文链接：https://javaforall.net
