java - 超过时间限制-查找快乐号码

我在leetcode上做了这个问题（如果是快乐的数字，则返回true），上面写着Time Limit Exceeded。

一个快乐的数字是由以下过程定义的数字：以任何正整数开头，用该数字的平方和代替该数字，然后重复该过程，直到该数字等于1（它将停留在该位置），否则它就会循环在不包含1的循环中无休止地循环。以1结尾的那些数字是快乐数字。

如果n是一个快乐数字，则返回True；否则返回False。

例：

Input: 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

class Solution {
    public boolean isHappy(int n) {
        int sum=n;
        while(sum!=1)
        {
        sum=sum_digits(n);
        }
        return sum==1;
    }
    public int sum_digits(int num){
        int sm=0;
        while(num!=0)
        {
            int d=num%10;
            sm=sm+d*d;
            num=num/10;
        }
        return sm;
    }
}

最佳答案

我找到了算法的答案。首先，我们应该说任何正数是“快乐”或“不快乐”。那些开心的人无论如何都会在结尾处给我们1，但是那些不开心的人会陷入循环，并且会有周期性的sum_digit()。因此，如果一个sum_digit()对于给定的数字n发生两次，那将不快乐！

public static boolean isHappy(int n) {
    int sum=n;
    List<Integer> history=new ArrayList<>();//for holding a list of numbers that have been reached
    while(sum!=1)
    {
        history.add(sum);
        sum=sum_digits(sum);
        if(history.contains(sum)){//if one the numbers in history repeats it will loop forever though n is not Happy
            return false;
        }
    }
    return sum==1;
}
public static int sum_digits(int num){
    int sm=0;
    int n=num;
    while(n!=0)
    {
        int d=n%10;
        sm=sm+d*d;
        n=n/10;
    }
    return sm;
}

现在，您可以使用它查找小于1000（或您希望的任何数字）的所有快乐数字：

public static void main(String[] args) {
  System.out.println(isHappy(999999));
  for (int i = 1; i < 1000; i++) {
        if (isHappy(i))System.out.println(i);
    }
}