今天在上刷题的时候遇到了一个有趣的问题，问题描述如下：

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

题目大意

题目大概意思是说将一个数按照 个、十、百、千位来分解（如果有的话），然后求他们的平方的和，得到结果后重复这个过程。最后结果为1，则该数字为happ number，则返回true，否则返回false

题目分析

第一眼看到题目其实是有点懵逼的，咋一看不知道循环结束的条件。其实循环结束的条件在题目中已经指出来——不为happly number的时候这个循环是重复的，所以说在这个循环的过程当中，推算出来的式子是有重复的部分，下面给出数字为6的时候式子的变换过程：

0^2 + 6^2 = 363^2 + 6^2 = 454^2 + 5^2 = 414^2 + 1^2 = 171^2 + 7^2 = 505^2 + 0^2 = 252^2 + 5^2 = 292^2 + 9^2 = 858^2 + 5^2 = 89    (循环起始部分8^2 + 9^2 = 1451^2 + 4^2 + 5^2 = 424^2 + 2^2 = 202^2 + 0^2 = 44^2 + 0^2 = 161^2 + 6^2 = 373^2 + 7^2 = 58    （一轮循环结束5^2 + 8^2 = 89    （循环重新开始

可以看到当不为happy number的时候，式子在推算到一定程度，就会开始死循环，根据这个特点，这里我使用集合的特性来存储式子，通过判断式子是否重复来界定是否为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}

其他解法

在上我发现我的思路还是具有普遍性，但是网站上我看到了两种比较有意思的解法，下面是具体的代码：

• 解法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]这个区间的特性来判断是否为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;}