Topic describes

Write an algorithm to determine whether a number n is a happy number.

Happiness number is defined as:

For a positive integer, replace the number each time with the sum of squares of the numbers at each of its positions. And then you repeat the process until the number is 1, or it could go on forever but it never gets to 1. If you can change it to 1, then that number is happiness. Return true if n is the happy number; If not, return false.

Happy leetcode – 202 number

Subject analysis

We can use the idea of linked list to translate the following question:

When the process ends up at 1, analogous to a list with no rings, 1 is the last empty node

When this goes on forever but never gets to one, you can think of it as a linked list with a loop

1. (Map)

Since you can use the idea of a circular list to solve the problem, then the method of solving the problem is the same as the solution of a circular list, not clear can see my previous article [Luffy]_ circular list [Luffy]_ circular list II

code

/ * * *@param {number} n
 * @return {boolean}* /
var isHappy = function(n) {
    if (n === 1) return true
    const mapper = new Map(a)let p = getNext(n)
    while(p ! = =1) {
        if(! mapper.has(p)) { mapper.set(p, p) p = getNext(p) }else {
            return false}}return true
};

var getNext = function(n) {
    let sum = 0
    while(n) {
        sum += (n % 10) * *2
        n = Math.floor(n / 10)}return sum
}
Copy the code

Fast and slow pointer method

code

/ * * *@param {number} n
 * @return {boolean}* /
var isHappy = function(n) {
    if (n === 1) return true
    let p = getNext(n)
    let q = getNext(getNext(n))
    while(p ! == q && q ! = =1) {
        p = getNext(p)
        q = getNext(getNext(q))
    }
    return q === 1
};

var getNext = function(n) {
    let sum = 0
    while(n) {
        sum += (n % 10) * *2
        n = Math.floor(n / 10)}return sum
}
Copy the code