basis

basis

Stack and queue:

  1. Infix expression change postfix expression

Two arrays, one stack to store the operator, and one output to store the result of the suffix expression

When encountering a number, output to output. When encountering an operator, if the priority is greater than the top of the stack, push it directly. If it is less than or equal to the top of the stack, pop the stack to output in turn until the operator is greater than the top of the stack. When brackets, pop the stack until the left bracket pops up

  1. Postfix expression calculation

An array that stores the operand meets the operand, pushes the stack to meet the operator, pops the top two elements of the stack, and pushes the calculation result onto the stack

  1. Circular queue

  2. Queue implemented by two stacks

//One input stack, one output stack /** * Initialize your data structure here. */ var MyQueue = function () { //One input stack, one output stack this .inStack = []; this .outStack = []; }; /** * Push element x to the back of queue. * @param {number} x * @return {void} */ MyQueue.prototype.push = function ( x ) { this .inStack.push(x); }; /** * Removes the element from in front of queue and returns that element. * @return {number} */ MyQueue.prototype.pop = function () { if (! this .outStack.length) { while ( this .inStack.length) { this .outStack.push( this .inStack.pop()) } } return this .outStack.pop(); }; /** * Get the front element. * @return {number} */ MyQueue.prototype.peek = function () { if (! this .outStack.length) { while ( this .inStack.length) { this .outStack.push( this .inStack.pop()) } } return this .outStack[ this .outStack.length- 1 ]; }; /** * Returns whether the queue is empty. * @return {boolean} */ MyQueue.prototype.empty = function () { return ! this .inStack.length &&! this .outStack.length; }; Copy code

Linked list:

  1. Reversed list
//Reverse order of the linked list: move 1~n to the front of the 0th one in turn function reverseLink ( head ) { if (!head || !head.next) return ; let pre = head, cur = head.next; while (cur) { pre.next = cur.next; cur.next = head; head = cur; cur = pre.next; } } Copy code
  1. Linked list ring entry

The two pointers start at the head at the same time, p1 walks 1 step at a time, p2 walks 2 steps at a time, the number of times when they meet is k of the ring, the second time p2 walks k steps first, and p1 is at the head. The two pointers start at the same time and walk one step at a time, and they meet The position is the entrance of the ring

Figure: 0. Basic concepts

Connected graph: any node i in the graph has a path to reach any node j. Strongly connected graph: a directed connected graph is a strongly connected graph connected component: an extremely connected subgraph of a non-connected graph

The number of edges in a connected graph is at least the number of nodes-1 The number of edges in a strongly connected graph is at least the number of nodes

  1. DFS of connected graph

Graph represented by adjacency matrix

function graphDFS ( g ) { let n = g.length, stack = [], visited = new Array (n), ans = [], count = 1 ; stack.push( 0 ); visited[ 0 ] = true ; ans.push( 0 ); while (stack.length) { let node = stack[stack.length- 1 ]; if (count == n) continue ; let i = 1 ; for (; i <n; i++) { if (!visited[i] && g[node][i] == 1 ) { stack.push(i); visited[i] = true ; //Visit node when pushing the stack ans.push(node); count++; break ; } } //This node has no unvisited subsequent nodes, pop up this node if (i == n) { stack.pop(); } } } Copy code
  1. BFS of connected graph
function graphBFS ( g ) { let n = g.length, queue = [], ans = [], visited = new Array (n + 1 ), count = 0 ; queue.push( 0 ); visited[ 0 ] = true ; while (queue.length) { let node = queue.shift(); ans.push(node); count++; if (count == n) continue ; for ( let i = 1 ; i <n; i++) { if (!visited[i] && g[node][i] == 1 ) { queue.push(i); visited[i] = true ; } } } } Copy code
  1. Disconnected graph DFS (general, suitable for connected)
function dfsGraph ( graph ) { let n = graph.length, visited = new Array (n), ans = []; function dfsVisit ( node ) { visited[node] = true ; ans.push(node); for ( let i = 0 ; i <n; i++) { if (!visited[i] && graph[node][i]) { dfsVisit(i); } } } for ( let i = 0 ; i <n;i++) { if (!visited[i]) { dfsVisit(i); } } return ans; } Copy code
  1. Non-connected graph BFS (general, suitable for connected)
function graphBFS ( graph ) { let n = graph.length, visited = new Array (n), ans = []; function bfsVisit ( node ) { let queue = [node]; while (queue.length) { let cur = queue.shift(); ans.push(cur); for ( let i = 0 ; i <n; i++) { if (!visited[i] && graph[cur][i]) { queue.push(i); visited[i] = true ; } } } } for ( let i = 0 ; i <n; i++) { if (!visited[i]) { bfsVisit(i); } } return ans; } Copy code
  1. Topological sort

Use a queue to find a node with an entry degree of 0 each time, and put it into the queue graph as an adjacency list

function topologicalSort ( graph ) { let n = graph.length, map = {}, queue = [], ans = []; for ( let i = 0 ; i <n; i++) { for ( let j = 0 ; j <graph[i].length; j++) { if (!map[j]) { map[j] = 1 ; } else { map[j]++; } } } for ( let i = 0 ; i <n; i++) { if (!map[i]) { queue.push(i); } } while (queue.length) { let node = queue.shift(); ans.push(node); graph[node].forEach( i => { map[i]--; if (map[i] == 0 ) { queue.push(i); } }); } return ans; } Copy code
  1. kruskal finds the minimum spanning tree

A graph with n nodes, initialized as n trees. Sort the edges in ascending order of weight and continuously traverse the edges. If the two nodes of the edge are not in the same set, add the edges, otherwise ignore

  1. prim finds the minimum spanning tree

All nodes are divided into two sets, A and B. Initialize the A set. Only the source node 0 is selected. Each time the edge with the smallest weight between A and B is selected, it is similar to dijkstra. Each iteration, the minimum distance from the source to the target node is updated.

  1. Single source shortest path dijkstra algorithm
function dijkstra ( graph ) { let n = graph.length, map = new Array (n), visited = new Array (n), count = 1 ; map[ 0 ] = 0 ; visited[ 0 ] = true ; let cur = 0 ; while (count <= n) { //relax adjacent nodes for ( let i = 0 ; i <graph[cur].length; i++) { if (!visited[i]) { //from Untouched if (!map[i]) { map[i] = map[cur] + graph[cur][i].weight; } else { map[i] = Math .min( map[i], map[cur] + graph[cur][i].weight ); } } } //Select the nearest node let min = 99999 , cur = -1 ; for ( let i = 0 ; i <n; i++) { if (!visited[i] && map[i] && map[i] < min){ min = map[i]; cur = i; } } visited[cur] = true ; count++; } return map; } Copy code
  1. Directed graph Euler path/Euler circuit

Euler path: A path in a directed graph that can pass through all edges without passing through an edge twice. The path back to the starting point is the Euler circuit.

Euler path: the out degree of the starting point is 1 greater than the in degree, the in degree of the end point is greater than the out degree, and the in degrees of other points are equal to the out degree

Euler circuit: all in-degree equals out-degree

//DFS the graph //Set the edge passed by as visited each time //The final boundless node is put into the stack function eulerPath ( graph ) { let stack = [], visited = {}; function dfs ( node ) { let i = 0 ; for (; i <graph[node].length;i++) { if (!visited[node + '_' + i]) { visited[node + '_' + i] = true ; dfs(i); } } //End of traversal stack.push(node); } dfs( 0 ); return stack.reverse(); } Copy code

random number:

  1. Generate [min, max] random number
//Math.random() generates the range (0, 1) function getRandom ( min, max ) { return Math .floor( Math .random() * (max-min + 1 )) + min; } Copy code

Sort:

  1. Heap sort
//Adjust the heap //params: heap, i //hint: i's left subtree and right subtree are already adjusted heap function heapMaxify ( heap, i ) { while (i <heap.length) { let max = i, left = i * 2 + 1 , right = i * 2 + 2 ; if (left <heap.length && heap[max] <heap[left]) { max = left; } if (right <heap.length && heap[max] <heap[right]) { max = right; } if (max == i) { return ; } else { let tmp = heap[i]; heap[i] = heap[max]; heap[max] = tmp; i = max; } } } //Build a heap //Adjust an array to a maximum heap function buildHeap ( heap ) { let n = heap.length, i = Math .floor((n- 2 )/2 ); while (i >= 0 ) { heapMaxify(heap, i); i--; } } //Heap sorting //Always swap the root of the heap (current maximum) with the end of the heap element (the end of the current heap) //Adjust the new root //Finally, you will get the ascending sorting result function heapSort ( heap ) { buildHeap(heap); let n = heap.length; for ( let j = n- 1 ; j >= 1 ; j--) { let tmp = heap[j]; heap[j] = heap[ 0 ]; heap[ 0 ] = tmp; heapMaxify(heap.slice( 0 , j- 1 ), 0 ); } } Copy code
  1. Increase of element x in the heap
//The value of an element i in the largest heap has increased.//Starting from i to find the correct position, if it is larger than the parent element, continue to exchange. //Don't worry about the changed elements will change the nature of the heap. Because the upper node must be larger than all nodes in the lower layer except x. function heapIncrease ( heap, i, x ) { heap[i] = x; let parent = Math .floor((i- 1 )/2 ); while (parent >= 0 && heap[i]> heap[parent]) { let tmp = heap[parent]; heap[parent] = heap[i]; heap[i] = tmp; i = parent; parent = Math .floor((parent- 1 )/2 ); } } Copy code
  1. Heap insertion (priority queue insertion)
//Put the element to the end of the pile //Continue to exchange with the parent node until it is not greater than the parent node //It is equivalent to adding the last -Infinity node to x function heapInsert ( heap, x ) { heap.push(x); let parent = Math .floor((heap.length- 2 )/2 ), i = heap.length - 1; while (parent >= 0 && heap[i] > heap[parent]) { let tmp = heap[parent]; heap[parent] = heap[i]; heap[i] = tmp; i = parent; parent = Math.floor((parent - 1)/2); } }

1

tip:

function preOrder(root) { if (!root) return []; let stack = [root], ans = []; while (stack.length) { let node = stack.pop(); ans.push(node); if (node.right) { stack.push(node.right); } if (node.left) { stack.push(node.left); } } return ans; }

tip:

function inOrder(root) { let stack = [], ans = [], node = root; while (node || !stack.length) { if (node) { stack.push(node); node = node.left; } else { node = stack.pop(); ans.push(node); node = node.right; } } return ans; }

tip: pop

function postOrder(root) { if (!root) return; let stack = [root], ans = []; pre = null; cur = null; while (stack.length) { cur = stack[stack.length - 1]; if (!cur.left && !cur.right || (!pre && (pre == cur.left || pre == cur.right))) { ans.push(stack.pop()); pre = cur; } else { if (cur.right) { stack.push(cur.right); } if (cur.left) { stack.push(cur.left); } } return ans; } }

1) h 2 ** h - 1 2) n Math.floor(logN) + 1 3) k 2 * k + 1, 2 * k + 2, Math.floor((k - 1)/2)