This is the 18th day of my participation in the August Genwen Challenge.More challenges in August

If you are interested in JavaScript, please continue to brush the list

One, happy tree

202. Happiness

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.

Example 1:

Input:19Output:trueExplanation:12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Copy the code

Example 2:

Enter n =2Output:false
Copy the code

Tip:

1 <= n <= 231 – 1

Source: LeetCode link: leetcode-cn.com/problems/ha… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

When the calculated value circulates indefinitely, it can never change to 1, and can only get 1 if it does not circulate.

Therefore, the calculated value can be regarded as the linked list node. If there are repeated values, it is equivalent to the linked list has rings. Fast or slow Pointers can be used to judge.

The fast or slow pointer moves backwards, and returns true when the fast pointer is 1. Return false if the list has loops that never reach 1.

Code implementation

/ * * *@param {number} n
 * @return {boolean}* /
// Get the sum of squares of the numbers at each position
var getSum = function(n) {
    let sum = 0;
    while(n) {
        sum += (n % 10) * (n % 10);
        n = Math.floor(n / 10);
    }
    return sum;
}
var isHappy = function(n) {
    let slow = n;
    let fast = getSum(n);
    while(fast ! =1&& slow ! = fast) { slow = getSum(slow); fast = getSum(getSum(fast)); }return fast == 1;
}
Copy the code

Reverse linked lists

206. Reverse linked lists

Given the head node of a single linked list, reverse the list and return the reversed list.

Example 1:

Enter: head = [1.2.3.4.5] output: [5.4.3.2.1]
Copy the code

Example 2:

Enter: head = [1.2] output: [2.1]
Copy the code

Example 3:

Input: head = [] Output: []Copy the code

Tip: The number of nodes in the list is in the range of [0, 5000] -5000 <= node. val <= 5000. Can you solve the problem in two ways?

Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

When the calculated value circulates indefinitely, it can never change to 1, and can only get 1 if it does not circulate.

Therefore, the calculated value can be regarded as the linked list node. If there are repeated values, it is equivalent to the linked list has rings. Fast or slow Pointers can be used to judge.

The fast or slow pointer moves backwards, and returns true when the fast pointer is 1. Return false if the list has loops that never reach 1.

Code implementation

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {
    let pre = null;
    let cur = head;
    while(cur) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
};
Copy the code