# 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```

1. Reversed list
```//Reverse order of the linked list: move 1~n to the front of the 0th one in turn

while (cur) {
pre.next = cur.next;
cur = pre.next;
}
}

Copy code```

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

```
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) {
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
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)
//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)