C++實現(xiàn)LeetCode(202.快樂數)
[LeetCode] 202.Happy Number 快樂數
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:
Input: 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
Credits:
Special thanks to @mithmatt and @ts for adding this problem and creating all test cases.
這道題定義了一種快樂數,就是說對于某一個正整數,如果對其各個位上的數字分別平方,然后再加起來得到一個新的數字,再進行同樣的操作,如果最終結果變成了1,則說明是快樂數,如果一直循環(huán)但不是1的話,就不是快樂數,那么現(xiàn)在任意給我們一個正整數,讓我們判斷這個數是不是快樂數,題目中給的例子19是快樂數,那么我們來看一個不是快樂數的情況,比如數字11有如下的計算過程:
1^2 + 1^2 = 2
2^2 = 4
4^2 = 16
1^2 + 6^2 = 37
3^2 + 7^2 = 58
5^2 + 8^2 = 89
8^2 + 9^2 = 145
1^2 + 4^2 + 5^2 = 42
4^2 + 2^2 = 20
2^2 + 0^2 = 4
我們發(fā)現(xiàn)在算到最后時數字4又出現(xiàn)了,那么之后的數字又都會重復之前的順序,這個循環(huán)中不包含1,那么數字11不是一個快樂數,發(fā)現(xiàn)了規(guī)律后就要考慮怎么用代碼來實現(xiàn),我們可以用 HashSet 來記錄所有出現(xiàn)過的數字,然后每出現(xiàn)一個新數字,在 HashSet 中查找看是否存在,若不存在則加入表中,若存在則跳出循環(huán),并且判斷此數是否為1,若為1返回true,不為1返回false,代碼如下:
解法一:
class Solution { public: bool isHappy(int n) { unordered_set<int> st; while (n != 1) { int sum = 0; while (n) { sum += (n % 10) * (n % 10); n /= 10; } n = sum; if (st.count(n)) break; st.insert(n); } return n == 1; } };
其實這道題也可以不用 HashSet 來做,我們并不需要太多的額外空間,關于非快樂數有個特點,循環(huán)的數字中必定會有4,這里就不做證明了,我也不會證明,就是利用這個性質,就可以不用set了,參見代碼如下:
解法二:
class Solution { public: bool isHappy(int n) { while (n != 1 && n != 4) { int sum = 0; while (n) { sum += (n % 10) * (n % 10); n /= 10; } n = sum; } return n == 1; } };
這道題還有一種快慢指針的解法,由熱心網友喵團團提供,跟之前那道 Linked List Cycle 檢測環(huán)的方法類似,不同的是這道題環(huán)一定存在,不過有的環(huán)不符合題意,只有最后 slow 停在了1的位置,才表明是一個快樂數。而且這里每次慢指針走一步,快指針走兩步,不是簡單的指向next,而是要調用子函數計算各位上數字的平方和,當快慢指針相等時,跳出循環(huán),并且判斷慢指針是否為1即可,參見代碼如下:
解法三:
class Solution { public: bool isHappy(int n) { int slow = n, fast = n; while (true) { slow = findNext(slow); fast = findNext(fast); fast = findNext(fast); if (slow == fast) break; } return slow == 1; } int findNext(int n) { int res = 0; while (n > 0) { res += (n % 10) * (n % 10); n /= 10; } return res; } };
類似題目:
參考資料:
https://leetcode.com/problems/happy-number/
到此這篇關于C++實現(xiàn)LeetCode(202.快樂數)的文章就介紹到這了,更多相關C++實現(xiàn)快樂數內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
matlab遺傳算法求解車間調度問題分析及實現(xiàn)源碼
這篇文章主要為大家介紹了matlab遺傳算法求解車間調度問題解析,文中附含詳細實現(xiàn)源碼,有需要的朋友可以借鑒參考下,希望能夠有所幫助2022-02-02C語言實現(xiàn)進程5狀態(tài)模型的狀態(tài)機
狀態(tài)機在實際工作開發(fā)中應用非常廣泛,用這幅圖就可以很清晰的表達整個狀態(tài)的流轉。本篇通過C語言實現(xiàn)一個簡單的進程5狀態(tài)模型的狀態(tài)機,讓大家熟悉一下狀態(tài)機的魅力,需要的可以參考一下2022-10-10