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; }};新聞熱點
疑難解答
