欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實現(xiàn)LeetCode(202.快樂數)

 更新時間:2021年08月06日 15:21:28   作者:Grandyang  
這篇文章主要介紹了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;
    }
};

類似題目:

Linked List Cycle

參考資料:

https://leetcode.com/problems/happy-number/

https://leetcode.com/problems/happy-number/discuss/56913/Beat-90-Fast-Easy-Understand-Java-Solution-with-Brief-Explanation

https://leetcode.com/problems/happy-number/discuss/56917/My-solution-in-C(-O(1)-space-and-no-magic-math-property-involved-)

到此這篇關于C++實現(xiàn)LeetCode(202.快樂數)的文章就介紹到這了,更多相關C++實現(xiàn)快樂數內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!

相關文章

  • C語言中的分支循環(huán)其嵌套語句

    C語言中的分支循環(huán)其嵌套語句

    這篇文章主要介紹了C語言中的分支循環(huán)其嵌套語句,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-02-02
  • matlab遺傳算法求解車間調度問題分析及實現(xiàn)源碼

    matlab遺傳算法求解車間調度問題分析及實現(xiàn)源碼

    這篇文章主要為大家介紹了matlab遺傳算法求解車間調度問題解析,文中附含詳細實現(xiàn)源碼,有需要的朋友可以借鑒參考下,希望能夠有所幫助
    2022-02-02
  • C語言實現(xiàn)旅游資訊管理系統(tǒng)

    C語言實現(xiàn)旅游資訊管理系統(tǒng)

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)旅游資訊管理系統(tǒng),文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • c語言動態(tài)內存分配知識點及實例

    c語言動態(tài)內存分配知識點及實例

    在本篇文章里小編給大家整理的是關于c語言動態(tài)內存分配知識點及實例,需要的朋友們可以學習下。
    2020-03-03
  • C語言實現(xiàn)簡單的貪吃蛇游戲的示例代碼

    C語言實現(xiàn)簡單的貪吃蛇游戲的示例代碼

    這篇文章主要為大家詳細介紹了C語言如何實現(xiàn)經典貪吃蛇游戲,文中的示例代碼講解詳細,對我們學習C語言有一定的幫助,感興趣的小伙伴可以跟隨小編一起了解一下
    2023-01-01
  • Qt5 串口類QSerialPort的實現(xiàn)

    Qt5 串口類QSerialPort的實現(xiàn)

    在Qt5以上提供了QtSerialPort模塊,方便編程人員快速的開發(fā)應用串口的應用程序。本文主要介紹了Qt5 串口類QSerialPort的實現(xiàn),,感興趣的可以了解一下
    2022-05-05
  • 基于select、poll、epoll的區(qū)別詳解

    基于select、poll、epoll的區(qū)別詳解

    本篇文章是對select、poll、epoll之間的區(qū)別進行了詳細的分析介紹。需要的朋友參考下
    2013-05-05
  • c++ 隊列相關知識總結

    c++ 隊列相關知識總結

    這篇文章主要介紹了c++ 隊列相關知識總結,幫助大家更好的理解和學習使用c++,感興趣的朋友可以了解下
    2021-03-03
  • C語言實現(xiàn)進程5狀態(tài)模型的狀態(tài)機

    C語言實現(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
  • 深入C++中API的問題詳解

    深入C++中API的問題詳解

    本篇文章是對C++中API的問題進行了詳細的分析介紹,需要的朋友參考下
    2013-05-05

最新評論