Happy Number

Thanatos 发布于2019-08-21 16:22 / 265人阅读

摘要：今天在上刷题的时候遇到了一个有趣的问题，问题描述如下题目大意题目大概意思是说将一个数按照个十百千位来分解如果有的话，然后求他们的平方的和，得到结果后重复这个过程。

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

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 = 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    (循环起始部分
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    （一轮循环结束
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
}

其他解法

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

解法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;
}

扫描下方的二维码或搜索「tony老师的前端补习班」关注我的微信公众号，那么就可以第一时间收到我的最新文章。

私有云 GPU服务器 Happy number number用法 number型数据

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/88454.html

[Leetcode] Happy Number 快乐数

摘要：集合法复杂度时间待定空间待定思路根据快乐数的计算方法，我们很难在有限步骤内确定一个数是否是快乐数，但使用排除法的话，我们可以尝试确定一个数不是快乐数。根据题意，当计算出现无限循环的时候就不是快乐数。 Happy Number Write an algorithm to determine if a number is happy. A happy number is a number...

lindroid 2019-08-14 16:11 评论0 收藏0
[LeetCode/LintCode] Happy Number

Problem 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 squar...

崔晓明 2019-08-14 15:11 评论0 收藏0
红皮书（4）：引用类型

摘要：类型类型重排序方法升序降序方法返回从参数指定位置开始到当前数组末尾的所有项。要注意的是，传递给构造函数的两个参数都是字符串不能把正则表达式字面量传递给构造函数。由于构造函数的模式参数是字符串，所以在某些情况下要对字符串进行双重转义。 Object类型 Array类型重排序方法: compare 升序： function compare(value1, value2){ ...

CoorChice 2019-08-21 12:07 评论0 收藏0
《JavaScript高级程序设计》笔记：引用类型（五）

摘要：元素是通过指定的分隔符进行分隔的。返回值如果从中删除了元素，则返回的是含有被删除的元素的数组。根据使用的方法不同，这个函数执行后的返回值可能会也可能不会影响访问的返回值。对数组中的每一项运行给定函数，返回该函数会返回的项组成的数组。 Object类型创建object实例方法有两种。第一种方法使用new操作符后跟object构造函数。如下： var person=new Object(...

maybe_009 2019-08-26 11:29 评论0 收藏0