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
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/109244.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...