java - 超过时间限制 - 寻找快乐的数字

Question

我在leetcode上做了这个问题(如果快乐数字则返回true)。它说超过时间限制。

快乐数字是通过以下过程定义的数字:从任何正整数开始，用其数字的平方和替换该数字，并重复该过程，直到该数字等于 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;
    }
}

Answer 1

我找到了算法的答案。首先，我们应该说任何正数要么是“快乐”，要么是“不快乐”。无论如何，高兴的都会在最后给我们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 的所有 Happy 数字(或您想要的任何数字):

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);
    }
}