Writing in the front
When gold, silver and four, even if the epidemic can not stop you to run (Tiao) to (CAO) big (Zhang) factory (XIN) heart. The first pass on the road to Dachang is the written test, and the written test is the algorithm.
A front-end engineer is, first and foremost, a software engineer
Data structures and algorithms are one of the necessary skills for software engineers, as well as for us front-end engineers. Although you may say that I do not use any knowledge about algorithms in my daily work, what I really master about algorithms is its logical thinking ability, which is very important for an engineer. Therefore, from today on, I decided to relearn the data structures and algorithms commonly used in the front end.
In this advertisement: front-end algorithm summary is my reading in the front-end algorithm and data structure of the small volume of reading + some of their own related accumulation combined, strongly suggest you to subscribe to the small volume of repair speech, vivid, simple and easy to understand. (Online request more…)
Several data structures that need to be mastered to open (mian) and send (SHI) the front-end
First list the front-end development needs to master the data structure:
- An array of
- 栈
- The queue
- The list
- Tree (binary tree)
This article starts with arrays, which front-end developers are most familiar with.
An array of
Arrays are probably one of the most frequently used data structures in everyday development, and they are the most familiar. Array is widely used in data structure, from the most familiar one-dimensional array, to the two-dimensional array, and stack and queue implementation, all need to rely on array to complete.
Create an array
When it comes to creating an array, you should have a lot of different methods in mind. For example, you can create an empty array.
/ / 1
const arr = [];
/ / 2
const arr = new Array(a)/ / 3
const arr = Array.of()
/ / 4
const arr = Array.from([])
Copy the codeIn algorithmic scenarios, we often need to create an array of specified length and populate it with initial values. The common implementation methods are as follows:
// Create an array of length 3 and element values 0
const arr = (new Array(3)).fill(0) / / [0, 0, 0]
Copy the codeAccess to an array
The access complexity of an array is O(1), because we can query an element of the array directly by subscripting it.
const arr = (new Array(3)).fill(0) / / [0, 0, 0]
// Access the second element
arr[1] / / 0
Copy the codeThrough the array
There are dozens of ways to traverse a number group in JS: for loop, forEach, for of, for in, map, filter, reduce, every, some, find, and so on. If there is no special need, then it is recommended to use a for loop to iterate over a group of numbers. Because the for loop is the best in terms of performance.
2 d array
A two-dimensional array, as the name implies, is a one-dimensional array where every element is an array.
const arr = [
[0.0.0],
[1.1.1],
[2.2.2]]Copy the codeIn algorithmic problems, two-dimensional arrays have other, more common names: matrices or checkerboards. (So just look at these two keywords and create a two-dimensional array.)
Creating a two-dimensional array
So how do you create a two-dimensional array? Many people might think to do this with the fill method, which creates a one-dimensional array.
const arr = (new Array(3)).fill([]) / / [[], [], []]
Copy the codeThis seems fine, but if you want to assign a value to an element, the problem arises:
// Assign 1 to the first column of the first row of the two-dimensional array
arr[0] [0] = 1;
console.log(arr); / / [[1], [1], [1]]
Copy the codeAs a result, we assign to only one element in the two-dimensional array, but change the values of all the elements. This is due to fill’s filling mechanism: when the argument you pass to fill is a reference type (such as the empty array passed above), fill is actually filling its reference. That is, the three empty filled arrays point to the same memory space, they are actually the same array.
So for how to create a two-dimensional array, it is recommended to create it through a for loop:
for(let i=0; i<arr.length; i++) {
arr[i] = []
}
Copy the codeAccessing a two-dimensional array
Accessing a two-dimensional array is the same as accessing a one-dimensional array by subscript. To access an element in a two-dimensional array exactly, you need to access its row and column:
arr[0] [1]; // Access the first row and second column of the two-dimensional array arR
Copy the codeIterate over a two-dimensional array
Traversing a one-dimensional array requires one for loop, so traversing a two-dimensional array requires two for loops:
let len = arr.length;
for(let i=0; i<len; i++) {
for(let j=0; j<len; j++) {
console.log(arr[i][j]) // Access row I, JTH element}}Copy the codeAn interview question
Here is a personal interview question I have experienced, roughly the meaning of the question is as follows:
Now we have an 8 by 8 checkerboard, marked with 1 if it’s a car, and 0 if it’s anything else. If there are two cars in either vertical or horizontal, you win, otherwise you lose. Find the output
If you see the checkerboard, you can convert it to a two-dimensional array. So you can easily convert this problem to: a two-dimensional array of 8 by 8, print true if there are two 1’s in one row or one column, and false otherwise.
const func = (arr) = > {
let len = arr.length;
// Iterate over a two-dimensional array
for(let i=0; i<len; i++) {
let num1 = 0; // Record the number of horizontal 1 occurrences
for(let j=0; j<len; j++) {
let num2 = 0; // Count the number of 1s in the vertical column
// arr[I][j
if(arr[i][j] === 1) {
num1++;
}
// arr[j][I
if(arr[j][i] === 1) {
num2++;
}
if(num1 > 1) return true
if(num2 > 1) return true}}return false
}
Copy the codeIs an array in JS really an array?
The first thing to know about this problem is what an array really is. In various official definitions, true arrays have one requirement: they are stored in contiguous memory. In JS, arrays are real arrays in most cases, such as:
const arr = [1.2.3]
Copy the codeBut an array is not really an array when its elements have more than one type:
const arr = ['1'.2.true]
Copy the codeIn this case, the array corresponds to a segment of discontinuous memory space, and its underlying memory space is allocated by hash mapping, which is realized by linked list objects. But in real algorithm problems, most of the time we’re going to use real arrays. Because arrays are stored in contiguous memory space, adding or deleting elements at any location in the array must be moved to the next element, so the complexity of adding/deleting an array is O(n).
A few common array algorithm problems
(Part of the title from Leetcode)
The two Numbers
Given an array of integers nums and a target value target, find the two integers in the array and return their array subscripts: Given nums = [2, 7, 11, 15], target = 9
Knock on the blackboard: Almost any summation problem can be transformed into a difference problem. If you are doing this as a summation, it is likely to be a two-level for loop, recording the first level as a and the second level as b, and then calculating whether a+b equals target. Obviously, the time complexity of the two-level loop is O(n ^ 2), which is definitely not an optimal solution. After transforming into the difference problem, there are many kinds of solutions to this problem. Let’s analyze them one by one:
Method 1: Use Map
When iterating through a set of numbers, Map is used to record the iterated elements and their corresponding cords. ; Then, when traversing the new element, calculate the diff value of the difference between it and target, and find if there is already an element with a key of diff in the Map. If it already exists, print the answer
const twoSum = function(nums, target) {
let targetMap = new Map(),
len = nums.length;
for(let i=0; i<len; i++) {
let diff = target - nums[i];
if(targetMap.has(diff)) {
return [i, targetMap.get(diff)]
}
targetMap.set(nums[i], i);
}
return[]}.Copy the codeMethod 2: colliding Pointers
Colliding Pointers are two Pointers at the head and tail of an array, each moving toward the middle. If the value of a double pointer is greater than target, then the right pointer goes to the left. Otherwise, the left pointer goes right; When it’s target, that’s what we want. But this method has one very important premise, it must be an ordered array.
// Assume that nums is ordered
const twoSum = function(nums, target) {
let left = 0,
right = nums.length- 1;
while(left < right) {
let sum = nums[left] + nums[right];
if(sum === target) {
return [left, right]
}
if(sum > target) {
right--;
}
if(sum < target) {
left++
}
}
return[]}.Copy the codeThree Numbers
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. Example: for a given array nums = [1, 0, 1, 2, 1, 4], meet the requirements of the ternary group collection: [[- 1, 0, 1], [1, 1, 2]]
Well, the old summation problem turns into a difference problem. Fix one value, and then look for the remaining elements to see if there are two elements whose sum with the fixed value is 0. The left pointer is set at the position of the element next to the element, and the right pointer is set at the end of the array. If the sum of the three numbers is greater than 0, the right pointer moves to the left; If less than 0, the left pointer moves to the right; Equals 0, the result is output. And don’t forget that an important prerequisite for the two-pointer solution is ordered arrays
const threeSum = function(nums, target=0) {
/ / sorting
nums.sort((a,b) = > a - b);
let len = nums.length,
res = []; // Result array
for(let i=0; i<len; i++) {
if(nums[i] > target) break
// The question is not repeated
// Fixed element decrement
if(i>0 && nums[i] === nums[i- 1]) {
continue
}
let left = i+1,
right = len- 1;
while(left < right) {
const sum = nums[i] + nums[left] + nums[right];
if(sum === target) {
res.push([nums[i], nums[left], nums[right]]);
// the left pointer is de-weighted
while(left<right && nums[left] === nums[left+1]) {
left++;
}
// The right pointer is de-weighted
while(left<right && nums[right] === nums[right- 1]) {
right--;
}
left++;
right--;
} else if(sum < target) {
left++;
} else{ right--; }}}return res
}
Copy the codeMerges two ordered arrays
Merge nums2 into nums1 to make nums1 an ordered array. Note: The number of elements initialized for nums1 and nums2 is m and N, respectively. You can assume that NUMs1 has enough space (space size greater than or equal to m + n) to hold elements in NUMs2. Example: input: nums1 =,2,3,0,0,0 [1], m = 3 nums2 = [6] 2, n = 3 output:,2,2,3,5,6 [1]
Method 1: JS merge array and sort
For those of you familiar with JS array operations, the first idea of this problem must be to merge arrays first, and then sort. Insert nums2 into nums1 using splice:
const merge = function(nums1, m, nums2, n) { nums1.splice(m, n, ... nums2);// nums2 is inserted into nums1
let sortNums = nums1.sort((a, b) = > a - b); / / sorting
return sortNums.filter(i= >i ! = =0); // Reserved space >= m+n, filter 0
}
Copy the codeMethod 2: double pointer
However, the standard solution to this problem — the one the interviewer wants most — is to use a two-pointer. Ideas:
- Set a pointer at the end of each array
- Compare the size of the elements at the two array Pointers and populate the larger element at the end of the container array nums1. The reason for filling elements from back to front is that the container array nums1 has elements at the head and none at the tail, which gives us a pit to fill in
- Since nums1 and nums2 are not necessarily equal in length, when nums1 is traversed, if nums2 has any remaining nums2 elements, the remaining NUMs2 elements should be filled into the nums1 header
- Otherwise, nums2 traversal is complete, nums1 still has elements left, no processing is required. Because NUMs1 itself is the result array we want to get
const merge = function(nums1, m, nums2, n) {
let i = m- 1,
j = n2 -,
k = m + n - 1; // k represents the nums1 tail index of the container array
// The loop boundary is completed for one of the arrays
while(i>=0 && j>=0) {
// Populate the end of the container array nums1 with larger elements
if(nums1[i] >= nums2[j]) {
nums1[k] = nums1[i];
i--;
k--;
} else{ nums1[k] = nums2[j]; j--; k--; }}// If nums2 has elements left
while(j>=0) { nums1[k] = nums2[j]; j--; k--; }}Copy the codeThe array a
Realization of an array, the multidimensional arrays into one dimensional array input: [1, [2,,4,2 [3], 2], 5, [6]], output:,2,3,4,2,2,5,6 [1]
I believe that many people have been exposed to this problem, and there are many ways to implement it, such as using the array in ES2019 new API — flat
Method 1: Array. Prototype. Flat
let arr = [1[2[3.4.2].2].5[6]].console.log(arr.flat(Infinity)); / /,2,3,4,2,2,5,6 [1]
Copy the codeAnd if you want to implement a flat yourself, what should you do? If you already have an algorithm in mind, you should be quick to think of using recursion. (This is probably what the interviewer is looking for.)
Method 2: Recursion
function flatten(arr){
var array = [];
arr.forEach(ele= > {
if(Array.isArray(ele)){
// If the element is an array, recursearray.push(... flatten(ele)); }else{ array.push(ele); }})return array;
}
Copy the codeWrite in the last
This paper simply summarizes the array and two-dimensional array, as well as some more common array related algorithm problems and their solution methods and ideas. As Xiuyan said in the chapter of arrays, arrays are almost the “cornerstone” of JavaScript data structures. In fact, there’s a lot more to the use of arrays in front-end algorithms. For example, stacks and queues mentioned above, special operations related to strings, and common sorting and lookup algorithms are all implemented based on arrays. I will summarize these in the subsequent learning process.