preface
The last feedback is good, the original after worship really a group of people began to learn, 2021 spring recruitment began, I can give you help is as far as possible in February to update the algorithm entry column, can help you very happy ๐~
Now I would like to share with you how we prepare the algorithm, spring recruitment is about to start, but also the final preparation, I hope it will be helpful to you.
I originally planned to introduce it through an article, recommend my way and route of brushing questions, and get some feedback from my partners: it is better to be more detailed, zero-based, small white, and github access speed is also a problem, it may not be able to load pictures.
So, I’m going to split it up into several posts so that you can get a good idea of what Chocolate has done with his first post in Denver. It will be the Spring Festival soon, I hope to help you with your spring recruit. The content plan is as follows:
- ๐ฎ Write a beginner’s guide to Zero-based front-end algorithms, Acmer with girlfriend brush 80+ stacks and Queues and Linked Lists (completed ๐)
- ๐ฎ Write a beginner’s guide to Zero-based front-end algorithms, Acmer with girlfriend brush 80+ [Recursion and Backtracking] (completed ๐)
- ๐ฎ Write a beginner’s guide to Zero-based front-end algorithms, Acmer with girlfriend brush 80+ [Double Pointers and Strings] (this issue completed ๐)
- ๐ฎ write a beginner’s guide to zero-based front-end algorithms, acmer with girlfriend brush 80+
- ๐ฎ to write a zero-based front-end algorithm introduction guide, Acmer with his girlfriend brush 80+ [dynamic programming DP chapter]
- ๐ฎ to write a zero-based front-end algorithm primer, acmer with girlfriend brush 80+ใ Summary ใ
Welcome to GitHub repository, there are 552 big factory real questions, covering all kinds of front-end real questions, I wish you a spring and autumn recruitment
How do you prepare the algorithm
First of all, I would like to introduce myself briefly. I played ACM in school (if not, forget it, because there are no cards of great value, iron cards, participation cards and certificates are a lot of them).
If you know ACM and have participated in the domestic front-end interview, it should not take a long time to brush the questions. If you have any idea about my ACM experience, I will consider releasing a video in STATION B.
Therefore, it may take 10-20 days to prepare the algorithm for the zero-based xiaobai, while the cycle may be longer for non-academic classes. So, now I’m going to share how I took my girlfriend to do this.
- The first point, clear algorithm it is not very difficult things, to understand the fact that things, perhaps you will like to do the topic, of course, for ACM big guy to do the topic is another matter, the main body of this article and the interview level shall prevail
- Second, the front end of the algorithm is relatively simple, I encountered in the spring and Autumn recruitment process are some common questions, such as search, greedy, simple dynamic programming, classical sorting algorithm, are based on
leetcode
Some simple and medium difficulty, and these algorithms for the class, should have learned in school, such as algorithm analysis and design, data structure and algorithm courses, then have this basis, your brush time can be shortened - Third, since said to want to brush the topic, how to brush, I was in the nuggets reference for several bosses, (at the end of the article is the reference point) everyone TuiJianFen project to brush, in here, I also am very recommend, here, I want to brush algorithm to reduce the number of point, introduction to show you, when you brush after the project, you will have the relevant thinking initiative to brush the topic, Rather than very passive to brush, it is also very convenient to sum up their own ~
- Other, can refer to the big guy’s article, here no longer repeat…
A mind map to make your path easier
To cut to the chase, first provide a mind map, so that knowledge from complex to simple.
To obtain hd PDF, please reply to [LeetCode] on wechat public account [Little Lion front end]. You can add penguin group [666151691].
This warehouse brush topic route reference SSH (give big guy point praise) warehouse address: github.com/sl1673495/l…
Thanks for the boss’s summary, I originally planned to punch in and learn there, but later I decided to build a new warehouse to punch in and learn.
Secondly, most of the code to solve the problems in this warehouse is my own code style, and the questions have been expanded, and will continue to update, why not star collection?
The warehouse is introduced
Warehouse address: github.com/Chocolate19…
This warehouse will use JavaScript throughout the language, is a pure front-end brush topic route, for the front-end brush topic no direction of small partners is simply good news. The problem solving codes will be recorded in the Issues of the warehouse and classified according to label. For example, if you want to see problems in the “recursion and backtracking” category, select the TAB and filter.
At the same time, small partners can submit their own solution code in Issues, ๐ค welcome Contributing, can stick to the coolest person! Give a โญ๏ธ if this project helped you!
Brush question route
Now let’s start the process. Give this article a thumbs up, take out your favorite keyboard, and go!
The following topic order is only personal and interview points to summarize the brush questions, you can mix according to their own ideas. Please refer to this warehouse for more questions
Double pointer
15. Sum of three numbers
The sum of three numbers to the original problem portal
Topic describes
Given an array nums containing n integers, determine if there are three elements a, B, and c in nums such that a + b + c = 0. Please find all the triples that meet the criteria and are not duplicated.
Note: Repeated triples cannot be included in the answer.
Example:
Given the array nums = [-1.0.1.2, -1, -4], the set of triples that meet the requirements is: [[-1.0.1], [...1, -1.2]]Copy the code
Their thinking
Because we can’t have duplicate solutions, we sort the array to simplify things, so we can tell if an element is duplicate by looking at whether it’s equal to the element before it
When the double pointer moves, avoid repeated solutions
Once you have a solution, you need to shrink the left and right Pointers “inward” to avoid pointing to duplicate elements
- The left pointer moves to the right until it points to an element that does not repeat itself, as long as it is left < right
- The right pointer moves to the left as long as left < right until it points to an element that does not repeat itself
Optimization point, if the current element value is greater than 0, because we have sorted in advance, there is no three numbers add up to 0, in this case, just break.
/ * * *@param {number[]} nums
* @return {number[][]}* /
var threeSum = function (nums) {
let len = nums.length;
if (len < 2) return [];
let res = [];
nums.sort((a, b) = > a - b); // Sort from smallest to largest
for (let i = 0; i < len - 2; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] === nums[i - 1]) continue; // remove duplicates
let L = i + 1;
let R = len - 1;
while (L < R) {
let sum = nums[i] + nums[L] + nums[R]; // The sum of three numbers
if (sum === 0) {
res.push([nums[i], nums[L], nums[R]]);
while (L < R && nums[L] == nums[L + 1]) L++; // remove the weight until it points to a different number
while (L < R && nums[R] == nums[R - 1]) R--;
L++;
R--;
} else if (sum < 0) {
L++; // If the sum is less than 0, the left-hand side is too small, move to the right
} else if (sum > 0) {
R--; // If the sum is greater than 0, the right-hand side is too large, so it moves to the left}}}return res;
};
Copy the code
16. The sum of the nearest three
16. The nearest sum of three portal
Topic describes
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 code
Tip:
- 3 <= nums.length <= 10^3
- -10^3 <= nums[i] <= 10^3
- -10^4 <= target <= 10^4
Their thinking
This is a little bit different from 15, we only want the sum of the three trees that are closest to target, so we need to update it every time, the sum of the three trees that are closest to target, which is simply a comparison, and then we don’t have to redo it, so it’s a little bit less of a consideration.
/ * * *@param {number[]} nums
* @param {number} target
* @return {number}* /
var threeSumClosest = function (nums, target) {
let len = nums.length;
nums.sort((a, b) = > a - b); // Sort from smallest to largest
let res = nums[0] + nums[1] + nums[len - 1]; // Initialize a random res
for (let i = 0; i < len - 2; i++) {
let L = i + 1;
let R = len - 1;
while (L < R) {
let sum = nums[i] + nums[L] + nums[R]; // The sum of three numbers
sum > target ? R-- : L++; // If it is larger than the target value, indent it to the left; if it is smaller, indent it to the right
if (Math.abs(sum - target) < Math.abs(res - target)) {
res = sum; // Update the res iteratively}}}return res;
};
Copy the code
75. Color classification
75. Color classification original topic portal
Topic describes
Given an array of n red, white, and blue elements, sort them in place so that the elements of the same color are adjacent and sorted in red, white, and blue order.
In this case, we used integers 0, 1, and 2 to represent red, white, and blue, respectively.
Note: You cannot solve this problem using collation functions in the code base.
Example:
Input:2.0.2.1.1.0] output: [0.0.1.1.2.2]
Copy the code
Advanced:
An intuitive solution is to use a counting sort two-pass scan algorithm. First, iterate over the number of 0, 1, and 2 elements, and then rewrite the current array in order of 0, 1, and 2. Can you come up with a one-pass scan algorithm that uses only constant space?
Their thinking
If the value of a double pointer is 2, then the right pointer is swapped; if the value of a double pointer is 0, then the left pointer is swapped. If the value of a double pointer is 1, then the right pointer is swapped.
/ * * *@param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function (nums) {
let len = nums.length;
let L = 0;
let R = len - 1;
let i = 0;
while (i <= R) {
while (nums[i] == 2 && i < R) { // If the current value is 2, then the right pointer is swapped
[nums[i], nums[R]] = [nums[R], nums[i]];
R--;
}
while (nums[i] == 0 && i > L) { // If the current value is 0, then the left pointer is swapped
[nums[i], nums[L]] = [nums[L], nums[i]];
L++;
}
i++;
}
return nums;
};
Copy the code
I think the following code should make it easier to understand:
/ * * *@param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var sortColors = function (nums) {
let len = nums.length;
let L = 0;
let R = len - 1;
let i = 0;
while (i <= R) {
if (nums[i] == 0) { // If the current value is 0, then the left pointer is swapped
[nums[i], nums[L]] = [nums[L], nums[i]];
L++;
i++;
} else if (nums[i] == 2) { // If the current value is 2, then the right pointer is swapped
[nums[i], nums[R]] = [nums[R], nums[i]];
R--;
} else{ i++; }}return nums;
};
Copy the code
344. Reverse the string
344. Reverse the string problem portal
Topic describes
Write a function that reverses the input string. The input string is given in the form of the character array char[].
Instead of allocating extra space to another array, you must modify the input array in place, using O(1) extra space to solve the problem.
You can assume that all the characters in the array are printable characters in the ASCII code table.
Example 1:
Input:"h"."e"."l"."l"."o"] output: ["o"."l"."l"."e"."h"]
Copy the code
Example 2:
Input:"H"."a"."n"."n"."a"."h"] output: ["h"."a"."n"."n"."a"."H"]
Copy the code
Their thinking
Method 1: Use the JS native API
/ * * *@param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function (s) {
return s.reverse();
};
Copy the code
Method two: double pointer, head and tail swap
/ * * *@param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function (s) {
let i = 0, j = s.length - 1;
while (i < j) {
[s[i], s[j]] = [s[j], s[i]]; // Double pointer, swap
i++ , j--;
}
return s;
};
Copy the code
11. Container that holds the most water
11. The container that holds the most water is the original portal
They describe you as n non-negative integers a1, A2… Each number represents a point in the coordinates (I, ai). Draw n vertical lines in the coordinates, and the two endpoints of vertical line I are (I, AI) and (I, 0). Find the two lines that together with the X-axis will hold the most water.
Note: you cannot tilt the container, and the value of n is at least 2.
The vertical lines in the figure represent the input array [1,8,6,2,5,4,8,3,7]. In this case, the maximum amount of water the container can hold (shown in blue) is 49.
Example:
Input:1.8.6.2.5.4.8.3.7] output:49
Copy the code
Their thinking
The two-pointer approach, we need to enumerate all the cases, have a little greedy thinking, each time we have to look at the short board let us accommodate the area. Each time, we choose the board with the shortest left and right Pointers, calculate the most water currently in the board, and then start from the short board pointer and work inward, and so on, until we can enumerate all the cases, and of course enumerate the maximum container area.
/ * * *@param {number[]} height
* @return {number}* /
var maxArea = function (height) {
let len = height.length;
let L = 0;
let R = len - 1;
let res = 0;
while (L < R) {
if (height[L] < height[R]) { // Select the weak spot
let ans = height[L] * (R - L);
L++;
res = Math.max(res, ans); // Find the maximum amount of water currently contained
} else {
let ans = height[R] * (R - L);
res = Math.max(res, ans); R--; }}return res;
};
Copy the code
42. After the rain
42. Connect to the rain water portal
Topic describes
Given n non-negative integers to represent the height diagram of each column of width 1, calculate how much rain the columns in this order can catch after rain.
The height diagram above is represented by the array [0,1,0,2,1,0,1,3,2,1,2,1,1], in which case six units of rain can be caught (the blue parts are rain). Thanks to Marcos for contributing this image.
Example:
Input:0.1.0.2.1.0.1.3.2.1.2.1] output:6
Copy the code
Their thinking
This store water, we need to look at the left side of the pointer column to see whose height is small, the current is to see the height of the small.
Take the left side as an example: Current column storage = highest recent column height (only look at the left side to the current column) – Current column height
Same thing on the right-hand side.
/ * * *@param {number[]} height
* @return {number}* /
var trap = function (height) {
let len = height.length;
let L = 0, R = len - 1;
let leftHeight = 0, rightHeight = 0;
let res = 0;
while (L < R) {
if (height[L] < height[R]) { // The height of the left side is small
leftHeight = Math.max(leftHeight, height[L]);
res += leftHeight - height[L]; // The current column can hold water
L++;
} else { // The right side is small, look at the right side
rightHeight = Math.max(rightHeight, height[R]);
res += rightHeight - height[R]; // The current column can hold waterR--; }}return res;
};
Copy the code
209. Smallest subarray of length
209. Smallest subarray of length
Topic describes
Given an array of n positive integers and a positive integer s, find the smallest contiguous subarray in the array whose sum is โฅ s and return its length. If no subarray exists, return 0.
Example:
Enter: s =7, nums = [2.3.1.2.4.3] output:2Explanation: Subarray [4.3] is the smallest subarray for this condition.Copy the code
Advanced:
- If you have done the O(n) time solution, try the O(n log n) time solution.
Their thinking
Slide window, the use of double pointer implementation, from left to right, meet the conditions on the left pointer left, find the minimum length, and then every window right pointer to slide right, until the end of the array.
/ * * *@param {number} s
* @param {number[]} nums
* @return {number}* /
var minSubArrayLen = function (s, nums) {
let len = nums.length;
let L = 0, R = 0;
let res = Infinity, sum = 0;
while (R < len) {
sum += nums[R];
while (sum >= s) { // Slide window
res = Math.min(res, R - L + 1);
sum -= nums[L];
L++;
}
R++;
}
return res == Infinity ? 0 : res; // Judge the validity
};
Copy the code
Long key entry
Long key entry
Topic describes
Your friend is typing his name on the keyboard. Occasionally, the key may be long pressed when typing the character C, and the character may be typed one or more times.
You will check the typed character on the keyboard. Return True if it might correspond to your friend’s name (some of which might be long pressed).
Example 1:
Enter: name ="alex", typed = "aaleex"Output:trueExplanation:'alex'In the'a' ๅ 'e'By long press.Copy the code
Example 2:
Enter: name ="saeed", typed = "ssaaedd"Output:falseExplanation:'e'It always needs to be typed twice, but in typed output this is not the case.Copy the code
Example 3:
Enter: name ="leelee", typed = "lleeelee"Output:true
Copy the code
Example 4:
Enter: name ="laiden", typed = "laiden"Output:trueExplanation: Long pressing characters in names is not necessary.Copy the code
Tip:
name.length
< = 1000typed.length
< = 1000name
ๅtyped
Are all lowercase characters.
Their thinking
CNT = CNT; CNT = CNT; CNT = CNT; CNT = CNT;
- if
typed
ๅname
If the first digit of the current index is not equal, then the name does not correspond, and directly jumps out, which is a small optimization. - when
typed
Don’t jump out until you’re done. If it’si == n
You jump out words, this kind of circumstance: name: ABC | typed: abcd will judge to make mistakes
/ * * *@param {string} name
* @param {string} typed
* @return {boolean}* /
var isLongPressedName = function (name, typed) {
let n = name.length; // Find the length of the string
let m = typed.length;
let cnt = 0; // Statistics the number of successful matches
let i = 0, j = 0; / / double pointer
let flag = false; // Determine if a mismatch phase is encountered halfway
while (1) {
if (name[i] == typed[j]) { // The match is successful
i++ , cnt++ , j++;
} else {
if (typed[j] == name[i - 1]) {
j++;
} else {
// If the first digit of the typed and name indexes are not equal, the typed and name indexes will be jumped directly
flag = true; }}if (flag) break;
if (j == m) break; / / when typed to jump out, if is I = = n will jump out, this kind of situation: ABC | abcd will judge to make mistakes
}
if (cnt === n && j === m) return true;
else return false;
};
Copy the code
763. Divide letter intervals
763. Dividing letter intervals original problem portal
Topic describes
The string S consists of lowercase letters. We want to divide the string into as many fragments as possible, with the same letter appearing in only one of them. Returns a list representing the length of each string fragment.
Example 1:
Enter: S ="ababcbacadefegdehijhklij"Output:9.7.8] the partition result is"ababcbaca"."defegde"."hijhklij". Each letter appears in at most one fragment. like"ababcbacadefegde"."hijhklij"The partition of is wrong because the number of segments divided is small.Copy the code
Tip:
S
The length of the[1, 500]
In between.S
Contains only lowercase letters'a'
ๅฐ'z'
ใ
Their thinking
This question is a very interesting question, both greedy taste, and have the taste of double pointer, the following is to say how to solve the problem:
First, we maintain a map, which counts the current letter position of the word, and we can record the farthest position of each letter by traversing.
Then, when iterating through the string again, we can get the farthest position of the current letter, and by greedy thinking, we can get the range maxLen for the farthest position of the letter, so that the same letter will only appear in one fragment.
Now that we have maxLen, we also need the I pointer, the tail pointer, to go to this place to count the segments that we can split.
(Consider that if you don’t go to maxLen, the letters in this range may be further away, so the condition that the same letter appears in only one fragment is not satisfied.)
See the stupid Pig demolition team leader diagram.
/ * * *@param {string} S
* @return {number[]}* /
var partitionLabels = function (S) {
let map = {}; // Count the farthest position of the current letter
for (let i = 0; i < S.length; i++) {
map[S[i]] = i; // Store the current position of the current letter
}
let start = 0; / / the head pointer
let res = [];
let maxLen = 0;
for (let i = 0; i < S.length; i++) {
let curMaxLen = map[S[i]];
maxLen = Math.max(maxLen, curMaxLen); // Calculate whether the current range can be extended further
if (i === maxLen) {
let tmp = i - start + 1;
start = i + 1;
res.push(tmp); // Split the fragment}}return res;
};
Copy the code
string
459. Repeated substrings
459. Repeated substring original problem portal
Topic describes
Given a non-empty string, determine whether it can be formed by repeating one of its substrings more than once. The given string contains only lowercase English letters and cannot exceed 10000 characters.
Example 1:
Input:"abab"Output: True Explanation: Can be a substring"ab"Repeat the composition twice.Copy the code
Example 2:
Input:"aba"Output: FalseCopy the code
Example 3:
Input:"abcabcabcabc"Output: True Explanation: Can be a substring"abc"Repeat the composition four times. (Or substrings"abcabc"Repeat the composition twice.Copy the code
Their thinking
For sample strings, look to whether consists of one of them is a repeated sequence of string, we can be the original string joining together with yourself, and then from the original string 1 (start from 0) to find, look to whether can find joining together after the start bit string, namely s.l ength, so there is no repeat such situation, otherwise, there is, Returns True.
/ * * *@param {string} s
* @return {boolean}* /
var repeatedSubstringPattern = function(s) {
return (s+s).indexOf(s,1) !== s.length
};
Copy the code
Description:
I think you might be wondering, hey, why is there only one problem for strings?
First of all, sort out this series of articles, mainly to provide you with some brush questions route ideas, the questions are ever-changing, and a question may have many ways to solve the problem, MOST of the questions I listed are the original questions I have encountered, a guide to the beginning. Second, strings are mostly tied to other algorithms, such as:
- 22. Parenthesis generation (traceback)
- 20. Valid parentheses (stacks)
- 17. Letter combinations for phone numbers (backtrace, DFS)
In addition, I would like to mention that string is a bit more of a palindrome, and a series of related issues, such as: There are original questions in LeetCode, such as horse-drawn cart algorithm, the problem of the longest substring of a palindrome, how to judge a palindrome, and the longest public prefix. I often encountered horse-drawn cart algorithm in written exams and interviews. I still remember that it was encountered by Bytedance at that time. If you haven’t heard of this algorithm, it’s good. At least this article has helped you
As for the letter combination of the phone number in the last article omitted, this is my 2020 spring recruitment Tencent interview real question, at that time was stuck by this question, found that it is not very difficult, now to add:
17. Alphabetic combinations of telephone numbers
17. Telephonic number combination original problem portal (backtrace, DFS)
Topic describes
Given a string containing only the numbers 2-9, return all the letter combinations it can represent.
The mapping of numbers to letters is given as follows (same as a telephone key). Note that 1 does not correspond to any letter.
Example:
Input:"23"Output:"ad"."ae"."af"."bd"."be"."bf"."cd"."ce"."cf"].
Copy the code
Description:
Although the above answers are listed in lexicographical order, you can choose the order in which the answers are printed.Copy the code
Their thinking
With backtracking, we can repeat the selection for the current option, so we start at 0 in the for loop, and we just do a map for the letter combinations.
Refer to xiao_ben_Zhu’s diagram
var letterCombinations = function (digits) {
if(! digits.length)return [];
// Direct mapping
const map = { '2': 'abc'.'3': 'def'.'4': 'ghi'.'5': 'jkl'.'6': 'mno'.'7': 'pqrs'.'8': 'tuv'.'9': 'wxyz' };
let res = [];
let dfs = (cur, start) = > {
if (start >= digits.length) {
res.push(cur);
return;
}
// Take the current optional letter combination
let str = map[digits[start]];
for (let i = 0; i < str.length; i++) {
dfs(cur + str[i], start + 1);
}
}
dfs(' '.0);
return res;
};
Copy the code
Method 2
This is a piece of code written before backtracking, in short, is the use of hierarchical traversal, anyway, every letter can be repeated, directly traversal, and then into the queue.
var letterCombinations = function(digits) {
if(! digits.length)return []
const map = { '2': 'abc'.'3': 'def'.'4': 'ghi'.'5': 'jkl'.'6': 'mno'.'7': 'pqrs'.'8': 'tuv'.'9': 'wxyz' };
let queue = []
queue.push(' ')
for(let i=0; i<digits.length; i++){let size = queue.length
while(size--){
let cur = queue.shift()
let str = map[digits[i]]
for(let j=0; j<str.length; j++){ queue.push(cur+str[j]) } } }return queue
};
Copy the code
In this paper, the reference
- How does the front end prepare data structures and algorithms?
- Write front-end algorithm advanced guide, I am how two months zero basis brush 200 questions
- (1.8W word) How do front-end engineers systematically practice data structures and algorithms? ใ the ใ
- Leetcode && LeetCode, thank you
conclusion
โค๏ธ follow + like + favorites + comments + forward โค๏ธ, original is not easy, your support will be my biggest motivation ~
Visit the oratory blog for convenient reading and playing
Finally, I wish you a happy New Year, the Year of the Ox and good luck. You can finish the spring recruitment as soon as possible. I hope my article can help you and we will meet in the next period soon
Come and follow me. Although the front end of learning is “bitter”, there are 100 Chocolate articles that are even sweeter
ใ Author: 100 Chocolateใjuejin.cn/user/298153…