Happy Number

Thanatos 發(fā)布于2019-08-21 16:22 / 355人閱讀

摘要：今天在上刷題的時(shí)候遇到了一個(gè)有趣的問題，問題描述如下題目大意題目大概意思是說將一個(gè)數(shù)按照個(gè)十百千位來分解如果有的話，然后求他們的平方的和，得到結(jié)果后重復(fù)這個(gè)過程。

今天在LeetCode上刷題的時(shí)候遇到了一個(gè)有趣的問題，問題描述如下：

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 = 82  
8^2 + 2^2 = 68  
6^2 + 8^2 = 100  
1^2 + 0^2 + 0^2 = 1

Happy Number 題目大意

題目大概意思是說將一個(gè)數(shù)按照個(gè)、十、百、千位來分解（如果有的話），然后求他們的平方的和，得到結(jié)果后重復(fù)這個(gè)過程。最后結(jié)果為1，則該數(shù)字為happ number，則返回true，否則返回false

題目分析

第一眼看到題目其實(shí)是有點(diǎn)懵逼的，咋一看不知道循環(huán)結(jié)束的條件。其實(shí)循環(huán)結(jié)束的條件在題目中已經(jīng)指出來——不為happly number的時(shí)候這個(gè)循環(huán)是重復(fù)的，所以說在這個(gè)循環(huán)的過程當(dāng)中，推算出來的式子是有重復(fù)的部分，下面給出數(shù)字為6的時(shí)候式子的變換過程：

0^2 + 6^2 = 36
3^2 + 6^2 = 45
4^2 + 5^2 = 41
4^2 + 1^2 = 17
1^2 + 7^2 = 50
5^2 + 0^2 = 25
2^2 + 5^2 = 29
2^2 + 9^2 = 85
8^2 + 5^2 = 89    (循環(huán)起始部分
8^2 + 9^2 = 145
1^2 + 4^2 + 5^2 = 42
4^2 + 2^2 = 20
2^2 + 0^2 = 4
4^2 + 0^2 = 16
1^2 + 6^2 = 37
3^2 + 7^2 = 58    （一輪循環(huán)結(jié)束
5^2 + 8^2 = 89    （循環(huán)重新開始

可以看到當(dāng)不為happy number的時(shí)候，式子在推算到一定程度，就會(huì)開始死循環(huán)，根據(jù)這個(gè)特點(diǎn)，這里我使用集合的特性來存儲(chǔ)式子，通過判斷式子是否重復(fù)來界定是否為happy number

AC代碼

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function (n) {
    let result = String(n).split(""),counter = 1
    let collections = new Set()
    collections.add(result.join(""))
    while (counter === collections.size) {
        result = result.reduce((total, currentValue) => {
            return total + Math.pow(currentValue, 2)
        }, 0)
        counter++
        collections.add(String(result))
        result = String(result).split("")
        if(result[0] === "1" && result.length === 1){
            return true
        }
    }
    return false
}

其他解法

在LeetCode上我發(fā)現(xiàn)我的思路還是具有普遍性，但是網(wǎng)站上我看到了兩種比較有意思的解法，下面是具體的代碼：

解法1： Using fact all numbers in [2, 6] are not happy (and all not happy numbers end on a cycle that hits this interval):

(大意就是說利用非happy number在[2,6]這個(gè)區(qū)間的特性來判斷是否為happy number

bool isHappy(int n) {
    while(n>6){
        int next = 0;
        while(n){next+=(n%10)*(n%10); n/=10;}
        n = next;
    }
    return n==1;
}

解法2：I see the majority of those posts use hashset to record values. Actually, we can simply adapt the Floyd Cycle detection algorithm. I believe that many people have seen this in the Linked List Cycle detection problem. The following is my code:

（大意是說利用修改 Floyd Cycle 來判斷是否為happy number

int digitSquareSum(int n) {
    int sum = 0, tmp;
    while (n) {
        tmp = n % 10;
        sum += tmp * tmp;
        n /= 10;
    }
    return sum;
}
bool isHappy(int n) {
    int slow, fast;
    slow = fast = n;
    do {
        slow = digitSquareSum(slow);
        fast = digitSquareSum(fast);
        fast = digitSquareSum(fast);
    } while(slow != fast);
    if (slow == 1) return 1;
    else return 0;
}

掃描下方的二維碼或搜索「tony老師的前端補(bǔ)習(xí)班」關(guān)注我的微信公眾號，那么就可以第一時(shí)間收到我的最新文章。