LeetCode---快乐数的多种解法（Java）

分手后的思念是犯贱 2022-01-26 11:07 281阅读 0赞

今天你快乐了吗？

谨以此篇文章记录快乐数的解法

## 题目： ##

编写一个算法来判断一个数是不是“快乐数”。

一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

示例：

>     输入: 19
>     输出: true
>     解释: 
>     12 + 92 = 82
>     82 + 22 = 68
>     62 + 82 = 100
>     12 + 02 + 02 = 1

我们以上面的示例来思考一下

19是快乐数，返回true

判断19为快乐数的依据是将19拆分开，计算每位数字的平方和，然后重复此运算。直到平方和恒为1，则确认为快乐数；否则，就不是快乐数。

那我们就可以根据以上思路设计解题算法（以下解法都是Java语言）

## 解法一 ##

此解法思路是使循环计算“n"的平方和，直至平方和恒等于一个值。然后判断这个值是否为1。

时间复杂度为O(n)

class Solution {
        public boolean isHappy(int n) { 
            int slow=sum_happy(n),fast=sum_happy(sum_happy(n));   //slow为n的每个数字的平方和，fast为slow的每个数字的平方和
            while(slow!=fast){           //直到平方和恒为一个数结束循环
                slow=sum_happy(slow);
                fast=sum_happy(sum_happy(fast));
            }
            return slow==1;          //如果平方和为1，则是快乐数
        }
        private int sum_happy(int n){          //计算n的每个数字的平方和
            int sum=0;
            while(n!=0){               
                int b=n%10;              //用取余的方法取出每个数字
                sum=sum+b*b;
                n=n/10;        //更新n
            }
            return sum;
        }
    }

## 解法二 ##

快乐数的反面则是不快乐数，不快乐数进行每位平方和计算到最后都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中（我也不是很懂为什么进入这个循环）。

class Solution {
        public boolean isHappy(int n) {
            if(n==4||n==16||n==37||n==58||n==89||n==145||n==42||n==20)   //不快乐数
                return false;
            int reply=sum_happy(n);           //计算平方和
            if(reply==1)             //平方和为1则是快乐数
                return true;
            return isHappy(reply);
            
        }
        private int sum_happy(int n){          //计算n的每个数字的平方和
            int sum=0;
            while(n!=0){               
                int b=n%10;              //用取余的方法取出每个数字
                sum=sum+b*b;
                n=n/10;        //更新n
            }
            return sum;
        }
    }

## 解法三 ##

此方法利用了数据集合HashSet，当然，也可以用ArrayList、LinkedList，但HashSet效率较高，而且HashSet里不包含重复元素。以下利用了contains()方法判断数据集合set里是否包含重复元素，即判断此次平方和是否和前面计算过的平方和相同，如若不同，则将这个值添加进集合set中，直至这个值为1。

class Solution {
        public boolean isHappy(int n) {
            Set<Integer> set = new HashSet<>();    //数据集合
            set.add(n);
            while(n!=1){          
                int sum=0;
                while(n/10!=0){   //平方和
                    int t=n%10;
                    sum=sum+t*t;
                    n=n/10;
                }
                n=sum+n*n;     //n为原来的n的每位平方和
                if(set.contains(n)){        //判断set里是否包含和n相同的数
                    return false;
                }
                set.add(n);
            }
            return true;
        }
    }

## 解法四 ##

和解法三同理，只是将HashSet换成了ArrayList

class Solution {
        public boolean isHappy(int n) {
            List<Integer> list=new ArrayList<>();   //数据集合
           while(n!=1){
               int sum=0;
               while(n>0){
                   int b=n%10;
                   sum=sum+b*b;
                   n=n/10; 
               }           
               n=sum; 
               if(list.contains(sum)) 
                   break;
             list.add(sum);
           }
        return n==1;
        }
    }

快乐数当然不止这些解法，但大致思路都是这样的，这里只提供了我所了解的解题方法，如果有错误的地方，欢迎指出

人生苦短，快乐就好