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