Happy number [fast and slow pointer of ring PROBLEMS]

Preface

Analyze the meaning of the question , There are problems related to the dead cycle , It belongs to the ring problem , It needs to be solved with closely related knowledge points, fast and slow pointers . Keep the fast and slow pointer on the ring / The sensitivity of the dead cycle problem .

One 、 Happy number

Two 、 Speed pointer

package everyday.doublePoint;

//  Happy number 
public class IsHappy {
    
    /* target： Change one number into another , Follow a fixed path to change , Change to 1 Is the number of happy , Entering the dead circle is non block music number .  This is similar to a path that may have rings , May be acyclic .  The key is to determine whether there is a ring , Acyclic is happy number , If there is a ring, it is a non happy number .  The most intuitive idea is hash Record .  But for the ring problem , The knowledge point closely related to it is the speed pointer , If the speed pointer collides , There is a ring , Otherwise, the fast pointer goes to the end . */
    public boolean isHappy(int n) {
    
        //  Initialize the speed pointer position , Fast ahead , Slow again .
        int fast = getNext(n), slow = n;
        //  Quickly and slowly start looking .
        while (fast != 1 && fast != slow) {
    
            // fast Take two steps ,slow Take a step , If there are rings, they will collide , otherwise fast Come to the end 1.
            fast = getNext(getNext(fast));
            slow = getNext(slow);
        }
        //  Look, it's because the ring ends , Or because fast Go to the end .
        return 1 == fast;
    }

    private int getNext(int n) {
    
        int sum = 0;
        while (n > 0) {
    
            int mod = n % 10;
            sum += mod * mod;
            //  to update n
            n /= 10;
        }
        return sum;
    }
}

summary

1） Keep the fast and slow pointer on the ring / The sensitivity of the dead cycle problem .

reference

[1] LeetCode Happy number