Happy Number

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 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1

此题有两个关键，一个是如何将一个数一位一位的拆开进行平方和求解。一个是如何较为快速的判断在这个过程中有没有出现循环，或平方和是不是1。 c语言版本 对于求解一个数的各位平方和，可以采用一直除10取余数的方法，对于happy number的判断，我还是采用了哈希表的方法，就是将每一次的平方和放入哈希表中，当然在放的时候先检查一下，该数值是否为1，为1就直接返回true，证明这个数是个happy number.还要判断一下这个数是否在哈希表中已经存在了，如果已经存在了就不要放入哈希表中，并且返回false,因为说明结果产生了循环。

bool isHappy(int n) {
    int hash[1024],hashlength=1024,hashAddress1,sum=0;
    memset(hash,-1,sizeof(hash));

    while(sum!=1){
        //计算一个整数各个位的和,sum的值就是和值。
        while(n>0){
            sum += (n%10)*(n%10);
            n = n/10;
        }

        if(sum == 1){
                return true;
            }
        //将值映射到哈希表上 
        hashAddress1 = sum % hashlength;
        if(hash[hashAddress1]==sum){
            return false;
        }
        while(hash[hashAddress1]!=-1){
            hashAddress1 = (++hashAddress1)%hashlength;
            if(hash[hashAddress1]==sum){
                return false;
            }
        }
            hash[hashAddress1] = sum;
            n = sum;
            sum = 0;
    }

}

java版本 跟c的思路一样，只是java有HashSet接口，所以写起来没c麻烦. 所以我正好学习了一下HashSet 。HashSet是基于HashMap实现的，HashSet底层采用HashMap来保存所有的元素。所以放入HashSet中的集合元素实际上是由HashMap的Key来保存，而HashMap的value存储了一个PRESENT，是一个静态的Object对象。

public boolean isHappy(int n) {
        long ln = n;
        Set<Long> set = new HashSet<Long>();
        long sum = 0;
        while(sum!=1){
            sum = 0;
            while(ln>0){
            //求ln%10的平法
                sum+=Math.pow(ln%10, 2);
                ln = ln/10;
            }
            if(sum == 1){
                return true;
            }
            //检查集合中是否已经存在sum
            if(set.contains(sum)){
                return false;
            }
            set.add(sum);
            ln = sum;
        }
        return false;
    }

更精短的c语言实现方法 利用的是一个fact：所有[2,6]的数字都不是happy number,还有一个数学发现就是，所有不以1结束的数字，都会以4结束无尽循环，（4->16->37->58->89->145->42->20->4）所谓的快乐数与不快乐数，都只是数学家们观察而发现的，现在还没有什么用处，也没有证明。以下就是用上述事实来进行的程序判断

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