Leetcode question brushing: hash table 03 (happy number)

Force button topic link

Write an algorithm to judge a number n Is it a happy number .

「 Happy number 」 Defined as ： For a positive integer , Replace the number with the sum of the squares of the numbers in each of its positions , Then repeat the process until the number becomes 1, It could be Infinite loop But it doesn't change 1. If It can be 1, So this number is the happy number .

If n If it's happy, count it back True ; No , Then return to False .

Example ：

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

package com.programmercarl.hashtable;

import java.util.HashSet;

/** * @ClassName IsHappy * @Descriotion https://leetcode.cn/problems/happy-number/ * @Author nitaotao * @Date 2022/6/20 16:14 * @Version 1.0 *  Happy number  **/
public class IsHappy {
    
    public static void main(String[] args) {
    
        System.out.println(isHappy(19));
    }
    public static boolean isHappy(int n) {
    
        /** *  Each calculated result is added to set aggregate , If there is repetition , Then it falls into a cycle , Is unhappy  */
        HashSet<Integer> set = new HashSet<>();
        // If this number doesn't appear 
        while (!set.contains(n)) {
    
            // Record this number 
            set.add(n);
            int sum = 0;
            while (n / 10 != 0) {
    
                sum += (n % 10) * (n % 10);
                n = n / 10;
            }
            sum += n * n;
            if (sum == 1) {
    
                return true;
            }
            n = sum;
        }
        // If there has been , It enters the cycle 
        return false;
    }
}

To tell you the truth, I had no idea at first , Then I looked at the solution , A word awakens the dreamer .

Ideas

The subject looks like a mathematical problem , It's not ！

There is a meeting in the title Infinite loop , So in other words In the process of summation ,sum It's going to repeat itself , It's very important to solve the problem ！

So this topic uses the Hashi method , To judge this sum Whether it occurs repeatedly , If it's repeated, that's it return false, Otherwise, keep finding sum by 1 until .

Welcome to accompany me Brush problem