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^2 + 9^2 = 828^2 + 2^2 = 686^2 + 8^2 = 1001^2 + 0^2 + 0^2 = 1s思路： 1. 就是检测是否有loop,如果出现loop还没有发现1，那就是没1，就不是happy number 2. loop就看是否出现两次，检查重复，就用hash做！ 3. 网上发现另一种，利用快慢指针的方法做，可以省掉hash的空间，这个方法就是在链表中多次使用的用于检测cycle的方法。 4. 用一快一慢两个指针，当快指针和慢指针相遇，说明遇到环了，如果在此之前还没发现快指针指向1，则这个环没有1，因此就不是happy number 5. 把链表中的方法运用在这个场合，说明第一个想到这个方法的人，是打破了思维中的限制：认为快慢指针只能用在链表中来找cycle。只有思维里没有这个限制或者打破了这层限制，才能看到这个方法起始有更广的应用范围，除了链表，一切前后相继的数，或者找任何地方的cycle，都可以认准快慢指针大法！ 6. 在方法2中，用到do-while,而不用while。平时写代码几乎不用do while。这里为啥非要用do-while呢？后面代码2.1尝试用while来替代do-while,很麻烦。原因是：do-while可以先计算，后判断；而while上来就先判断，然后才计算。而这道题，slow和fast初值都是n,而判断是否跳出循环的条件是slow!=fast，现在用while就不行，因为slow和fast初始值相等，所以无法进入while。因此，就应该用do-while，来做到初始值相等，但运算之后不等的情况！
//方法1：hash找cycleclass Solution {public: bool isHappy(int n) { // unordered_set<int> ss; while(n!=1){ if(ss.count(n)) return false; ss.insert(n); int cur=0; while(n){ cur+=((n%10)*(n%10));//bug:+=这种简写容易出现的bug,后面一定要优先计算，因此必须用括号提高优先级 n/=10; } n=cur; } return true; }};//方法2：快慢指针找cycle!class Solution {public: int happy(int n){ int res=0; while(n){ res+=((n%10)*(n%10)); n/=10; } return res; } bool isHappy(int n) { // int slow=n,fast=n; do{//思考一下为什么用do-while?不能用while slow=happy(slow); fast=happy(happy(fast)); if(fast==1) return true; }while(slow!=fast); return false; }};//方法2.1：快慢指针找cycle!尝试把do-while换成while，费劲！还是do-while好用！class Solution {public: int happy(int n){ int res=0; while(n){ res+=((n%10)*(n%10)); n/=10; } return res; } bool isHappy(int n) { // int slow=n,fast=happy(n); while(slow!=fast){ slow=happy(slow); fast=happy(happy(fast)); if(fast==1) return true; } return fast==1; }};新闻热点
疑难解答
