After the five sorting questions last time, I did five more questions today to record my process of doing questions and thinking. Next time, I will record the method after finishing and optimizing. This record is mainly to record the first reaction I saw these questions, because do less, so the first reaction is often not so accurate, practice makes perfect.

Bracket validity judgment

This is LeetCode number 20. It’s easy.

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

A valid string must meet the following requirements:

1. An open parenthesis must be closed with a close parenthesis of the same type.

2. The left parentheses must be closed in the correct order.

   Example 1: Input: s = “()” Output: true Example 2: Input: S = “()[]{}” Output: true Example 3: Input: s = “(]” Output: false Example 4: Input: s = “([)]” Output: false

This is a classic stack algorithm, and if we look at it this way, like in a bucket, first in, last out, last in, first out, if the first one is to the right of the parentheses, it must be wrong, because the parentheses are 100% unpaired. If it’s on the left, we’ll put it in, if it’s on the right, we’ll see if the last one is on the left, if it is, we’ll take it out, cancel it out in pairs, and we’ll keep putting it in, and if it’s not on the left, we’ll return FALSE, because these two don’t match, they’ll never match. That’s it.

So my code looks like this.

function symbol(str) { let arr = str.split(","); let res = []; // Let len = 0; For (let I = 0; i < arr.length; I++) {switch (arr [I]) {/ / if it is on the right side, find a case on the "} ": if (res[len - 1] == '{') { res.pop() len-- } else { return false } break; case "]": if (res[len - 1] == '[') { res.pop() len-- } else { return false } break; case ")": if (res[len - 1] == '(') { res.pop() len-- } else { return false } break; default: // if it is left, fill res.push(arr[I]) len++ break; If (res.length == 0) {return true} else {return false}}Copy the code

Merge sort linked lists

Given an array of linked lists, each list is already sorted in ascending order.

Please merge all lists into one ascending list and return the merged list.

Example 1: input: lists = [].enlighened by [1 4], [2, 6]] output:,1,2,3,4,4,5,6 [1] : list array is as follows: [1 - > > 5, 4-1 - > 3 - > 4, 6] 2 - > merge them into an ordered list. 1 - > 1 - > 2 - > 3 - > 4 - > 4 - > 5 - > 6 example 2: input: lists = [] output: [] example 3: input, output lists = [[]] : []Copy the code

This problem, without too much explanation, is to combine multiple lists into one. Since each list is ordered, we compare the val of each list, select the smallest one, take it out, and fill it in our new list until all the values are filled in.

However, there is a problem, there is no linked list in our JS data type, which is also very confusing to me at the beginning of this problem. At that time, I did not know that this should be written by myself, now we will first implement, how to change from array to link

ListNode = function (val) {this.val = val; this.next = null; } // array->link generateLink = function (array) { const fakeHead = new ListNode(0); // let current = fakeHead; For (let I = 0; i < array.length; i++) { current.next = { val: array[i], next: null }; // Set the pointer to next of the current list, so that the next assignment will be to next of the current list. Next} return fakeHead. Next} // link->array exports. GenerateArray = function (link)  { let arr = []; while (link) { arr.push(link.val); link = link.next; } return arr; }Copy the code

So now that we’ve implemented the process of converting an array to a linked list ourselves, it’s time to implement the code

Let lists = [[1, 4, 5], [1, 3, 4], [2, 6]] // Change each item in array to a list lists. Map ((v, I) => {lists[I] = generateLink(v)}) set an initial list let list = {val: null, next: null} let link = list contrast(lists); Let arr = generateArray(list.next) console.log(arr); function contrast(lists) { if (lists.length == 0) return; let len = lists.length; let minVal = Infinity; let index = 0; For (let I = 0; i < len; i++) { if (lists[i] && lists[i].val < minVal) { minVal = lists[i].val; index = i; }} // If found, assign if (minVal! = Infinity) { link.next = { val: minVal, next: null } link = link.next; } // If null is found, delete the item from the array. If not null, next. If (lists[index] == null) {lists. Splice (index)} else {lists[index] = lists[index]. Next; } // loop next time to find contrast(lists)}Copy the code

Count sorting

In plain English, find the largest number in the array arr and treat it as the largest subscript of the new array arr1.

It then iterates all the numbers in arR to subscripts of ARR1, and the values of arR1 subscripts are subscripts that appear in ARR

The number of times. We said arr = [5, 7, 4, 7, 8, 2, 1, 3], arr1 [0, 1, 1, 1, 1, 1, 0, 2, 1].

Arr1 is represented by zero zeros, one one, one two, one three, one four, one five, zero six, two seven, and one eight

Then create a new array of the same length as ARR, and fill it with the number of times subscript ARr1

So to implement a counting sort, and a total of steps

1. Create two new arrays,res for the return value and list for the count

2. Find the largest number in arR, which represents the largest subscript of list

3. Loop through the array, fill in the list

4. Based on the list and arR, fill in the RES

   function countSort(arr) { let len = arr.length; let res = []; Let list = []; // let Max = 0;

   for (let i = 0; i < len; If (arr[I] > Max) Max = arr[I]} for (let I = 0; i < len; i++) { list[arr[i]] = list[arr[i]] ? List [arr[I]] + 1:1} for (let I = 0; i < list.length; i++) { while (list[i] > 0) { res.push(i); list[i]– } } console.log(res); }

Number of valid palindromes

Given an integer x, return true if x is a palindrome integer; Otherwise, return false.

Palindromes are integers that read in positive (left to right) and backward (right to left) order. For example, 121 is palindrome and 123 is not.

Example 1: Input: x = 121 Output: true Example 2: Input: x = -121 Output: false Description: The value is -121 read from left to right. Read from right to left, 121-. So it's not a palindrome number. Example 3: Input: x = 10 Output: false Description: Read from right to left, the value is 01. So it's not a palindrome number.Copy the code

There are a lot of ways on the Internet to invert the numbers and compare them, but what I understand is that you pair the heads and the tails, and when you pair them, you get.

function palindrome(arr) { let arr1 = arr; let len = arr.length; for (let i = 0; i < Math.floor(len / 2); If (arr[I]! = if (arr[I]! = if (arr[I]! = arr1[len - 1 - i]) return false } return true; }Copy the code

The former sequence traversal

Give you the root node of the binary tree, root, and return a pre-traversal of its node value.

Input: root = [1,null,2,3] output: [1, 3]Copy the code

Input: root = [1,2] output: [2]Copy the code

Input: root = [1, NULL,2]Copy the code

Pre-order traversal is traversal of a binary tree in the order of root, left, and right, and the whole tree and the subtree are in that order.

For example, in the graph above, the preceding traversal is [F,C,A,D,B,E,H,G,M]

When the root of F is [F, left [C,A,D,B], right [E,H,G,M]];

[F, root C, left A, right [D,B],E,H,G,M];

[F,C,A,D,B, root E, left H, right [G,M]]

So it makes sense that every time we have to find the root, then we have to find the left tree, and after we find the root of the left tree, if the left tree still has the left tree, then we have to keep going, and then we have to find the right tree.

Before we can implement a pre-order traversal, we will first implement a binary tree from the array itself.

Before we can do that, we need to know what a binary tree is, and a binary tree simply means that every root has to have a smaller left hand side than the root, and every root has to have a bigger right hand side than the root, right

Let STR = "1, 2,3" let arr = str.split(',').map(Number) const tree = convertBinaryTree(arr); function convertBinaryTree(arr) { let root; let insertNode = function (parentNode, childNode) { if (! childNode || childNode.val == '') return; Val < parentNode.val) {if (parentNode.left === null) parentNode.left = childNode; else insertNode(parentNode.left, If (parentNode.right === null) parentNode.right = childNode; else insertNode(parentNode.right, childNode) } } arr.forEach(val => { let node = { val: val, left: null, right: null } if (root) insertNode(root, node); else root = node }) return root }Copy the code

Now we are going to implement our code

Function preOrderTraversal(tree) {res.push(tree.val) traversal (tree) preOrderTraversal(tree.left); // If (tree.right) preOrderTraversal(tree.right); // Go to the left side, go to the right side}Copy the code

My understanding may have a deviation, there may be insufficient place, I hope you criticize and correct, this is my above my whole understanding of the topic.