LeetCode精选TOP面试题202.快乐数

2020-03-17
阅读量 | 字数：753字 | 预计阅读时长：3分钟

题目描述

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

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

解题思路

这是一个在编程的时候会出现死循环的问题，个人认为重点工作其实倒不是怎么判断是不是快乐数，而是找到打破循环的方法或者条件。

思路1 ：快慢指针
慢指针slower每次前进一步（进行一次平方计算），快指针faster每次前进两步（进行两次平方计算），当slower和faster不相等的时候，就一直循环。那为啥还说能打破循环呢？
这是因为当快慢指针相等的时候会停止循环，相等的有两种情况：
- 当慢指针和快指针都通过计算变成了1；
- 当慢指针走过一圈之后，快指针肯定恰好走过了两圈，如果不是快乐数，快慢指针的值肯定是相同的；
  
  之所以选择快指针走两步而不是三步四步，是因为1，2公倍数最小，公约数最多，这样最节省空间和时间
思路2 ：借助HashSet
哈希Set特点就是不允许重复，那只要每次求和之后，判断当前的值n是否已经存在于hashset中就好啦，存在就不是快乐数，直接return false，不存在就添加进hashset，直到n 变成1跳出循环，或者返回false。
思路3 ：投机取巧
小于10的数中，只有1和7是快乐数，借鉴leetcode上大神的思路，所以，投机取巧就很简单了:
- 只要每次计算得到的n大于10，那么就继续计算;
- 每次计算得到的n小于10，如果等于1或者7，就是快乐数，不等就不是。

代码实现(Java)

/**
 * @author : flower48237
 * @2020/3/16 20:38
 * title : LeetCode精选TOP面试题202.快乐数
 */
public class Solution3 {
    public boolean isHappy(int n) {
    	// 法 1 -- 快慢指针
        int slower = n;
        int faster = n;
        do {
            slower = getSqrtSum(slower);
            faster = getSqrtSum(faster);
            faster = getSqrtSum(faster);
        }while (slower != faster);
        return slower == 1;// 返回slower和1是否相等的判定值
        
    	// 法 2 -- 借助HashSet
        HashSet<Integer> hashset = new HashSet<Integer>();
        hashset.add(n);
        if (n == 1){
            return true;
        }
        while (n != 1){
            n = getSqrtSum(n);
            if (hashset.contains(n)){
                return false;
            }
            hashset.add(n);
        }
        return true;
        
        // 法 3 -- 投机取巧
        while (true){
            if (n < 10){
                if (n == 1 || n == 7) {
                    return true;
                }else {
                    return false;
                }
            }
            n = getSqrtSum(n);
        }
    }
    // 三个方法都会用到的计算平方的步骤
    public int getSqrtSum(int num){
        int sum = 0;
        while (num > 0){
            int item = num % 10;
            sum += item * item;
            num /= 10;
        }
        return sum;
    }
}

本文作者： whtli
本文链接： https://hexo.whtli.cn/archives/f2d7b9d0.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。