The title of this article is selected from LeetCode’s selection of TOP interview questions, which are actually encountered by myself and my colleagues in more than 80% of the time (front-end positions in Chengdu and Beijing).
Please refer to # simple questions for the previous version
Binary tree (DFS)
Binary tree before and after traversal routine detailed
The preorder traversal topic is as follows:
The root node is node A (as shown in the following image), and then asks you to print out the nodes in the numeric order shown in the following image.
And we can see the pattern here, which is that the depth-first traversal, first the left subtree, then the right subtree, we don’t have to do recursion here, because some of the big factories are very strict about binary tree traversal without recursion, recursion is too easy.
The key idea is: depth-first traversal, first traversal left subtree, then traversal right subtree,
So, we need a set of generic templates for how to traverse a binary tree, first left subtree, then right subtree, as follows, right
var Traversal = function(root) {
const stack = [];
while (root || stack.length){
while(root){
stack.push(root);
root = root.left;
}
root = stack.pop();
root = root.right;
}
return res;
};
Copy the codeWe combine the image and find that the order of the overall stacks generated by this traversal is
- A, B, C, D
- D out of the stack
- B the stack
- E into the stack
- E out of the stack
- Out of A stack
- C stack
- C a stack
- F into the stack
- F the stack
Let’s put the top pushed elements in order, A, B, D, E, C, F, and that’s the order of the preceding traversal! Solved!
D, B, E, A, C, F (this is in order bentley’s requirements, ok, two problems solve)
Put the concrete preorder traversal code:
var preorderTraversal = function(root) {
// Initialize the data
const res =[];
const stack = [];
while (root || stack.length){
while(root){
res.push(root.val);
stack.push(root);
root = root.left;
}
root = stack.pop();
root = root.right;
}
return res;
};
Copy the codeIn order traversal is a meaning, in the previous order traversal based on the transformation
var preorderTraversal = function(root) {
// Initialize the data
const res =[];
const stack = [];
while (root || stack.length){
while(root){
stack.push(root);
root = root.left;
}
root = stack.pop();
res.push(root.val);
root = root.right;
}
return res;
};
Copy the codeThe posterior traversal is a little different, but the routine is the same. We need to first traverse the right subtree, then traverse the left subtree, and the reverse, and we can do it. The code is as follows:
var postorderTraversal = function(root) {
// Initialize the data
const res =[];
const stack = [];
while (root || stack.length){
while(root){
stack.push(root);
res.unshift(root.val);
root = root.right;
}
root = stack.pop();
root = root.left;
}
return res;
};
Copy the codeSymmetric binary tree
In short, a binary tree is symmetric. For example:
The binary tree [1,2,2,3,4,4,3] is symmetric.
1
/ \
2 2
/ \ / \
3 4 4 3
Copy the codeBut the following [1,2,2,null,3,null,3] is not mirror symmetric:
1 / \ 2 2\3 3Copy the codeIdeas:
Recursive solution:
- Determines whether the values of the current nodes of the two Pointers are equal
- judge
AThe right subtree ofBIs the left subtree of - judge
AThe left subtree ofBIs the right subtree of
function isSame(leftNode, rightNode){
if(leftNode === null && rightNode === null) return true;
if(leftNode === null || rightNode === null) return false;
return leftNode.val === rightNode.val && isSame(leftNode.left, rightNode.right) && isSame(leftNode.right, rightNode.left)
}
var isSymmetric = function(root) {
if(! root)return root;
return isSame(root.left, root.right);
};
Copy the codeThe maximum depth of a binary tree
This question encountered in the interview didi, mainly to master the routines of binary tree traversal
- As long as you get to the point where there’s no left subtree or right subtree
- If you have recorded the depth before, you can compare whether it is larger than the previous record. If it is larger, you can update the depth
- And so on, all the way to the deepest
var maxDepth = function(root) {
if(! root)return root;
let ret = 1;
function dfs(root, depth){
if(! root.left && ! root.right) ret =Math.max(ret, depth);
if(root.left) dfs(root.left, depth+1);
if(root.right) dfs(root.right, depth+1);
}
dfs(root, ret);
return ret
};
Copy the codeConvert an ordered array into a binary search tree
Let’s start with the question:
Given an array of integers, NUMs, whose elements have been sorted in ascending order, convert it to a highly balanced binary search tree.
A height-balanced binary tree is a binary tree where the absolute value of the height difference between the left and right subtrees of each node is no more than 1.
Example 1:
Nums = [-10, -3.0.5.9] Output: [0, -3.9, -10.null.5] Explanation: [0, -10.5.null, -3.null.9] will also be taken as the correct answer:Copy the codeExample 2:
Input: nums = [1.3] Output: [3.1] Explanation: [1.3] and [3.1] are highly balanced binary search trees. Tip:1 <= nums.length <= 104
-104 <= nums[i] <= 104Nums are listed in strict ascending orderCopy the codeIdeas:
- Building a tree includes: Building
Root, build root.left and root.right - It says “highly balanced” — constructed
root, select the middle element of the array asrootNode value, you can maintain balance. - Recursive functions can pass either an array or a pointer. When passing a pointer, choose: l and r respectively represent the first and last indexes of the array that participates in building BST.
var sortedArrayToBST = function(nums) {
return toBST(nums, 0, nums.length - 1)};const toBST = function(nums, l, r){
if( l > r){
return null;
}
const mid = l + r >> 1;
const root = new TreeNode(nums[mid]);
root.left = toBST(nums, l, mid - 1);
root.right = toBST(nums, mid + 1, r);
return root;
}
Copy the codeThe stack
A stack is a first-in, first-out data structure, so when it comes to the idea that you need first-in, first-out, you can use a stack.
Secondly, I think the stack is very similar to recursion. Recursion is not to push the stack first, and then come in first out, just like function call stack.
20. Valid parentheses
This is a typical stack problem. Given a string s containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, determine if the string is valid.
A valid string must meet the following requirements:
The opening parenthesis must be closed with a closing parenthesis of the same type. The opening brackets must be closed in the correct order.
The sample1: Enter: s ="()"Output:trueThe sample2: Enter: s ="[the] {} ()"Output:trueThe sample3: Enter: s ="(]"Output:falseThe sample4: Enter: s ="([]"Output:false
Copy the codeThere is a rule in this question:
- Before the close parenthesis, must be the corresponding open parenthesis, in order to cancel!
- Before the close parenthesis, is not the corresponding open parenthesis, then the string, must not be valid parenthesis!
That means we just put the open bracket on the stack, and if we find the close bracket, we compare it to the top element, and if it doesn’t, we return false
var isValid = function(s) {
const map = { '{': '} '.'(': ') '.'[': '] ' };
const stack = [];
for(let i of s){
if(map[i]){
stack.push(i);
} else {
if(map[stack[stack.length - 1]] === i){
stack.pop()
}else{
return false; }}}return stack.length === 0;
};
Copy the codeMinimum stack
First look at the title:
Design a stack that supports push, pop, and top operations and can retrieve the smallest element in constant time.
- Push (x) — Pushes the element x onto the stack.
- Pop () — Deletes the top element of the stack.
- Top () — Gets the top element on the stack.
- GetMin () — Retries the smallest element in the stack.
Example: MinStack MinStack =new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3); minStack.getMin(); -- -- > returns3.minStack.pop(); minStack.top(); - > to return0.minStack.getMin(); -- -- > returns2.Tip: Pop, top, and getMin operations are always called on non-empty stacks.Copy the codeInstead of writing getMin, it’s easy to satisfy other methods. Let’s take a look:
var MinStack = function() {
this.stack = [];
};
MinStack.prototype.push = function(x) {
this.stack.push(x);
};
MinStack.prototype.pop = function() {
this.stack.pop();
};
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1];
};
Copy the codeHow to ensure the minimum each time, let’s take an example:
As shown above, we need a secondary stack to record the minimum,
- So let’s start by pushing negative 2 on the stack
- This is minStack, because the smallest stack is -2, so push -2
- stack push 0
- At this time, the auxiliary station minStack will compare 0 with -2, -2 is smaller, and minStack will push -2
- stack push -3
- At this time, the auxiliary station minStack will compare -3 with -2. -3 is smaller, and minStack will push -3
So when we take the smallest, we can always get the smallest value in the minStack, so we have the solution:
var MinStack = function() {
this.stack = [];
/ / auxiliary stack
this.minStack = [];
};
MinStack.prototype.push = function(x) {
this.stack.push(x);
// Push x if it is the first time or the current x is smaller than the minimum value in the minimum stack
if(this.minStack.length === 0 || x < this.minStack[this.minStack.length - 1]) {this.minStack.push(x)
} else {
this.minStack.push( this.minStack[this.minStack.length - 1])}}; MinStack.prototype.pop =function() {
this.stack.pop();
this.minStack.pop();
};
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1];
};
MinStack.prototype.getMin = function() {
return this.minStack[this.stack.length - 1];
};
Copy the codeDynamic programming
Dynamic programming, you have to know the dynamic transfer equation, and if you have that, it’s the key to the problem, so let’s get a sense of that from the problem
53. Maximum suborder sum
The title is as follows:
Given an array of integers, nums, find a contiguous subarray with the largest sum (the subarray contains at least one element) and return its largest sum.
The sample1: Nums = [-2.1, -3.4, -1.2.1, -5.4] output:6Explanation: Continuous subarrays [4, -1.2.1] is the largest, is6. The sample2: Input: nums = [1] output:1The sample3: Input: nums = [0] output:0
Copy the codeIdeas:
- This problem can be solved by dynamic programming, the key is to find the dynamic transfer equation
- Suppose dp[I] : including the maximum continuous subsequence before the subscript I and is dp[I].
Determine that the recursion formula DP [I] can only be derived in two directions:
- Dp [i-1] + nums[I], that is, nums[I] adds to the current contiguous subsequence and
- Nums [I] : computes the sum of the current contiguous subsequence from the beginning
- Dp [I] = Max (dp[I] + nums[I], nums[I]);
var maxSubArray = function(nums) {
let res = nums[0];
const dp = [nums[0]].for(let i=1; i < nums.length; i++){if(dp[i-1] >0){
dp[i]=nums[i]+dp[i-1]}else{
dp[i]=nums[i]
}
res=Math.max(dp[i],res)
}
return res
};
Copy the code70. Climb the stairs
First look at the title:
Suppose you are climbing the stairs. It takes you n steps to get to the top.
You can climb one or two steps at a time. How many different ways can you climb to the top of the building?
Note: given n is a positive integer.
The sample1Input:2Output:2Explanation: There are two ways to get to the top of the building.1. 1Order +1 阶
2. 2Order sample2Input:3Output:3Explanation: There are three ways to climb to the top of the building.1. 1Order +1Order +1 阶
2. 1Order +2 阶
3. 2Order +1 阶
Copy the codeWhen it comes to dynamic programming, you have to know the dynamic transfer equation, which is the key to the problem,
For this problem, let’s assume that DP [10] is the number of ways to reach the top of the building by climbing to the 10th floor.
So, does DP [10] mean that you go to step 8 and then take two more steps, and you go to step 9 and then take one more step,
So dp[10] is equal to DP [9]+dp[8]
Dp [n] = dp[n-1] + dp[n-2]
The code is as follows:
var climbStairs = function(n) {
const dp = {};
dp[1] = 1;
dp[2] = 2;
for(let i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2]}return dp[n]
};
Copy the codeMathematical problems
The following are more mathematical problems, and these are very important, because they’re often used in the intermediate problems, like the one we’re going to talk about in a second, where you add two numbers, which is a template.
66. Plus one
There are two key points to this question:
- The variable carry that needs to have a carry keeps track of what the carry is
- We also need a variable, sum, that resets the sum for each iteration to help us figure out whether to carry and what number to carry
var plusOne = function(digits) {
let carry = 1; // Carry (since we are sure +1, the initial carry is 1)
for(let i = digits.length - 1; i >= 0; i--){
let sum = 0; // This variable is used to calculate the carry and digits[I] values for each loop
sum = digits[i] + carry;
digits[i] = sum % 10; // The modular operation takes the units digit
carry = (sum / 10) | 0; // Divide by 10 by hundreds and discard the decimal place
}
if(digits[0= = =0) digits.unshift(carry);
return digits
};
Copy the code69 square root of x
Int SQRT (int x);
Calculates and returns the square root of x, where x is a non-negative integer.
Since the return type is an integer, only the integer part of the result is retained, and the fractional part is eliminated.
The sample1Input:4Output:2The sample2Input:8Output:2Description:8The square root of PI is PI2.82842. Since the return type is an integer, the fractional part will be omitted.Copy the codeThis is a typical dichotomy problem, so we need to be familiar with the general template for dichotomy. Let’s do this:
Find 4 in [1, 2, 3, 4, 5, 6, 7, 8, 9], return subscript if it exists, return -1 if it does not exist
funcion searchNum(target, nums){
if(! nums.length)return -1;
let l = 0;
let r = nums[nums.length - 1];
while(l <= r){
let mid = l + r >> 1
if(nums[mid] === target) return mid;
if(nums[mid] > target) {
r--
} else {
l++
}
}
return -1;
}
Copy the codeNotice in example 2, the decimal part is going to be left out. So we know that if a number aa squared is greater than xx, then AA must not be the square root of xx. We need to continue the search for the square root of xx in the interval [0.. a-1][0..a−1] next round.
So the code looks like this:
const mySqrt = x= > {
let [low, high] = [0, x];
while (low <= high) {
const mid = (low + high) >> 1;
if (mid * mid > x) {
high = mid - 1;
} else if (mid * mid < x) {
low = mid + 1;
} else {
returnmid; }}return high;
};
Copy the code171. Excel serial number
This problem is more important, but also more basic, in short, is the base conversion
The title is as follows:
You are given an integer columnNumber and return its corresponding column name in the Excel table.
Such as:
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
Copy the codeThe sample1: Input: columnNumber =1Output:"A"The sample2: Input: columnNumber =28Output:"AB"The sample3: Input: columnNumber =701Output:"ZY"The sample4: Input: columnNumber =2147483647Output:"FXSHRXW"
Copy the codeTo put it bluntly, this is a base 26 problem. We used to know that when you go from base 10 to base 2, you just keep dividing by 2 and adding up the remainder. The same is true for base 26
Ideas:
- Get the number for each character starting at the end, cur = c. charcodeat () -64
- Sum of digits sum += Current number * number of digits in the base
- *= 26, carry = 1
var titleToNumber = function(s) {
let sum = 0, i = s.length - 1, carry = 1;
while (i >= 0) {
let cur = s[i].charCodeAt() - 64;
sum += cur * carry;
carry *= 26;
i--;
}
return sum;
};
Copy the code172. Zero in factorial
Given an integer n, return n! The number of zeros in the mantissa of the result.
The sample1Input:3Output:0Explanation:3! = 6There is no zero in the mantissa. The sample2Input:5Output:1Explanation:5! = 120, the mantissa has1A zero.Copy the codeThis is an easy problem. There are as many zeros as there are fives
var trailingZeroes = function (n) {
let r = 0;
while (n > 1) {
n = parseInt(n / 5);
r += n;
}
return r;
};
Copy the code// ## 190
268. The missing figures
The title is as follows:
Given an array nums containing n numbers in [0, n], find the number in the range [0, n] that does not appear in the array.
Advanced:
Can you solve this problem with a linear time complexity algorithm using only extra constant space?
The sample1: Input: nums = [3.0.1] output:2Explanation: n =3Because there are3So all the numbers are in the range [0.3].2Is the missing number because it does not appear in nums. The sample2: Input: nums = [0.1] output:2Explanation: n =2Because there are2So all the numbers are in the range [0.2].2Is the missing number because it does not appear in nums.Copy the codeSo this is an easy one, it’s the sum of 0 minus n minus the sum of the array
- The sum of 0-n is an arithmetic sequence:
(first + mantissa) * Number of terms / 2To find
var missingNumber = function(nums) {
const len = nums.length
let sum = ((1 + len) * len) / 2
for (let i = 0; i < len; i++) {
sum -= nums[i]
}
return sum
}
Copy the code// Power of -3
412. Fizz Buzz
There is nothing to say about this problem, just write the code according to the problem, first look at the problem:
Write a program that outputs a string representation of numbers from 1 to N.
-
If n is a multiple of 3, output “Fizz”;
-
If n is a multiple of 5, output “Buzz”;
-
If n is a multiple of both 3 and 5, output “FizzBuzz”.
Example: n =15, return: ["1"."2"."Fizz"."4"."Buzz"."Fizz"."Seven"."8"."Fizz"."Buzz"."11"."Fizz"."13"."14"."FizzBuzz"
]
Copy the code var fizzBuzz = function (n) {
const list = [];
for (let i = 1; i <= n; i++) {
const is3Times = i % 3= = =0; // Is a multiple of 3
const is5Times = i % 5= = =0; // Is a multiple of 5
const is15Times = is3Times && is5Times; // Is a multiple of 15
if (is15Times) {
list.push('FizzBuzz');
continue;
}
if (is3Times) {
list.push('Fizz');
continue;
}
if (is5Times) {
list.push('Buzz');
continue;
}
list.push(`${i}`);
}
return list;
};
Copy the code-
- Integer inversion
This post will be updated later
Ring problem
The characteristic of this kind of problem is that you have to cycle to find it, and how to cycle to find it, you can see by the problem.
141. Ring linked list
The title is as follows:
Given a linked list, determine whether there are rings in the list.
If there is a node in the list that can be reached again by continuously tracing the next pointer, there is a loop in the list. To represent the loop in a given list, we use the integer POS to represent where the end of the list is joined into the list (the index starts at 0). If pos is -1, there are no rings in the list. Note: POS is not passed as a parameter, only to identify the actual condition of the linked list.
Returns true if there is a loop in the list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1 output: trueCopy the codeExample 2:
Input: head = [1,2], pos = 0 output: true explanation: there is a loop in the list with the end connected to the first node.Copy the codeWe use the marking method:
Mark the traversal nodes, if the traversal process encountered a marked ring
var hasCycle = function(head) {
let traversingNode = head;
while(traversingNode){
if(traversingNode.isVistitd) return true
traversingNode.isVistitd = true
traversingNode = traversingNode.next
}
return false;
};
Copy the code160. Intersecting linked lists
The title is as follows:
Given the head nodes headA and headB of two singly linked lists, you find and return the starting node where the two singly linked lists intersect. If two lists do not intersect, null is returned.
In the figure, two linked lists intersect at node C1:
The topic data guarantees that there are no rings in the entire chain structure.
Note that after the function returns the result, the list must retain its original structure.
Example 1:
Enter intersectVal =8, listA = [4.1.8.4.5], listB = [5.0.1.8.4.5], skipA = 2, skipB = 3Output: Intersected at'8'Explanation: The value of the intersecting node is8(Note that if two lists intersect, it cannot be0). Starting from the header of each list, A is [4.1.8.4.5], the linked list B is [5.0.1.8.4.5]. In A, there is before the intersection node2A node; In B, there is before the intersection node3A node.Copy the codeExample 2:
Enter intersectVal =2, listA = [0.9.1.2.4], listB = [3.2.4], skipA = 3, skipB = 1Output: Intersected at'2'Explanation: The value of the intersecting node is2(Note that if two lists intersect, it cannot be0). Starting from the header of each list, A is [0.9.1.2.4], the linked list B is [3.2.4]. In A, there is before the intersection node3A node; In B, there is before the intersection node1A node.Copy the codeThis post will be updated later
202. Happiness
The problem is as follows: Write an algorithm to determine whether a number n is a happy number.
“Happy number” is defined as:
- For a positive integer, replace the number each time by the sum of the squares of the numbers in each of its positions.
- And then you repeat the process until this number gets to 1, or it could go on forever but it never gets to 1.
- If it can be 1, then this number is a happy number.
- Return true if n is a happy number; If not, false is returned.
How to analyze the happiness number?
If we look at a table, we conclude that there are two ways to square a number in the way happiness numbers are defined
-
- get
1
- get
-
- An infinite loop
Refer to the diagram below for an infinite loop
Some people say will it keep getting bigger, and the answer is no: Let’s look at this list,
- You can see that if you are 13 bits, your next happy number algorithm is going to be 4 bits 1053,
- If you are
9999.4The next happy number is324
| digits | Maximum number of bits | Next happy number |
|---|---|---|
| 1 | 9 | 81 |
| 2 | 99 | 162 |
| 3 | 999 | 243 |
| 4 | 9999 | 324 |
| 13 | 9999999999999 | 1053 |
So the code just needs to determine these two, and the code looks like this:
// Encapsulate the method to get the happy number
function getNext(n){
n = String(n);
let sum = 0;
for(let num of n){
sum = sum + Math.pow(+num, 2);
}
return sum;
}
var isHappy = function(n) {
// Hash table to see if the loop
const map = {};
while( n ! = =1 ){
map[n] = true;
n = getNext(n)
if(map[n]) return false
}
return true
};
Copy the codeAfter the intermediate algorithm will be written, please be sure to master these basic algorithm problems, the foundation is not strong, after the intermediate questions are many on the basis of these basic questions.