String matching with stacks (valid parentheses)

Problem: given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective. A valid string must meet the following requirements: The left parenthesis must be closed with the same type of the right parenthesis. The left parentheses must be closed in the correct order.

Use the data structure of the stack, push the left parenthesis into the stack in turn, and see if the end of the stack matches the right parenthesis. If so, take out the end of the stack. Otherwise, the input is judged unreasonable. (Just use the array push and pop methods to implement the last in, first out of the stack, later we can implement the stack of common methods encapsulated in a constructor ~)

function judgeValidBracket(str){ let bracket={ "{":"}", "[":"]", "(":")" } let arr=str.split(''); let bracketArr=[]; // temporary stack array for(let I =0; i<arr.length; I ++){for(let key of BRACKET){if(arr[I]==key){bracketarr.push (arr[I])} Else else if(arr[I]! =bracket[bracketArr.pop()]){ return false } } } return true; } let STR ="{[]}"; / / / / parameter judgeValidBracket (STR) trueCopy the code

Merges two ordered lists

Problem: Merge two ascending lists into a new ascending list and return. A new list is formed by concatenating all the nodes of a given two lists.

Parameters: L1 (head node of list 1), L2 (head node of list 2)

class Node{
 constructor(val){
 this.val=val;
 this.next=null
 }
}
Copy the code

Solution a:

Create a new list, loop the two lists one by one, and put the smaller one in the new list until the two lists end.

function concatLists(l1,l2){ let temp=new Node(); // The merged list (virtual head node) let cur=temp; // The merged list points to while(l1! =null&&l2! =null){ if(l1.val>l2.val){ cur.next=l2; l2=l2.next; }else{ cur.next=l1; l1=l1.next; } cur=cur.next; }} next=l1? l2:l1; return temp.next;Copy the code

Method 2:

Idea: use recursive method, directly change the original linked list pointing, return the list with small head node.

Function getCurNode(l1,l2){if(l1==null)return l2; if(l2==null)return l1; if(l1.val>l2.val){ l2.next=getCurNode(l1,l2.next); return l2 }else{ l1.next=getCurNode(l1.next,l2); return l1 }Copy the code

Count sorting

(For the limited size of items, a larger space will be sacrificed)

Algorithm idea: place the number n in the NTH bucket of the new array, fill the target array, place each element I in the C(I) item of the new array, and subtract 1 from C(I) for each element.

Implementation:

function countSort(arr) { let maxValue=0; For (let I =0; i<arr.length; i++){ maxValue=maxValue<arr[i]? arr[i]:maxValue; } let bucketArr =new Array(maxValue + 1); let sortIndex = 0; For (let I = 0,len=arr.length; i < len; i++) { if (! bucket[arr[i]]) { bucket[arr[i]] = 0; } bucket[arr[i]]++; } for (let j = 0,len= bucketarr.length; j < len; j++) { while(bucket[j] > 0) { arr[sortedIndex++] = j; bucket[j]--; } } return arr; }Copy the code

Binary tree forward traversal

Class Node{constructor(data,left,right){this.data = data; this.left = left; this.right = right; } show(){ return this.data; } } class BST{ constructor(){ this.root = null; Insert (data){var node = new node (data,null,null); if(this.root == null){ this.root = node; }else{ var current = this.root; var parent; while(true){ parent = current; if(data < current.data){ current = current.left; if(current == null){ parent.left = node; break; } }else{ current = current.right; if(current == null){ parent.right = node; break; }}}}} / / sequence traversal preOrder first (node) {if (node) {the console. The log (node. The show () + ""); this.perOrder(node.left); this.perOrder(node.right); Var BST = new BST(); var nums = []; // for(var I = 0; i < nums.length; i ++){ bst.insert(nums[i]); } bst.perOrder(bst.root);Copy the code