LeetCode202-Happy Number

题目

Write an algorithm to determine if a number is “happy”.

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

分析

解法一:HashMap记录重复

该题题意非常容易理解,大致思路不外乎就是辗转相除、求各位的余数、做平方直至各位的平方和为1时停止。但有个很微妙的问题来了,我们很容易判定这个数是快乐数,但不容易判定它不是快乐数。通过观察可以发现,当这个数不停地产生新数字的时候我们应该等他一直计算更新,但一旦产生之前出现过的数字时,那么必然是死循环。因而解决办法就是增加一个记录用的HashMap,在循环内部,每得一个数字先查它是否已在HashMap,若不在说明是第一次出现,就加入HashMap;若在则产生死循环,返回false。

解法二:龟兔追赶

设定两个快慢指针,分别指向他们自己当前得到的数字,慢指针slow每轮做一次运算,快指针quick每轮做两次运算,显然会有两种情况产生(神奇的是两种方法在代码上可以地统一起来):

  • 不是快乐数:如果不是,那么一定存在死循环,即有类似n1->n2->n3->…->n2的环存在,那么这样总有一轮quick会追上slow,即quick == slow
  • 是快乐数:如果是,那么slow和quick最终一定都会收敛于1这个数,因为就算quick先到达1,quick会再多做几次运算,但每次运算的结果都是1,所以最后还是会有quick == short成立

代码

解法一

public class Solution {
    public boolean isHappy(int n) {
        Set<Integer> appeared = new HashSet<Integer>();
        while(n != 1){
            n = getSum(n);
            
            //判重 or 记录
            if(appeared.contains(n)) return false;
            else appeared.add(n);
        }
        
        return true;
    }
    
    //将n按位拆解,并求出每位的平方和返回
    int getSum(int n) {
        
        int sum = 0;
        int left = 0;
        while(n != 0){
            left = n % 10;
            sum += left * left;
            n = n / 10;
        }
        
        return sum;
    }
}

解法二

public class Solution {
    public boolean isHappy(int n) {
       
        int slow, quick;
        slow = quick = n;
        do {
            slow = getSum(slow);
            quick = getSum(quick);
            quick = getSum(quick);
        } while(slow != quick);
        
        return slow == 1 ? true : false;
    }
    
    //将n按位拆解,并求出每位的平方和返回
    int getSum(int n) {
        
        int sum = 0;
        int left = 0;
        while(n != 0){
            left = n % 10;
            sum += left * left;
            n = n / 10;
        }
        
        return sum;
    }
}

Leave a Comment.