HappyNumber [source code]

public class HappyNumber {
static

public class Solution {
    public boolean isHappy(int n) {
        int slow = n, fast = n;
        do {
            slow = getSquareSum(slow);
            fast = getSquareSum(fast);
            fast = getSquareSum(fast);
        } while (slow != fast);
        return slow == 1;
    }

    public int getSquareSum(int n) {
        int res = 0;
        while (n > 0) {
            int digit = n % 10;
            res += digit * digit;
            n /= 10;
        }
        return res;
    }
}

    public static void main(String[] args) {
        HappyNumber.Solution tester = new HappyNumber.Solution();
        System.out.println(tester.isHappy(Integer.parseInt(args[0])));
    }
}

这个题目的难点肯定是在于return false的情形, 关键是要怎么判断出来进入了死循环. 这个问题我想了半天最后还是一点思路都没有.
这里这个答案是 discussion 最优解, 是一个比较直观而且通用的解法, 这个是作者自己的解释:

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.

最后的速度也是非常好(2(83), 几乎可以算是一个 submission 最优解了), space 更是只有O(1).
这个代码的本质我现在还不是完全理解, 不过是一个很通用的算法: 针对死循环检测;

不过感觉这里其实偷欢了一点概念: 这里做的其实不是一个通用的死循环检测, 而是一个cycle detection. 这两个严格来说并不是完全等价的问题. 事实上, 我就没有想到要用cycle detection来做这个题目.

在这个问题上, 我也尝试过用举例子的方法来找到思路, 但是我举例子的方式太粗犷了, 我直接就写了一个小函数, 然后从0到30的每一个数字都跑一下, 人工判断是否进入了死循环. 我当时这么做的原因是因为感觉这个题目可能是一个 pattern题. 当这个尝试失败了以后, 我直接就放弃了.

感觉这个思维习惯有问题, 我现在思考问题的时候找方向完全就是凭感觉, 脑子里冒出来什么就用什么. 脑子里要是什么都没有冒出来的时候就死机. 为了避免今后有这种情况, 建议每一个方向都在纸上写下来. 有点像backtracking search.

• pattern 题?
• 没思路? 举例总结简单升级找思路;

这样的做法.

这题你找几个 unhappy 的 number 算一算, 是可以发现这里的死循环是有 cycle 的(有些其他的死循环不一定就肯定是有 cycle, 比如说可能是发散, 越来越大). 然后就是怎么找 cycle 了.
这里给出的是一种方法, 另外一个思路就是 hashset, 这个更直接, 类似于之前看到的东南西北 string 题一样.

至于怎么理解这个 Floyd 算法? 还是 enumeration.

• 如果是一个happy 的, 那么 fast 会先停在1, 然后 slow 会停在1, 然后循环结束;
• 如果是一个 unhappy 的, fast 走的比较快, 最后肯定会赶上 slow(因为有 cycle), 这个时候也是停止循环, 但是这个时候的停止点就不是1了.

另外一个重要的问题, 这里证明有 cycle/loop 的过程我并没有证明, 只是通过举例子简单归纳了一下, discussion 上面有人给出了一个非常出色的证明:
Earlier posts gave the algorithm but did not explain why it is valid mathematically, and this is what this post is about: present a "short" mathematical proof.

First of all, it is easy to argue that starting from a number I, if some value - say a - appears again during the process after k steps, the initial number I cannot be a happy number. Because a will continuously become a after every k steps.

Therefore, as long as we can show that there is a loop after running the process continuously, the number is not a happy number.

There is another detail not clarified yet: For any non-happy number, will it definitely end up with a loop during the process? This is important, because it is possible for a non-happy number to follow the process endlessly while having no loop.

To show that a non-happy number will definitely generate a loop, we only need to show that for any non-happy number, all outcomes during the process are bounded by some large but finite integer N. If all outcomes can only be in a finite set (2,N], and since there are infinitely many outcomes for a non-happy number, there has to be at least one duplicate, meaning a loop!

Suppose after a couple of processes, we end up with a large outcome O1 with D digits where D is kind of large, say D>=4, i.e., O1 > 999 (If we cannot even reach such a large outcome, it means all outcomes are bounded by 999 ==> loop exists). We can easily see that after processing O1, the new outcome O2 can be at most 9^2D < 100D, meaning that O2 can have at most 2+d(D) digits, where d(D) is the number of digits D have. It is obvious that 2+d(D) < D. We can further argue that O1 is the maximum (or boundary) of all outcomes afterwards. This can be shown by contradictory: Suppose after some steps, we reach another large number O3 > O1. This means we process on some number W <= 999 that yields O3. However, this cannot happen because the outcome of W can be at most 9^23 < 300 < O1.

这个证明总体来说非常聪明和完整. 一个小的改动是: suppose O3 to be the first number that exceeds O1. 这样我们才能说W <= 999.

题外话, 刚开始没有想出来正确答案的时候, 用这个代码来举例子:

int res = n;  
while (res != 1) {  
    n = res;  
    res = 0;  
    while (n > 0) {  
        int digit = n % 10;  
        res += digit * digit;  
        n = n / 10;  
    }  
}

这个代码刚开始都不觉得很好写, 因为你第二个 iteration 的 beginning 要干的事情和最开始第一个 iteration 之前要干的事情是不一样的.
解决的办法就是 res 的 init 放在 loop 里面; 在 loop 外面让 res 记录 n, 然后在第一个iteration 之前开始进行正式的 init.
当然这个问题还有其他的解决思路, 比如可以用do while来解决(有点在于把第一个termination condition的判断放到了 iteration1的后面); 另外一个最直接的办法是把 while 的header 直接改成 true(也就是无视), 然后在 body 里面加 break 之类的出口. 达到的效果其实是类似的, 就是让第一次 condition 的判断在第一次执行 body 之后才发生.

基于这个代码, 我尝试写了一个算法:

public class Solution {  
    public boolean isHappy(int n) {  
        int res = n;  
        while (res > 10) {  
            n = res;  
            res = 0;  
            while (n > 0) {  
                int digit = n % 10;  
                res += digit * digit;  
                n = n / 10;  
            }  
        }  
        if (res == 1) return true;  
        return false;  
    }  
}

这个算法看起来是对的, 不过其实有问题, 7就出问题了. //看 ver2, 这个思路居然是对的, 而且是最优解;

Problem Description

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
Credits:
Special thanks to @mithmatt and @ts for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:40.36%
Contributor: LeetCode
Companies
uber airbnb twitter
Related Topics
hash table math
Similar Questions
Add Digits Ugly Number