1.2021Year already half, "gold nine silver ten" written test is about to start, sort out some algorithm questions to study together.2.I use JavaScript(V8/Node) to solve the problem, which has been debugged.3.Come on! Progress together!Copy the code1. Sort
The following two functions are general functions that you will use in sorting, so I won’t write them all
function checkArray(array) {
if(! array || array.length <=2) return }
function swap(array, left, right) {
let rightValue = array[right]
array[right] = array[left]
array[left] = rightValue
}
Copy the code2. Time complexity
The worst time complexity is often used to measure an algorithm.
Constant time O(1) means that this operation doesn’t depend on the amount of data, it’s a fixed time operation, like four operations.
For aN algorithm, the number of operations may be calculated as aN + 1, where N represents the amount of data. So the time of this algorithm is order N. Because the amount of data is usually very large when we calculate the time complexity, the low-order term and the constant term can be ignored.
Of course, it is possible that both algorithms are O(N) time complexity, so the way to compare the two algorithms is to compare the low-order terms with the constant terms.
3. Bit operations
Bit operations are useful in algorithms and can be much faster than four operations.
You should know how to convert decimal to binary and binary to decimal before learning bitwise operations. Here’s a simple way to do it
- Decimal 33 can be thought of as 32 + 1, and it should be six-bit binary (since 33 is approximately 32, and 32 is 2)
So decimal 33 is 100001, and as long as it is raised to the power of 2, it is 1 otherwise 0
- So binary 100001, same thing, the first digit is 2 to the fifth, the last digit is 2 to the zero, which adds up to 33
4. The left < <
10 << 1 / / - > 20
Copy the codeTo move to the left is to move the whole binary to the left, so 10 is represented as 1010 in binary, and when you move one bit to the left it becomes 10100, which is 10 to the decimal, which is 20, so you can basically view the left shift as the following formula: A times 2 to the b.
5. Count right >>
10 >> 1 / / - > 5
Copy the codeArithmetically, to move to the right is to move the whole binary to the right and remove the extra right-hand side, so 10 is represented as 1010 in binary, and when you move to the right by one bit it becomes 101, and when you convert to decimal it becomes 5, so you can basically think of it as the following formula int v = a/(2 ^ b) right shift is very useful, For example, it can be used to take the middle value in binary algorithms
13 >> 1 / / - > 6
Copy the code6. Maximum suborder sum
Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.
class Solution:
def maxSubArray(self.nums: List[int]) -> intDynamic programmingres = cur = nums[0]
for i in range(1, len(nums)):
cur = max(nums[i], cur + nums[i])
res = max(res, cur)
return res
Copy the codeDynamic programming. Time complexity O(n), space complexity O(1).
7. List
Interview question: Reverse one-way linked lists
They need to reverse a one-way linked list. The idea is very simple. Three variables are used to represent the current node and the nodes before and after the current node. Although this question is very simple, it is a common interview question
Here is the code to implement the algorithm
var reverseList = function(head)
{
// Determine the variable boundary problem
if(! head || ! head.next)return head
// The initial setting is null because the first node is inverted and the tail node points to null
let pre = null
let current = head
let next
// Check whether the current node is empty
// Get the next node of the current node if it is not empty
// Then set next of the current node to the previous node
// Set current to the next node and pre to the current node
while(current) {
next = current.next
current.next = pre
pre = current
current = next
}
return pre
};
Copy the code8. Pre-order, middle-order, post-order traversal of binary tree
Sequential traversal means that the root node is visited first, then the left node, and finally the right node.
Middle-order traversal means that the left node is visited first, then the root node, and finally the right node.
Sequential traversal means that the left node is accessed first, then the right node, and finally the root node.
9. Recursive implementation
The recursive implementation is fairly simple, with the following code
function TreeNode(val)
{
this.val = val;
this.left = this.right = null;
}
var traversal = function(root) {
if (root)
{
/ / first order
console.log(root);
traversal(root.left);
/ / in the sequence
// console.log(root);
traversal(root.right);
/ / after order
// console.log(root);}};Copy the code10. Tree depth
The maximum depth of a binary tree
The following is the algorithm implementation
var maxDepth = function(root)
{
if(! root)return 0
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};
Copy the code11. Dynamic programming
The basic idea behind dynamic programming is very simple. By breaking up a problem into subproblems, which are generally very similar, we can reduce the amount of computation by solving each subproblem only once.
Once you have a solution to each subproblem, store the result for future use.
12. Merge two ordered lists
Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.
Input: l1 = [1.2.4], l2 = [1.3.4] output: [1.1.2.3.4.4]
Copy the codeHere is the code to implement the algorithm
function mergeTwoLists(l1, l2) {
if (l1 = null && l2 == null) {
return null;
}
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
returnl2; }}Copy the codeUse recursion to complete the iteration
Reverse linked lists
Given the head node of a single linked list, reverse the list and return the reversed list.
Enter: head = [1.2.3.4.5] output: [5.4.3.2.1]
Copy the code// Reverse the linked list
function reverseList(head){
//1, walk through the list, remove the value of each node in the list, store it in the array
// Save the value of the node instead of the entire node, which can save memory.
let arr=[];// arR is used to store the values of the nodes in the linked list
let p=head;//p is used to traverse the list
while(p){
arr.push(p.val);
p=p.next;
}
//2, run through the list again and assign the values in reverse order to the val field of each node to reverse the list
// (instead of creating a new list, we used the original list to save time and memory.)
p=head;
while(p){
p.val=arr.pop();
p=p.next;
}
return head;
}
Copy the code1. Iterate through the list, removing the value of each node in the list and storing it in the array
2. Iterate through the list again and assign the values in the array to the val field of each node in reverse order to achieve the inversion of the list
14. Binary search algorithm (based on the sorted case)
function binarySearch(arr, data) {
var end = arr.length - 1,
start = 0;
while (start <= end) {
var middle = Math.floor((start + end) / 2);
if (arr[middle] > data) {
end = middle - 1;
} else if (arr[middle] < data) {
start = middle + 1;
} else {
returnmiddle; }}return -1;
}
var arr = [1.2.3.4.5.6];
console.log(binarySearch(arr, 2));
Copy the code15. Fibonacci numbers
The Fibonacci sequence is defined recursively as follows:
F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n >=3, n∈ n *)
The implementation process
Fibonacci numbers, usually denoted by F(n), form a sequence called the Fibonacci sequence. The sequence starts with 0 and 1, and each successive digit is the sum of the preceding two. That is:
F (0) = 0, F (1) = 1, F (N) = F (N – 1) + F (N – 2), where N > 1. Given N, compute F(N).
Here is the code to implement the algorithm
/ * * *@param {number} N
* @return {number}* /
var fib = function(N) {
if (N<2) return N;
var frist = 0;
var second = 1;
for (var i=2; i<=N; i++) { second = frist + second; frist = second - frist; }return second;
};
Copy the codeFor loop, use two variables to store the first two Fibonacci numbers. And there is no need for temporary variables in the exchange of variables, space complexity O(N)
16. Find the maximum difference of the following positive arrays
Input [10.5.11.7.8.9] output6
Copy the codeThis is a question to test the search for the maximum value of a basic array, and obviously we know that the maximum difference must be the difference between the maximum and minimum value of an array.
function getMaxProfit(arr) {
var minPrice = arr[0];
var maxProfit = 0;
for (var i = 0; i < arr.length; i++) {
var currentPrice = arr[i];
minPrice = Math.min(minPrice, currentPrice);
var potentialProfit = currentPrice - minPrice;
maxProfit = Math.max(maxProfit, potentialProfit);
}
return maxProfit;
}
Copy the code17. Randomly generate a string of the specified length
Implement an algorithm that randomly generates characters of specified length.
Here is the code to implement the algorithm
For example, given a length8Output 4 ldkfg9jfunction randomString(n) {
let str = 'abcdefghijklmnopqrstuvwxyz9876543210';
let tmp = ' ',
i = 0,
l = str.length;
for (i = 0; i < n; i++) {
tmp += str.charAt(Math.floor(Math.random() * l));
}
return tmp;
}
module.exports = randomString;
Copy the codeFind the greatest sum of any two numbers
Find the two largest numbers and return their sum.
function topSum(arr){
if(arr.length<2) return null;
var first,second;
if(arr[0]>arr[1]){
first = arr[0];
second=arr[1];
}else{
first = arr[1];
second=arr[0];
}
for(var i=2; i<arr.length; i++){if(arr[i]>first){
second = first;
first = arr[i];
}else if(arr[i]>second){ second = arr[i]; }}return first+second;
}
Copy the code19. Remove duplicate values from an array of integers
For example, enter: [1.13.24.11.11.14.1.2] output: [1.13.24.11.14.2[need to be removed11 和 1These two elements.Copy the codeThis question appears in many front end questions. It mainly inspects the use of Object by individuals and uses key to screen.
/** * unique an array **/
let unique = function(arr) {
let hashTable = {};
let data = [];
for(let i=0,l=arr.length; i<l; i++) {if(! hashTable[arr[i]]) { hashTable[arr[i]] =true; data.push(arr[i]); }}return data
}
module.exports = unique;
Copy the code20. Replace Spaces
Implement a function that replaces each space in a string with “%20”.
For example, if the string is "We Are Happy.", the replacement string is "We%20Are%20Happy"Copy the codeUse a simple re to get a space and replace it with %20.
Partial re rules :/g matches all elements that match the conditions. \d: indicates numbers ^ : indicates the beginning $: indicates the end + : matches multiple strings for example: ^\d+$matches only numberslet readline = require('readline');
let rl = readline.createInterface({
input:process.stdin,
output:process.stdout
})
rl.on('line'.function(input){
// let result = deal(input);
let result = input.trim().replace(/ /g.'% 20'); //replace(get value, replace value)
console.log(result);
return result;
})
Copy the code21. Implement a function to determine whether the input is a palindrome string
function isPlalindrome(input) {
if (typeofinput ! = ='string') return false;
return input.split(' ').reverse().join(' ') === input;
}
Copy the code22. Tencent: Array flattening, de-weighting, sorting
The interview questions
Known as an array: var arr = [[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10]. Write a program to flatten and divide an array of duplicate data, resulting in an ascending and non-repeating array
let arr =[[1.2.2], [3.4.5.5], [6.7.8.9[11.12[12.13[14]]]], 10]
function newArray ( ) {
while(arr.some(Array.isArray)){ arr = [].concat(... arr) } arr = [...newSet(arr)].sort((a,b) = >{
return a-b
})
return arr
}
newArray()
console.log(arr);
Copy the code23. Write a function to calculate the intersection of multiple arrays
Requirement: Each element in the output must be unique
const getIntersection = (. arrs) = > {
return Array.from(new Set(arrs.reduce((total, arr) = > {
return arr.filter(item= > total.includes(item));
})));
}
Copy the code24. Select sort
Select sort starts at the beginning of the array, compares the first element to the other elements, checks all the elements, puts the smallest element in the first place, starts with the second element, and repeats all the way to the end.
It’s very simple: the outer loop starts at 0 to Length-1, and then the inner loop compares the smallest open head
function selectSort(arr) {
var len = arr.length;
for(let i = 0; i < len -1; i++) {
for(let j = i ; j<len; j++) {
if(arr[j] < arr[i]) { [arr[i],arr[j]] = [arr[j],arr[i]]; }}}return arr
}
Copy the code- The I of the outer cycle represents the number of rounds, and arr[I] represents the earliest (smaller) position of the current round.
- The inner layer starts with I, goes back, finds something smaller than the beginning, and just switches places
25. Climbing stairs
There is a staircase with M steps. You start at the first step. If you can only go up one or two steps at a time, how many ways can you go up the M step?
There are only two ways to get to the n steps, from (n-1) or (n-2). So you can think of it recursively, if you have an array s[n], then s[1] = 1 (there is only one way to do it since you started at level 1), and s[2] = 1 (there is no other way to go up from s[1]).
Then we can derive s[3] ~ s[n].
To continue the simulation, s[3] = s[1] + S [2], because you can only take two steps from level 1, or one step from level 2.
function cStairs(n) {
if(n === 1 || n === 2) {
return 1;
} else {
return cStairs(n-1) + cStairs(n-2)}}Copy the codeYeah, it’s actually Fibonacci numbers
26. Stack implementation queue
Use stacks to implement the following operations on queues:
Push (x) – Puts an element at the end of the queue. Pop () — Removes the element from the head of the queue. Peek () — returns the element at the head of the queue. Empty () — Returns whether the queue is empty.
Example:
let queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); / / returns 1
queue.pop(); / / returns 1
queue.empty(); / / returns false
Copy the codeTheir thinking
Since the stack is fifo, to get fifO effect, we might as well use two stacks. When doing push, we push to Stack1, and when doing POP and PEEK, we go through Stack2.
There is a special case where stack2 is empty. How to do pop and peek? Simply pop and push elements from Stack1 into Stack2, and then operate stack2 as normal, as shown below:
Here is the code to implement the algorithm
var MyQueue = function() {
this.stack1 = [];
this.stack2 = [];
};
MyQueue.prototype.push = function(x) {
this.stack1.push(x);
};
// Move stack1 elements to stack2
MyQueue.prototype.transform = function() {
while(this.stack1.length) {
this.stack2.push(this.stack1.pop());
}
}
MyQueue.prototype.pop = function() {
if(!this.stack2.length) this.transform();
return this.stack2.pop();
};
MyQueue.prototype.peek = function() {
if(!this.stack2.length) this.transform();
return this.stack2[this.stack2.length - 1];
};
MyQueue.prototype.empty = function() {
return !this.stack1.length && !this.stack2.length;
};
Copy the code27. Queue implementation stack
And the effect of the previous problem is just the opposite, with the queue first in first out way to achieve the effect of the first out.
Their thinking
Take the queue above as an example. It is easy to push directly from the end of the queue. But what about Pop and Peek?
Back to our goal, our goal is to get to the end of the line, which is 3. This is easy to do, we let the first element out of the queue, except for the last element, the rest of the elements in another queue.
var MyStack = function() {
this.queue1 = [];
this.queue2 = [];
};
MyStack.prototype.push = function(x) {
if(!this.queue2.length) this.queue1.push(x);
else {
Queue2 already has a value
this.queue2.push(x);
// The old stack top is moved to Queue1
this.queue1.push(this.queue2.shift()); }}; MyStack.prototype.transform =function() {
while(this.queue1.length ! = =1) {
this.queue2.push(this.queue1.shift())
}
// Queue2 holds the previous element
// Switch queue1 and Queue2
// Now queue1 contains the first element, queue2 contains only the last element of the queue
let tmp = this.queue1;
this.queue1 = this.queue2;
this.queue2 = tmp;
}
MyStack.prototype.pop = function() {
if(!this.queue2.length) this.transform();
return this.queue2.shift();
};
MyStack.prototype.top = function() {
if(!this.queue2.length) this.transform();
return this.queue2[0];
};
MyStack.prototype.empty = function() {
return !this.queue1.length && !this.queue2.length;
};
Copy the codeOne of the things to note about the implementation is that Queue1 always holds the preceding elements, and Queue2 always holds the last element of the queue (that is, the element at the top of the stack).
The catch with pushing is that you can’t push new values to Queue1 when queue2 already has elements, because the top of the stack should be updated. For the new value, push to Queue2 and then push the old top of the stack out of Queue2 and into Queue1, thus updating the top of the stack.
28. Two-pointer problem
The sum of the nearest three numbers
Given an array of n integers nums and a target value target. Identify the three integers in NUMs so that their sum is closest to target. Returns the sum of these three numbers. Assume that there is only one answer for each set of inputs.
Example:
Enter nums = [-1.2.1, -4], target = 1Output:2Explanation: The sum closest to target is2 (-1 + 2 + 1 = 2).Copy the codeFirst, sort in ascending order, then choose a base point I (0 <= I <= nums.length-3) from left to right, and use a double pointer to find the smallest difference on the right side of the base point.
Suppose the base point is I, and when initialized, the two Pointers are:
- Left: I + 1, one digit to the right of the base point.
- Right: last digit of nums. length-1 array.
If the sum is greater than target, move the right pointer to the left to try a smaller value, or move the left pointer to the right to try a smaller value.
In this process, the global minimum difference min is constantly updated, as well as the and RES recorded at this time. Finally, return res.
/ * * *@param {number[]} nums
* @param {number} target
* @return {number}* /
let threeSumClosest = function (nums, target) {
let n = nums.length
if (n === 3) {
return getSum(nums)
}
// This is the first order of business
nums.sort((a, b) = > a - b)
let min = Infinity // The minimum difference from target
let res
// Try to make a base pointer from left to right
for (let i = 0; i <= nums.length - 3; i++) {
let basic = nums[i]
let left = i + 1 // The left pointer starts with the first digit to the right of I
let right = n - 1 // The right pointer starts with the last item in the array
while (left < right) {
let sum = basic + nums[left] + nums[right] // The sum of three numbers
// Update the minimum difference
let diff = Math.abs(sum - target)
if (diff < min) {
min = diff
res = sum
}
if (sum < target) {
// If the sum is less than the target value, try moving the left pointer to the right to enlarge the value
left++
} else if (sum > target) {
// Otherwise, the right pointer moves to the left
right--
} else {
// If the difference is 0, it must be the answer
return sum
}
}
}
return res
}
function getSum(nums) {
return nums.reduce((total, cur) = > total + cur, 0)}Copy the code