other

other

Large number operations:

  1. Multiply strings

Topic: Multiplying numbers represented by two very large strings

Solution: According to the vertical calculation, multiplication according to multiplication. Use an array to store the result of each single bit multiplication. Then use string addition for addition.

/** * @param {string} num1 * @param {string} num2 * @return {string} */ var subMultiply = function(num1, num2) { let result = [], rest = 0; for (let i = num1.length-1; i >= 0; i--) { let cur = Number(num1[i]) * Number(num2) + rest; result.unshift(cur% 10); rest = Math.floor(cur/10); } if (rest) { result.unshift(rest); } return result.join(''); } var multiply = function(num1, num2) { if (num1 == '0' || num2 == '0') return '0'; let result = [], cur = 0; //num1 is multiplied by each digit of num2, and the result is stored in an array (string array) for (let i = num2.length-1; i >= 0; i--) { cur = subMultiply(num1, num2[i]); result.push(cur); } //Padding 0 for each result result = result.map((num, index) => { let zeroStr =''; while(index> 0) { zeroStr += '0'; index--; } num += zeroStr; return num.split('').reverse().join(''); }); let sum = [], rest = 0; for (let i = 0; i <result[result.length-1].length; i++) { cur = 0; result.forEach(num => { if (num[i]) { cur += Number(num[i]); } }); cur += rest; let bit = cur% 10; rest = Math.floor(cur/10); sum.push(bit); } if (rest) { sum.push(rest); } return sum.reverse().join(''); }; Copy code
  1. Find Pow(x, n)

tip: Every integer can be decomposed into a sequence sum of 2 ** k powers.

/** * @param {number} x * @param {number} n * @return {number} */ var myPow = function ( x, n ) { if (n == 0 ) return 1 ; if (x == 1 || == X - . 1 && n-% 2 == 0 ) return . 1 ; IF (X == - . 1 && n-% 2 == . 1 ) return - 1; let flag1 = 1 , flag2 = 1 ; if (x < 0 && n% 2 == 1 ) { flag1 = -1 ; } x = Math .abs(x); = n-FLAG2> 0 ? . 1 : - . 1 ; IF (FLAG2 == - . 1 && n-== 0 - 2 ** 31 is ) { flag2 = -2 ; = n- 2 ** 31 is - . 1 ; } else { n = Math .abs(n); } let tmp = x, result = 1 , base = 1 , sum = 0 ; //The sum of powers does not reach n, the complexity is logn while (sum <n) { //The base position is 1 if ((n & base)> 0 ) { result *= tmp; sum += base; } //X^2^k -> x^2^(k+1) tmp = tmp * tmp; base = base << 1 ; } if (flag2 ==- 1 ) { result = 1/result; } if (flag2 ==- 2 ) { result = 1/result/2 ; } if (flag1 ==- 1 ) { result = 0 -result; } return result; }; Copy code
  1. Divide two integers

tip: Converting to a negative number will not overflow. The result of division is required to be an integer, then it is the sum of powers of 2.

/** * @param {number} dividend * @param {number} divisor * @return {number} */ var subdivide = function ( dividend, divisor ) { //The dividend is greater than the divisor, which proves that the absolute value of the dividend is small. The result is rounded down to 0 let ans = 0 , tmp = divisor; // Inflate by 2 times each time. It can be understood that the result can always be expressed as a sum of powers of 2. //-10 is less than -3 * 2 (the result of proof is greater than 2 ** 1) while (dividend < 0 ) { if (dividend> divisor) return ans; //The dividend is greater than the divisor of 2, and the result is rounded to 1 if (dividend <= divisor && dividend> divisor + divisor) return ans + 1 ; i = 1 ; tmp = divisor; while (dividend <= tmp + tmp) { tmp = tmp << 1 ; i = i * 2 ; } ans += i; dividend -= tmp; } return ans; }; var divide = function ( dividend, divisor ) { //The dividend is 0, the result is 0 if (dividend == 0 ) return 0 ; //The divisor is 1, the result is the dividend if (divisor == 1 ) return dividend; //divisor -1 IF (divisor == - . 1 ) { //minimum dividend is not a negative, compared with the dividend negated IF (dividend The> 0 - 2 ** 31 is ) { return 0 - dividend The; //minimum dividend is negative , the result is the maximum positive number } the else { return 2 ** 31 is - . 1 ; } } //The sign of the result let negative = false ; //If the sign of the dividend and the divisor are opposite, the result is negative. if (dividend> 0 && divisor < 0 || dividend < 0 && divisor> 0 ) { negative = true ; } //All conversions are calculated as negative numbers and will not overflow dividend = dividend> 0 ? 0 -dividend: dividend; divisor = divisor> 0 ? 0 -divisor: divisor; //Start calculation let result = subdivide(dividend, divisor); if (negative) { result = 0 -result; } return result; }; Copy code
  1. The sum of two integers, without addition and subtraction

tip: Two numbers are AND, the result is the XOR of the two numbers after addition, and the result is the result of the addition.

Solution: Take the result of the XOR of two numbers as a, and the result of the AND as b b <<1 because b is the carry result. Add loops, knowing that no carry is generated (b == 0)

var getSum = function ( a, b ) { let sum = a ^ b, carry = (a & b) << 1 ; while (b != 0 ) { a = sum; b = carry; sum = a ^ b; carry = (a & b) << 1 ; } return a; }; Copy code

tree:

  1. Determine whether a tree is a binary search tree:

tip: BST definition: the left subtree is all smaller than the root, and the right subtree is all larger than the root.

Solution: In the middle-order traversal, determine whether the sequence is an ascending non-recursive traversal, and the popped node is regarded as being visited.

Solution: Traverse a tree in non-recursive middle order:

  1. First find the leftmost node through while, and continue to push the stack
  2. Pop one node at a time. A node is popped out, which means that its left subtree has been visited. At this time, it visits itself and pushes the right subtree and all the left subtrees of the right subtree onto the stack.
  3. Except for the first node, every time a node is visited, the value is compared with lastValue. In ascending order, set lastValue to the current value.

2. The nearest common ancestor of the two nodes of the binary tree

tip: Solve by traversing the path and pressing the stack

  1. Delete node in BST

The predecessor of a node is the rightmost node of the left subtree. If the node is not the left subtree, traverse the ancestors upwards until there is an ancestor of the right subtree. The predecessor is the rightmost node of the left subtree of the ancestor or The ancestors themselves. If the node is the right subtree, then it is an ancestor.

The successor is the leftmost node of the right subtree. If the node is not the right subtree, traverse the ancestor until the ancestor has a left node, and the successor is the leftmost node of the ancestor's right subtree or the ancestor itself. If the node is the left subtree, then it is the ancestor.

var buildStack = function ( root, node, path ) { if (!root) return false ; path.push(root); if (root == node || buildStack(root.left, node, path) || buildStack(root.right, node, path)) { return true ; } else { path.pop(); return false ; } } var lowestCommonAncestor = function ( root, p, q ) { let stack1 = [], stack2 = []; buildStack(root, p, stack1); buildStack(root, q, stack2); let p1 = stack1.length- 1 , p2 = stack2.length- 1 ; while (p1> p2) { p1--; } while (p2> p1) { p2--; } while (stack1[p1] != stack2[p2]) { p1--; p2--; } return stack1[p1]; }; Copy code
  1. The successor of a node in BST: the leftmost subtree of the right subtree

  2. Delete BST node

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined? 0: val) * this.left = (left===undefined? null: left) * this.right = (right===undefined? null: right) *} */ /** * @param {TreeNode} root * @param {number} key * @return {TreeNode} */ var subDeleteNode = function ( head, root, key, parent, flag ) { if (!root) return null ; //found Deleted node if (root.val == key) { let node = null , pre = null ; //If there is a predecessor, replace the node with the predecessor. The predecessor is the last right node of the left subtree ( if there is no left subtree itself) if (root.left) { //Confirm the predecessor and assign it to node node = root.left; while (node.right) { pre = node; node = node.right; } //The predecessor needs to inherit the right subtree of the deleted node (the predecessor definitely has no right subtree) node.right = root.right; //If the predecessor is not the left subtree of the deleted node, it may have a left subtree, and its left subtree needs to be handed over to the number of right children of its parent node (the right subtree of the parent node is the predecessor itself, that is, there is nothing ), its new left subtree is the left subtree of the deleted element if (pre) { pre.right = node.left; node.left = root.left; } if (!parent) { return node; } else { parent[flag] = node; return head; } //If there is no predecessor, use the successor instead, and the successor is the leftmost subtree of the right subtree } else if (root.right) { node = root.right; pre = null ; while (node.left) { pre = node; node = node.left; } //If the successor is not the right subtree of the deleted node, //the right subtree of the successor needs to become the left subtree of the successor father (the successor itself is the left subtree of the father, and then the successor itself has to be removed so the father has no left Subtree. The successor must not have a left subtree) //At the same time, the new right subtree of the successor is the right subtree of the deleted node.//If the successor is the right subtree of the deleted node, then the translation is fine, and there must be no left child tree. if (pre) { pre.left = node.right; node.right = root.right; } node.left = root.left; if (!parent) { return node; } else { parent[flag] = node; return head; } } if (parent) { parent[flag] = null ; return head; } else { return null ; } } else if (key <root.val){ return subDeleteNode(head, root.left, key, root, 'left' ) || head; } else { return subDeleteNode(head, root.right, key, root, 'right' ) || head; } } var deleteNode = function ( root, key ) { if (!root) return null ; return subDeleteNode(root, root, key, null , '' ); }; Copy code
  1. Implement the prefix tree

Title: Prefix tree definition: N-ary tree. The same path does not repeatedly build subtrees

/** * Initialize your data structure here. */ var Trie = function () { this .root = {}; }; /** * Inserts a word into the trie. * @param {string} word * @return {void} */ Trie.prototype.insert = function ( word ) { var current = this .root; word.split( "" ).forEach( ( letter, index ) => { if (current[letter]) { current = current[letter]; } else { current[letter] = {}; current = current[letter]; } if (index == word.length- 1 ) { current.end = true ; } }); }; /** * Returns if the word is in the trie. * @param {string} word * @return {boolean} */ Trie.prototype.search = function ( word ) { let current = this .root, i = 0 ; for (; i <word.length; i++) { if (current[word[i]]) { current = current[word[i]]; } else break ; } return i == word.length && current.end == true ; }; /** * Returns if there is any word in the trie that starts with the given prefix. * @param {string} prefix * @return {boolean} */ Trie.prototype.startsWith = function ( prefix ) { let current = this .root, i = 0 ; for (; i <prefix.length; i++) { if (current[prefix[i]]) { current = current[prefix[i]]; } else break ; } return i == prefix.length; }; Copy code
  1. BST pruning: keep fixed interval nodes and do not change the node structure

tip: The topic of the tree must be good at using recursion, especially when the original idea is to traverse in front, middle and back.

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined? 0: val) * this.left = (left===undefined? null: left) * this.right = (right===undefined? null: right) *} */ /** * @param {TreeNode} root * @param {number} low * @param {number} high * @return {TreeNode} */ var trimBST = function ( root, low, high ) { if (!root) return null ; if (root.val <low) { return trimBST(root.right, low, high); } if (root.val> high) { return trimBST(root.left, low, high); } root.left = trimBST(root.left, low, high); root.right = trimBST(root.right, low, high); return root; }; Copy code
  1. Top k high-frequency words: heap sort
/** * @param {string[]} words * @param {number} k * @return {string[]} */ var compare = function ( a, b ) { return (a.count> b.count || (a.count == b.count && a.word <b.word))? 1 : -1 ; }; //Maintain a minimum heap of size k var heapMinify = function ( heap, start ) { while (start <heap.length) { let min = start; let left = 2 * start + 1 , right = 2 * start + 2 ; if (left <heap.length && compare(heap[left], heap[start]) ==- 1 ) { min = left; } if (right <heap.length && compare(heap[right], heap[min]) ==- 1 ) { min = right; } if (start == min) { return ; } let tmp = heap[min]; heap[min] = heap[start]; heap[start] = tmp; start = min; } }; var buildMinHeap = function ( heap ) { if (heap.length == 1 ) return ; let n = heap.length, i = Math .floor(n/2 ) -1 ; while (i >= 0 ) { heapMinify(heap, i); i--; } }; var topKFrequent = function ( words, k ) { let map = {}; for ( let i = 0 ; i <words.length; i++) { if (!map[words[i]]) { map[words[i]] = { word : words[i], count : 1 }; } else { map[words[i]].count++; } } let items = Object .values(map), heap = items.slice( 0 , k); buildMinHeap(heap); for ( let i = k; i <items.length; i++) { if (compare(items[i], heap[ 0 ]) == 1 ) { heap[ 0 ] = items[i]; heapMinify(heap, 0 ); } } let ans = []; while (heap.length) { ans.push(heap[ 0 ]); heap[ 0 ] = heap[heap.length- 1 ]; heap.pop(); heapMinify(heap, 0 ); } return ans.map( item => item.word).reverse(); }; Copy code

7. Find the k-th smallest number in BST

tip: Conducive to recursion. If it is found in the left subtree, directly return the value returned by the left subtree. If the left subtree does not exist, count +1. If it happens to be k, it proves that the current node is. Otherwise, go to the right subtree to find and return the value returned by the right subtree.

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined? 0: val) * this.left = (left===undefined? null: left) * this.right = (right===undefined? null: right) *} */ /** * @param {TreeNode} root * @param {number} k * @return {number} */ var kthSmallest = function ( root, k ) { let count = 0 ; var inordertraverse = function ( root ) { if (!root) return - 1 ; let value = inordertraverse(root.left); if (value !=- 1 ) return value; count++; if (count == k) return root.val; return inordertraverse(root.right); }; return inordertraverse(root); }; Copy code

8. Refactor the string

Topic: Rearrange the string so that every two characters are not adjacent

Solution: 1. count the number of occurrences of each character, and select the one with the most remaining times from the remaining characters each time. Use big root pile

/** * @param {string} s * @return {string} */ //No one character appears more than half of the number of times.//Each time choose one of the non-self characters with the most remaining number //Maintain a large root heap var heapMaxify = function ( arr, index ) { let endIndex = Math .floor(arr.length/2 ) -1 ; while (index <= endIndex) { let left = 2 * index + 1 , right = 2 * index + 2 , max = index; if (left <arr.length && arr[left].count> arr[index].count) { max = left; } if (right <arr.length && arr[right].count> arr[max].count) { max = right; } let tmp = arr[index]; arr[index] = arr[max]; arr[max] = tmp; if (max != index) { index = max; } else { break ; } } }; //After this, it is not sorted, but just built a big root heap, var buildHeap = function ( arr ) { let endIndex = Math .floor(arr.length/2 ) -1 ; for ( let i = endIndex; i >= 0 ; i--) { heapMaxify(arr, i); } }; var reorganizeString = function ( s ) { let map = {}; for ( let i = 0 ; i <s.length; i++) { if (!map[s[i]]) { map[s[i]] = 1 ; } else { map[s[i]]++; if (map[s[i]]> Math .ceil(s.length/2 )) { return "" ; } } } let items = [], ans = '' ; for ( let key in map) { if (map.hasOwnProperty(key)) { items.push({ letter : key, count : map[key] }); } } buildHeap(items); for ( let i = 0 ; i <s.length; i++) { //If it is the first element, or the previous element is different from the top of the heap, take the top of the heap directly if (ans.length == 0 || ans[ ans.length- 1 ] != items[ 0 ].letter) { ans += items[ 0 ].letter; items[ 0 ].count--; } else { let max = 0 ; //Take the left subtree by default if (items.length> 1 ) { max = 1 ; } //Compare the right subtree if (items.length> 2 && items[ 2 ].count> items[max].count) { max = 2 ; } //Exchange position let tmp = items[ 0 ]; items[ 0 ] = items[max]; items[max] = tmp; //Take the maximum value of the top triangle ans += items[ 0 ].letter; items[ 0 ].count--; } //If the number of elements at the top of the heap is 0, it proves that the character cannot be used anymore , move the last leaf node to the top of the heap and adjust. if (items[ 0 ].count == 0 ) { items[ 0 ] = items.pop(); } //Adjust heapMaxify(items, 0 ); } return ans; }; Copy code

9. Output and target path

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined? 0: val) * this.left = (left===undefined? null: left) * this.right = (right===undefined? null: right) *} */ /** * @param {TreeNode} root * @param {number} targetSum * @return {number[][]} */ var pathSum = function ( root, targetSum ) { if (!root) return []; let ans = [] , path = [root.val]; const tarverse = ( node, sum ) => { if (!node.left && !node.right && sum == targetSum) { ans.push([...path]); return ; } if (node.left) { path.push(node.left.val); tarverse(node.left, sum + node.left.val); path.pop(); } if (node.right) { path.push(node.right.val); tarverse(node.right, sum + node.right.val); path.pop(); } }; tarverse(root, root.val); return ans; }; Copy code
  1. BST to doubly linked list

tips: recursion

/** *//Definition for a Node. * function Node(val, left, right) { * this.val = val; * this.left = left; * this.right = right; * }; */ /** * @param {Node} root * @return {Node} */ var treeToDoublyList = function ( root ) { if (!root) return null ; var inorderConvert = function ( node ) { if (!node) return [ null , null ]; let left = inorderConvert(node.left); let right = inorderConvert(node.right); node.left = left[ 1 ]; node.right = right[ 0 ]; if (left[ 1 ]) { left[ 1 ].right = node; } if (right[ 0 ]) { right[ 0 ].left = node; } return [left[ 0 ]? left[ 0 ]: node, right[ 1 ]? right[ 1 ]: node]; } let [head, tail] = inorderConvert(root); head.left = tail; tail.right = head; return head; }; Copy code

Picture:

  1. Find the number of islands:

Depth-first traversal or breadth-first traversal. When the stack is empty, it is proved that an island traversal is completed (a connected graph traversal is completed), and then the next connected graph node is found through a double loop. Use the method of changing the value of the visited node to 0 instead of re-declaring the visited array, saving space

/** * @param {character[][]} grid * @return {number} */ var numIslands = function ( grid ) { if (!grid || grid.length == 0 ) return 0 ; let nr = grid.length, nc = grid[ 0 ].length, result = 0 , queue = []; for ( let i = 0 ; i <nr; i++) { for ( let j = 0 ; j <nc; j++) { if (grid[i][j] == '1' ) { result++; grid[i][j] = '0' ; //Join the current node (using the one-dimensional expanded position calculation as the unique identifier) queue.push([i, j]); while (queue.length) { let cur = queue.shift(), row = cur[ 0 ], col = cur[ 1 ]; if (row> 0 && grid[row- 1 ][col] == '1' ) { queue.push([row- 1 , col]); grid[row- 1 ][col] = '0' ; } if (row <nr- 1 && grid[row + 1 ][col] == '1' ) { queue.push([row + 1 , col]); grid[row + 1 ][col] = '0' ; } if (col> 0 && grid[row][col- 1 ] == '1' ) { queue.push([row, col- 1 ]); grid[row][col- 1 ] = '0' ; } if (col <nc- 1 && grid[row][col + 1 ] == '1' ) { queue.push([row, col + 1 ]); grid[row][col + 1 ] = '0' ; } } } } } return result; }; Copy code
  1. Copy of graph

The graph is represented by an entry node {val, neighbours}

var buildGragh = function ( originNode, newNode, map ) { map[originNode.val] = newNode; originNode.neighbors.forEach( neighbor => { let newNeighbor = map[neighbor.val]? map[neighbor.val]: buildGragh(neighbor, { val : neighbor.val, neighbors : []}, map); newNode.neighbors.push(newNeighbor); }); return newNode; }; var cloneGraph = function ( node ) { if (!node) return null ; return buildGragh(node, { val : node.val, neighbors : []}, {}); }; Copy code

3. Find Euler paths in a directed connected graph

Euler path: Go through all nodes and walk only once on each edge

Solution: DFS each node from the starting node, and the principle of selecting the next node each time is the smallest lexicographic order. And the traversed edges are recorded as visited or deleted from the adjacency list, and recorded as visited. The first point that cannot be traversed is reached last. So first push the stack and then pop one by one (array reverse order)

/** * @param {string[][]} tickets * @return {string[]} */ //Find Euler path in connected graph var findItinerary = function ( tickets ) { let map = {}, stack = []; var dfs = ( src ) => { while (map[src] && map[src].length) { let nextDest = map[src].shift(); dfs(nextDest); } stack.push(src); } for ( let i = 0 ; i <tickets.length; i++) { let [src, dest] = tickets[i]; if (!map[src]) { map[src] = [dest]; } else { map[src].push(dest); } } for ( let key in map) { if (map.hasOwnProperty(key)) { map[key].sort(); } } dfs( 'JFK' ); stack.reverse(); return stack; }; Copy code

Monotonic stack:

  1. Maximum water volume

Problem: Given the heights of the baffle height array, find the maximum volume of water that can be accommodated.

Solution: Set a monotonically increasing array. Because a partition that is shorter than the height of a partition to the right is meaningless.

  1. After choosing k numbers to remove, the remaining number is the smallest

Title: The number num represented by the string, remove the k characters, so that the number represented by the remaining string is the smallest

Solution: Increment the stack monotonically, and when it encounters a descending order (smaller than the top number of the stack), pop the stack until the top element of the stack is smaller than the current element or reaches k number. If it is the former, push Nums[i] onto the stack.

var removeKdigits = function ( num, k ) { if (num == '0' ) return '0' ; let stack = [num[ 0 ]], i = 1 ; for (; i <num.length && k> 0 ; i++) { if (num[i] >= stack[stack.length- 1 ]) { stack.push(num[i]); } else { while (stack.length && stack[stack.length- 1 ]> num[i] && k> 0 ) { stack.pop(); k--; } stack.push(num[i]); } } while (k> 0 ) { stack.pop(); k--; } while (i <num.length) { stack.push(num[i++]); } let start = 0 ; while (stack[start] == '0' ) start++; stack = stack.slice(start); return stack.length? stack.join( '' ): '0' ; }; Copy code
  1. Time to wait for warming up

Topic: Given a temperature array, return the time to wait for the temperature to rise every day

/** * @param {number[]} T * @return {number[]} */ var dailyTemperatures = function ( T ) { //Maintain a monotonically decreasing stack, where the element index is stored in the stack, and the temperature corresponding to the element decreases let stack = [], result = new Array (T.length), top = 0 ; stack.push( 0 ); result[ 0 ] = 0 ; for ( let i = 1 ; i <T.length; i++) { result[i] = 0 ; while (top >= 0 && T[stack[top]] <T[i]) { result[stack[top]] = i-stack[top]; stack.pop(); top--; } stack.push(i); top++; } return result; }; Copy code