Read the instructions before
The article will be divided into three parts, including some common interview algorithm questions, most of the algorithm questions from “Sword finger Offer”, here I would like to express my thanks to the author of this book, and some from my own collection. There are a variety of solutions to the topic, hope prawn more comments or corrections
1. Array traversal
Description: In an array, each row is sorted in ascending order from left to right and each column is sorted in ascending order from top to bottom. Finish: Enter one of these two dimensional arrays and an integer to determine if the array contains the integer
The array is ordered, and the number of traversals can be reduced according to the law. If the number is not equal, you can remove some rows/columns depending on the size of the target number and the number
function findNumInSortedArray(arr, num) {
if(! Array.isArray(arr) || typeof num ! ='number' || isNaN(num)) {
return;
}
let rows = arr.length;
let columns = arr[0].length;
let row = 0;
let column = columns -1;
while(row < rows && column >=0 ){
if (arr[row][column] == num) {
return true;
} else if (arr[row][column] > num) {
column --;
} else{ row ++ ; }}return false;
}
Copy the code2. String replacement
Description: Implement a function that replaces each space in a string with %20. If enter ‘we arr happy’, then print ‘we%20are%20happy’
We can use regular replacement and ergodic replacement
// Use refunction replaceStr(str){
if(typeof str ! = ='string') {
console.log('str is not string');
return;
}
return str.replace(/\s/g, '% 20'} // To use traversal substitution, you need to traverse STR, recognize Spaces, and then replace stringsfunction replaceStr2(str) {
if(typeof str ! = ='string') {
console.log('str is not string');
return;
}
let strArr = [];
let len = str.length;
let i = 0;
while(i < len) {
if (str[i] === ' ' ) {
strArr[i] = '% 20';
} else{ strArr[i] = str[i]; }}return strArr.join(' ');
}
Copy the code3. Reverse printing of linked lists
Description: Enter the head node of a linked list and print the value of each node from end to end
You can flip the list and print it again, but that will break the structure of the list. You can also use stacks to store nodes and then print them
function displayLinkList(head) {
let stack = [];
let node = head;
while(node) {
stack.push(node);
node = node.next;
}
for (letlen = stack.length - 1; len >=0 ; len--) { console.log(stack[i].ele); }}Copy the code4. Rebuild the binary tree
Description: Input the results of the preceding and middle order traversal of a binary tree, please reconstruct the binary tree. It is assumed that the result of both the preceding and the middle traversal of the input does not contain duplicate numbers. For example, input preorder traversal sequence {1,2,4,7,3,5,6,8} and intermediate order traversal sequence {4,7,2,1,5,3,8,6}, then rebuild the binary tree and return.
In a binary tree, the first digit is always the value of the tree’s root node. In a middle tree, the value of the root node is in the middle of the sequence. Find the root node, determine the left and right subtrees, and recurse, the key being to mount the ‘root’ nodes in turn (determine whether they are left or right). The front order determines the root node, and the middle order determines the left and right nodes
// Node definitionfunction TreeNode(ele) {
this.ele = ele;
this.right = null;
this.left = null;
}
function constructBinaryTree(preOrders, inOrders) {
if (!inOrders.length) {
return null;
}
let rootIndex = 0;
let l_preOrders = [];
let l_inOrders = [];
let r_preOrders = [];
letr_inOrders = []; // Determine the root nodelet head = new TreeNode(preOrders[0]);
for (let i = 0; i < inOrders.length; i++ ) {
if (preOrders[0] === inOrders[i]) { rootIndex = i; }} // Determine the left and right child treefor (let i = 0; i < rootIndex; i++) {
l_preOrders.push(preOrders[ i + 1]);
l_inOrders.push(inOrders[i]);
}
for (let i = rootIndex + 1; i < inOrders.length; i ++ ) {
r_preOrders.push(preOrders[i]);
r_inOrders.push(inOrders[i]);
}
head.left = constructBinaryTree(l_preOrders, l_inOrders);
head.right = constructBinaryTree(r_preOrders, r_inOrders);
return head;
}
function getTreeFromPreInOrders(preOrders, inOrders) {
if (Array.isArray(preOrders) && Array.isArray(inOrders)) {
return constructBinaryTree(preOrders, inOrders);
}
console.error('preOrders or inOrders is no Array');
}
Copy the code5. Mutual realization of stack and queue
Stack: first in, last out, queue: first in, first out
-
Description: Implement queues with two stacks
If all the data in stack A are placed on stack B in sequence, the data that entered stack A earlier will appear at the top of stack B. Therefore, the queue unqueuing is equivalent to the stack unqueuing of stack B, and the queue joining is equivalent to the stack unqueuing of stack A. When stack B is empty, all data on stack A is removed from stack B
let stack_a = [];
let stack_b = [];
function push (node ) {
stack_a.push(node);
}
function pop () {
if (stack_b.length === 0 ) {
for (leti = 0, len = stack_a.length; i < len; i ++ ) { stack_b.push(stack_a.pop()); }}return stack_b.pop();
}
Copy the code-
Description: Use two queues to implement stacks
Two queues, one queue is used as the storage area, the queue with data is sent to the cache queue, so when the queue with data is sent to the last queue, it is the data that needs to be pushed out of the stack. The pushed data is enqueued to the queue with data. If two are empty, either one is enqueued
let queue_a = [];
let queue_b = [];
function push(node) {
if (queue_a.length && queue_b.length) {
return console.log('wrong ! ');
}
if (queue_a.length) {
queue_a.push(node);
} else if (queue_b.length) {
queue_b.push(node);
} else{ queue_a.push(node); }}function pop() {
if(queue_a.length && ! queue_b.length) {for (let i = 0, len = queue_a.length; i < len; i++) {
if (i == len -1) {
return queue_a.shift();
} else{ queue_b.push(queue_a.shift()); }}}else if(! queue_a.length && queue_b.length) {for (let i = 0, len = queue_b.length; i < len; i++) {
if (i == len -1) {
return queue_b.shift();
} else{ queue_a.push(queue_b.shift()); }}}else if (queue_a.length && queue_b.length) {
console.log('wrong! ');
} else {
return null;
}
return null;
}
Copy the codeRotate the smallest number in the array
The rotation of a number to the end of an array is called rotation of the array. Take a rotation of an incrementally sorted array and print the smallest element of the rotation array. For example, the array {3,4,5,1,2} is a rotation of {1,2,3,4,5}, whose minimum value is 1
Idea: increasing order to find the most value, you can try dichotomy. The first element of the array must be larger than the last. Select the middle element and compare it to the last element. If it is larger than the last element, the smallest element is in the right range, otherwise in the left range
function findMinFromRotateArr(arr) {
if(! Array.isArray(arr)) {return console.error('wrong! ')}let start = 0;
let end = arr.length - 1;
while((end - start) > 1) {
let mid = Math.floor(((end + start)) / 2) ;
if (arr[mid] >= arr[end]) {
start = mid;
} else{ end = mid; }}return arr[end];
}
Copy the code7. Fibonacci numbers
Description: when n = 0,f(n) = 0; When n = 1, f(n) = 1; When n is greater than 1, f(n) = f(n-1) + f(n-2). Now that you want an integer n, print the NTH term of the Fibonacci sequence
The Fibonacci sequence is a classic mathematical problem. It can be solved by recursion and loop. Note that under recursion, if N is large, it will consume a lot of memory
// A recursive solutionfunction fibonacci(n) {
if (n <= 0) {
return 0;
}
if(n == 1) {
return 1;
}
returnfibonacci(n - 2) + fibonacci(n-1); } // loop solutionfunction fabonacci(n) {
if (n <= 0) {
return 0;
}
if(n == 1) {
return 1;
};
let fn_2 = 0;
let fn_1 = 1;
let fn = 0;
for (let i = 2; i <= n; i++) {
fn = fn_1 + fn_2;
fn_2 = fn_1;
fn_1 = fn;
}
return fn;
}
Copy the code-
Fibonacci variation 1 states: a frog can jump up one step or two steps at a time. Find out how many ways the frog can jump up n steps.
F (n) = f(n) = f(n) = f(n) = F (n) = F (n) = F (n) = F (n) = F (n) = F (n) = F (n) = F (n) So f(n) = f(n-1) + f(n-2) is a Fibonacci sequence
-
[] This is a 2×1 rectangle. It can be placed horizontally or vertically. How many ways can it cover a small rectangle like 8*2×1
// Big rectangle: [][][][][][][][] [][][] // [][][][][][][]Copy the codeIf the pendulum is vertical, one column will be occupied. If the pendulum is horizontal, two columns will be occupied by one pendulum. When the rectangle is first placed from eight columns, either the pendulum is vertical and then covers seven columns, or the pendulum is horizontal and then covers six columns. So we can abstract it as f of 8 is equal to f of 7 plus f of 6. It’s still a Fibonacci problem
8. Bit operation
Bit operations in js: & (and), | (or), ~ (a), ^ (exclusive or), < < (left), > > (right), > > > (unsigned moves to the right)
-
Description: Input an integer, output the number of 1 in the binary representation of the number. Where negative numbers are represented by complement.
We can use the right shift and bit and operation. Determine if the rightmost binary number of an integer is 1(and 1 and), then move it right until it is 0
// The flaw is that you can't handle negative numbers. Because signed numbers, the highest bit of the binary has a symbol for a number, the negative number is 1function numOf1(n) {
if(n.toString().indexOf('. ')! = 1) {return console.error('n is not a int');
}
let num = 0;
while(n) {
if (n & 1) {
num ++ ;
}
n = n >> 1;
}
returnnum; } // change the value of 1 to the left to compare with the value of I, so as to determine whether each bit of I is 1 // if it is 32 bits, then it will loop 32 timesfunction numOf1(n){
if(n.toString().indexOf('. ')! = 1) {return console.error('n is not a int');
}
let nums = 0;
let flag = 1;
while(flag) {
if(flg & n) {
nums ++;
}
flag = flag << 1;
}
returnnums; } // The principle of this is that when a binary number is subtracted from the binary number by 1, the resulting number is compared with the original binary number. The problem can be reduced to the number of ones in the binary number, which is the most efficientfunction numsOf1(n) {
if(n.toString().indexOf('. ')! = 1) {return console.error('n is not a int');
}
let nums = 0;
while(n) {
nums ++ ;
n = (n - 1) & n;
}
return nums;
}
Copy the code9. A number raised to an integer power
Description: Given a float of type double base and an integer of type int exponent. I’m going to take base exponent. Library functions are not used
The first reaction is to use the for loop to add up the product, but it is possible to ignore some cases: the input value of 0 is to a negative integer power. And how to reduce the number of iterations
function power(base, exponent) {
if (base == 0 && exponent < 0) {
return console.error('base should not be 0');
}
let absExponent = exponent < 0 ? -exponent : exponent;
let result = 1;
for (let i = 1; i <= absExponent; i++) {
result *= base;
}
if (exponent < 0) {
result = 1 / result;
}
returnresult; } // Use the recursion to reduce the number of products // use the bit and the operation can determine the odd and even, the integer right move one can take the number of integer divided by 2 // can reduce the number of operations by mutual multiplication, such as the number to the 8th power is the number of the 2nd power, the number of the 4th power is the number of the 2nd power...function power (base, exponent) {
if (exponent == 0) {
return 1;
}
if (exponent == 1) {
return base;
}
letresult = power(base, exponent >> 1); result *= result; / / for odd numberif (exponent & 1 == 1) {
result *= base;
}
return result;
}
Copy the codeDelete the linked list node
Description: Define a function to delete nodes, pass parameters as the head node and node to be deleted, the required time complexity is O(1).
If you delete a linked list, you iterate over the node to be deleted, and then point the previous node to the next node. However, each deletion requires traversal, and the time complexity is O(n). If you directly assign the value of the next node of the node to be deleted to the node to be deleted and then delete the next node, it is equivalent to deleting the node.
function deleteNode(headNode, deleteNode) {
if(! headNode || ! deleteNode) {return; } // The deleted node is the headerif(headNode == deleteNode) { headNode = null; } // The deleted node is the tail nodeelse if (deleteNode.next == null) {
let node = headNode;
while(node.next ! = deleteNode) { node = node.next; } node.next = null; deleteNode = null; } // The deleted node is an intermediate nodeelse {
letnextNode = delete.next; deleteNode.ele = nextNode.ele; deleteNode.next = nextNode.next; nextNode = null; [(n-1)O(1) + O(n)]/n -> O(1)Copy the code11. Reorder arrays
Description: Take an array of integers and implement a function to adjust the order of the numbers in the array so that all odd numbers are in the first half of the array and all even numbers are in the second half of the array.
If the number is even, take it out and place it at the end of the array. If p1 points to an even number and P2 points to an odd number, the two Pointers will be swapped.
function reOrderArray(arr)
{
// write code here
if(! Array.isArray(arr)) {return ;
};
let start = 0;
let end = arr.length - 1;
while(start <= end) {
let isOddS = arr[start] & 1;
letisEvenE = ! (arr[end] & 1);if(isOddS && ! isEvenE) { start ++; }else if (isOddS && isEvenE) {
start ++;
end --;
} else if(! isOddS && isEvenE) { end --; }else {
lettemp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start ++ ; end --; }}return arr;
}
Copy the code12. The KTH node of the derivative in the linked list
Description: Input a linked list, output the last KTH node in the list.
The length of the linked list can be obtained by traversing the list for the first time, and then by the penultimate KTH node, then by traversing the list for the NTH +1-k node. To iterate over a list once, take two Pointers, one to the head node and the other to the k-1st node, and then iterate over both Pointers simultaneously. When the second pointer points to the end of the list, the first pointer points to the KTH node
// The header is null, the number of nodes is less than k, and k is not greater than 0function findKthToTial (head, k) {
if(! head || k <= 0) {return null;
}
let startNode = head;
let endNode = head;
for (let i = 0; i < k - 1; i++) {
if(! endNode.next) {return null;
}
endNode = endNode.next;
}
while(endNode.next) {
startNode = startNode.next;
endNode = endNode.next;
}
return startNode;
}
Copy the codeReverse linked lists
Description: Input a linked list, reverse the list, output the new list header.
Thread: Iterate through the list, pointing the next node to the previous one
function resverseList(head) {
if(! head) {return null;
}
if (head.next == null) {
return head;
}
let node = head;
let nextNode = null;
let reservedNode = null;
let newHead = head;
while (node.next) {
nextNode = node.next;
reservedNode = nextNode.next;
nextNode.next = newHead;
node.next = reservedNode;
newHead = nextNode;
}
return newHead;
}
Copy the codeMerge two sorted lists
Description: Input two monotonically increasing linked lists, output the combined linked list of two lists, of course, we need the combined linked list to meet the monotonic rule
Compare two linked list nodes in turn
function mergeLinkList(head1, head2) {
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
let mergeHead = null;
if (head1.ele < head2.ele ) {
mergeHead = head1;
mergeHead.next = mergeLinkList(haed1.next, head2);
} else {
mergeHead = head2;
mergeHead.next = mergeLinkList(head1, head2.next);
}
return mergeHead;
}
Copy the codeBinary tree inclusion
Input two binary trees A and B to determine whether B is A substructure of A.
Find the root node where A contains B and compare the left and right subtrees based on that node
// Tree node definitionfunctionNode(ele) { this.ele = ele; this.left = null; this.right = null; } // Check that tree A has tree Bfunction hasSubTree(pRootA, pRootB) {
if(pRootA == null || pRootB == null) {
return false;
}
let result = false;
if(proot.ele === prootb.ele) {result = doesTreeAHaveTreeB(pRootA, pRootB); }if(! result) { result = hasSubTree(pRootA.left, pRootB); }if(! result) { result = hasSubTree(pRootA.right, pRootB) }return result;
}
functionDoesTreeAHaveTreeB (pRootA, pRootB) {// Determine pRootB firstif (pRootB == null) {
return false;
}
if(pRootA == null) {
return true;
}
if(pRootA.ele ! = pRootB.ele) {return false;
}
return doesTreeAHaveTreeB(pRootA.left, pRootB.left) && doesTreeAHaveTreeB(pRootA.right, pRootB.right)
}
Copy the code16. Mirror image of binary tree
Description: Complete a function, input a binary tree, the function output its mirror image
For non-leaf nodes, there are two nodes, then swap them
function mirror(root) {
if (root == null) {
return ;
}
let temp = root.left;
root.left = root.right;
root.right = temp;
if (root.left) {
mirror(root.left);
}
if(root.right) { mirror(root.right); }}Copy the code17. Print the matrix clockwise
Description: / Enter a matrix and print out each number in clockwise order from the outside in. For example, if you enter the following matrix: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10, in turn, print out the number 1.
The condition is that the number of columns > the number of columns x2, and the number of rows > the number of rows x2
function printMatrix (arr) {
if(! Array.isArray(arr)) {return;
}
let rows = arr.length;
let columns = arr[0].length;
let start = 0;
while( columns > start * 2 && rows > start * 2) {
printMatrixInCicle(arr, columns, rows, start); start ++ ; }}function printMatrixInCicle (arr, columns, rows, start) {
let endX = columns - 1 - start;
letendY = rows -1 - start; // Print a line from left to rightfor (leti = start; i <= endX; ++i) { console.log(arr[start][i]); } // Print a column from top to bottomif (start < endY) {
for (leti = start + 1; i <= endY; ++ i) { console.log(arr[endY][i]); }} // Print a line from right to leftif (start < endX && start < endY) {
for (leti = endX -1 ; i >= start; --i) { console.log(arr[endY][i]); }} // Print a line from bottom to topif (start < endX && start < endY - 1) {
for (leti = endY -1 ; i >= start + 1; --i) { console.log(arr[i][start]); }}}Copy the codeBiaozhiwang.github. IO star