LeetCode 202. Happy number

202. Happy number

difficulty Simple

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 this process The result is 1, So this number is the happy number .

If n yes Happy number Just go back to true ; No , Then return to false .

Example 1：

 Input ：n = 19
 Output ：true
 explain ：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2：

 Input ：n = 2
 Output ：false

Answer key

​ This problem looks very simple , Is to split the number , Then add the squares of these numbers , If it is equal to 1 Just go back to true, Can't return 1 Just go back to false. But I've been thinking about a problem , If not equal to 1 Will it be infinite and fall into a dead circle , I didn't understand this problem at first .

• Will it be infinite

  The answer is no , Please refer to the official explanation Happy number - Happy number - Power button （LeetCode）

  [ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-TEU7mDU1-1654571171236)(C:\Users\12447\AppData\Roaming\Typora\typora-user-images\image-20220607104722751.png)]

  ​ You can find , When it comes to 4 When it comes to digits ,next It becomes 3 digit , When it comes to 13 When it comes to digits ,next It becomes 4 digit , Are getting smaller .

• Will it fall into a dead circle ,

  The answer is, of course ,4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

Solution 1

​ First we need to find the sum of the squares of each digit , We can write a function to get the sum of squares of digits , The function is to go to the number of single digits each time （n%10）, then n Again out of 10, know n Less than 0.

​ Then there is another problem , What to do when you fall into a dead circle , The official solution uses set duplicate removal , When set Contained in the n When , It shows that we are in a dead circle , Why can't we get there 1, Just exit and go back false.

class Solution {
    
    private int getNext(int n){
    // Sum of squares of digits 
        int count = 0;
        while(n > 0){
    
            count += (n % 10) * (n % 10);
            n /= 10;
        }
        return count;
    }

    public boolean isHappy(int n) {
    
        Set<Integer> set = new HashSet<>();//set duplicate removal 
        while(n != 1 && !set.contains(n)){
    //n It's not equal to 1, And set Do not include this number 
            set.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
}

Solution 2

​ The official solution to the second question gives the method of speed pointer , It's interesting . First of all, let's understand what the fast and slow pointer method is , The fast and slow pointer method is a method to judge whether a loop has been generated , You can move the fast or slow pointer to determine whether an dead loop has occurred . The principle is , Because the fast pointer moves fast , It will catch up with the slow pointer , When both the fast pointer and the slow pointer point to the same number , It means that a cycle is generated .

class Solution {
    
    private int getNext(int n){
    // Sum of squares of digits 
        int count = 0;
        while(n > 0){
    
            count += (n % 10) * (n % 10);
            n /= 10;
        }
        return count;
    }

    public boolean isHappy(int n) {
    
        int slow = n;// Slow pointer 
        int fast = getNext(n);// Quick pointer 
        while(fast != 1 && slow != fast){
    // When the fast pointer has not arrived 1, The fast pointer has not caught up with the slow pointer 
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }
        return fast == 1;
    }
}