Leecode快乐数

小感触 2020年03月11日 207次浏览

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

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

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

自己的解题思路:

  • 根据题意,使用一个简单的递归,简化反复获取每一位数据计算平方和的过程。
  • 如果无线循环,那么计算结果会形成闭环,结合一个Set存储之前已经计算过的数据,判断是否形成了闭环。
class Solution {
    LinkedHashSet<Integer> his = new LinkedHashSet<>();
    public boolean isHappy(int n) {
	//当前要计算的值已经存在历史记录中,形成了闭环,不是快乐数。
        if (his.contains(n)) {
            return false;
        }
	//抽取每一位,计算平方和。
        int nn = n;
        int v = 0;
        while (n != 0) {
            v += Math.pow(n % 10, 2);
            n /= 10;
        }
	//条件成立出口
        if (v == 1) {
            return true;
        }
	//当前计算不成立,加入历史记录,进行下一次递归
        his.add(nn);
        return isHappy(v);
    }
}

学习一种解题思路:

不是快乐数的数称为不快乐数(unhappy number),所有不快乐数的数位平方和计算,最後都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中

  • 针对非快乐数会陷入闭环的问题,这里不使用Set记录,而是直接模拟两个指针进行在这个可能形成闭环的路上计算。
  • 两个计算指针一快一慢,但都是计算当前数据的平方和,不过是慢指针需要机选两次的工作,快指针一次就计算完成了。相当于快指针走2步,慢指针走1步。
  • 如果这个数据是不快乐数,那么快指针肯定会超越慢指针一周并等于它。如果相等时候发现快慢指针的值不是1,说明陷入了死循环。那么就不是快乐数据。

假设上面的循环,计算平方和:
|第几次计算|慢指针平方和|快指针平方和|
|----|-----|-----|
|1|4|16|
|2|16|58|
|3|37|145|
|4|58|20|
|5|89|16(注意快指针已经是第二圈了)|
|6|145|58|
|7|42|145|
|8(相遇)|20|20|

class Solution {
    public boolean isHappy(int n) {
	//慢指针,一次计算一次数据的平方和。
        int slow = trans(n);
	//快指针,一次计算两次数据的平方和。
        int fast = trans(trans(n));
        while (true) {
	    /**
	      两指针继续步进,无论如何,都会相等,
	      要么是陷入1的死循环,此时是快乐数。
	      要么是陷入4->16->37->...的非快乐数循环。
	    */
            slow = trans(slow);
            fast= trans(trans(fast));
            if (slow == fast) {
                return slow == 1;
            }
        }
    }
    public int trans(int n) {
        int v = 0;
        while (n != 0) {
            v += Math.pow(n % 10, 2);
            n /= 10;
        }
        return v;
    }
}

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/happy-number