20200301：快乐数（leetcode202）

快乐数

• 题目
• 思路与算法
• 代码实现

题目

思路与算法

1. 楼下太吵，刷个简单的，这题本身没有任何难点，非要说难点就在如何判断这个数的各个位平方和会不会变成死循环，一直加下去，举个例子：
2. 25，这个数往下加，29->85->89->145->42->20->4->16->37->58->89如此，这个89重复出现了，意味着进入了循环，所以我们只需要判断如何跳出循环即可，因此想到利用哈希表的数据唯一性来实现。
3. 方法二为大佬的快慢指针法，也列出来，非常nb的破除循环的方法。

代码实现

方法一：哈希表解法

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<>();
        set.add(n);
        while(n > 1){
            n = bitSum(n);
            if(set.contains(n)){
                 return false;
            }  
            set.add(n);
        }
        return true;
    }
    // 获取其逐位数字的平方和
    private int bitSum(int n){
        int sum = 0;
        int num;
        while(n != 0){
            num = n%10;
            n /= 10;
            sum += num*num;
        }
        return sum;
    }
}
           

方法二：快慢指针法

class Solution {
    public boolean isHappy(int n) {
       int fast,slow;
       fast = n;
       slow = n;
       // 此处需要先执行一次，因此使用do while
       do{
           slow = bitSum(slow);
           fast = bitSum(fast);
           fast = bitSum(fast);
       }while(slow != fast);
       return slow == 1;
    }


    // 获取其逐位数字的平方和
    private static int bitSum(int n){
        int sum = 0;
        if(n == 0){
            return 0;
        }
        while (n > 0){
            int i = n % 10;
            sum += i*i ;
            n /= 10;
        }
        return sum;
    }
}