preface
The react fiber tree corresponds to a data structure called a linked list. The data structure of our new Map in ES6 is actually the data structure of the corresponding dictionary, while the data structure of Set is the data structure of the Set, which is an unordered and unique data structure. And in VUE is also a large number of stack and queue data structure, so, look for information, learn some, record as follows, if there is an error, please big brother advice!
Learning instructions
I’m learning data structure and algorithm, consulted a lot of people, they just tell me directly to brush, so I open the power button ready to brush trip, however, after a brush, found that since there is no system of knowledge, learn fast, forget too fast, the biggest feeling is cannot extrapolate, finally realized that the importance of the knowledge system.
So, turn over the university’s new data structure and algorithm, review again.
Basic knowledge of
First of all, there are several kinds of data structures. We must thoroughly understand what the data structures are, so that we can clearly know what kind of data structures we should use to solve problems when we meet algorithms.
The stack
A stack is a data structure that follows LIFO.Copy the code
However there is no stack in our front end this kind of data structure, but we have the universal array, use it can simulate the stack, and can also derive stack operation method, we know that in the es standard array has two standard method of push and pop, in fact, they can be expressed and into the stack operation method, good, cut the crap, let’s get started!
Class Stack {constructor() {this.stack = [] // Stack length this.size = 0} // push(I) {this.stack[this.size] = I This.size ++} // pop() {if (this.stack.length > 0) {const last = this.stack[--this.size] this.stack.length-- return Peek () {return this.stack[this.size-1]; // Peek () {return this.stack[this.size-1]; } // whether the stack isEmpty isEmpty() {return stack.length === 0; Clear (){this.stack = []} see(){console.log(this.stack) return this.stack}}Copy the codeAt this point, a simple implementation of the front stack is complete
And in our front end, what we call the call stack, which is actually the data structure of the stack, you’ll find that it’s exactly the same as pushing in first and popping out last
The queue
A queue is a first-in, first-out data structure.Copy the code
Class Queue {constructor() {this.queue = [] // Queue length this.size = 0} // Push (I) {this.queue[this.size] = I this.size++} shift() {if (this.queue. Length === 0) {return} const first = this.queue[0 (let i = 0; i < this.queue.length - 1; Queue [I] = this.queue[I + 1]} this.queue. Length -- return first} getFront() {this.queue[0]; GetRear () {return this.queue[this.size-1]} clear() {this.queue = []} console.log(this.queue) return this.queue } }Copy the codeAt this point a simple queue is implemented
In fact, in the front end, our asynchronous events completely conform to the data structure of the queue, fifO, do you still feel that the front end does not need to learn the data structure?
The list
Linear lists stored by chain are collectively referred to as linked listsCopy the codeThe above is the definition of a linked list. If it feels difficult to understand, it is essentially a list of multiple elements, but its elements are stored in a discontinuous way and need to be associated with the next pointer. This is the structure of a linked list, no picture, no truth
Singly linked list
Two-way linked list!
As shown above, a bidirectional list (doubly linked list) is a type of linked list. Like a singly linked list, a double-linked list is made up of nodes, and each data node has two Pointers to direct successors and direct precursors. So, starting from any node in a bidirectional linked list, you can easily access its predecessors and successors. In general, we construct bidirectional circular lists.
With these concepts out of the way, it turns out that there are no linked lists in the front end either. Instead, we can implement a simple linked list using objects,
Var a = {name: '1'} var b = {name:' 1'} var c = {name: '1'} var d = {name:' 1'} var e = {name: '1'} var c = {name:' 1'} var e = {name: '1'} '1'} // create a linked list a.next.b.next.c.next.d.next.eCopy the codeNow that we have a linked list, one might ask, what’s the advantage of a linked list data structure that’s less convenient than an array? We found that linked lists are not contiguous, they are associated by Next, so when we delete, we just need to change the next pointer and delete naturally. However, if you want to delete in an array, you will find that it is quite troublesome
Of course, since a linked list is a data structure, there must be some operations, so let’s see what they have
Let p = a while (a) {console.log(a) p = a.ext ()} const f={name:' 1'} // insert a.ext = f.ext =b after a element // delete the list. // delete the listCopy the codeIn this article, we simulated the traversal, insertion and deletion of the linked list in JS, so we found that the data structure of the linked list is not as difficult as we operate the array
A collection of
A set is made up of a group of unordered but related members, each of which can only appear once in the set. It is an unordered and unique data structureCopy the codeIn previous data structures, there was no front end implementation. Finally, our collection has its own front end Set constructor, which is known as -set. We usually use it to perform array de-duplication.
Set
A set is a new data structure for ES6. A set object is a collection of values that you can iterate over in the order in which they are inserted. Elements in a Set occur only once, that is, the elements in a Set are unique. Let’s look at the basic operation of set
Var s = new Set([1, 2, 3, '3', 4]); // Add a key s.dd (5); // Duplicate elements are filtered automatically in Set. Dd (5); console.log(s); Set {1, 2, 3, 4,5} // delete a key. // check if the element s.haas (3) console.log(s) exists; //Set{1, 3, "3", 4, 5}// Note that the number 3 and string '3' are different elements.Copy the codeSince it’s a set, how can we not find the intersection, the union? Unfortunately, set doesn’t give us a way to do that, but it doesn’t matter, we have arrays, and we can use arrays to solve for intersections
// const arr1=new Set([1,2,4]) const arr2=new Set([2,3,4,5]) new Set([...arr1, // intersection const arr1=new Set([1,3,4,6,7,9]) const arr2=new Set([2,3,4,5,6,7]) const arr=new Set([...arr1].filter((item)=>{arr2.has(item)}))Copy the codeThe dictionary
A dictionary is a data structure that stores unique data in key-value pairsCopy the codeThen you say, “Isn’t this an object?” What’s the difference between him and the object? In ES6, we can use the Map constructor to create a dictionary, right
Map
Cut the crap and get right to the code
/ / create a dictionary const map = new map ([[' a ', 1], [' b ', 2]]). console.log(map);Copy the code
Console. log(map.size); // add key can be a non-primitive type console.log(map.set([1,2],'')); The map. The set (' name ', 'li'). The set (' age, 18); / / query console. The log (map. Get (' name ')); / / remove the console log (map. The delete (' name ')); // Console. log(map.has('name'));Copy the codeWith that said, let’s look at the use of dictionaries for example: find the subscripts of the three largest numbers in an array
======= ======= //1, we can use the dictionary to store the largest three values //2, there is a better way to understand the use of sorting, Function maxThree(arr) {var I = 0; var j = 0; Var TMP = arr[0] var v = 0 var b = new Map() while (I < 3) {while (j < arr) {if (TMP < arr[j] &&! b.has(j)) { tmp = arr[j] v = j } j++ } b.set(v, tmp) i++ j = 0 tmp = 0 } // console.log(b) } maxThree([1, 3, 4, 5, 6, 7, 9, 1, 1, 9, 2, 8, 3, 4, 5,])Copy the codefigure
A graph is an abstract model of a network structure consisting of a set of vertices connected by edgesCopy the codeIf it’s a little confusing, let’s go straight to the picture.
So in our JS, again, there is no graph we can also use arrays and objects to represent a graph, if we use arrays to represent a graph, we will give a name called adjacency matrix, and if we use arrays and objects mixed then we will call it adjacency list, essentially the difference in representation
Adjacency matrix
Let’s say we want to use an adjacency matrix to represent it as shown below
,1,0,0,0 var matrix = [[0], [0,0,1,1,0], [0,0,0,0,1],,0,0,0,0 [1], [0,0,0,1,0]]Copy the codeAs shown in the code, but in fact he is the essence of the horizontal and vertical at the same time have A, B, C, D, E when transverse associated with the formation of longitudinal, then modify the current corresponding to 1, if can be expressed in the form of matrix relationship between each vertex, well, to the adjacency matrix notation, so far, the difficulty is not actually draw A adjacency matrix, But the abstract business logic into an adjacency matrix to solve the problem, such as in the electricity business well-known sku, due to the high complexity of business, all, we write the algorithm often extremely complex business logic, the adjacency matrix to act on the power Interested can look at the points of minutes to learn front-end sku algorithm (specifications to choose more goods)
Adjacency list
Adjacency lists are a lot more intuitive to represent than adjacency matrices, which are pretty abstract, so how do we represent this figure in terms of adjacency lists? Since adjacency lists are relatively simple to create using use cases,
class Graph { constructor() { this.vertices = []; This.adjlist = new Map(); // Add a new vertex to the graph addVertex(v) {if (! this.vertices.includes(v)) { this.vertices.push(v); this.adjList.set(v, []); }} // Add a edge between a and b to the graph addEdge(a, b) {// If there is no vertex a in the graph, add vertex A if (! this.adjList.has(a)) { this.addVertex(a); } // If there is no vertex B in the graph, add vertex B first if (! this.adjList.has(b)) { this.addVertex(b); } this.adjList.get(a).push(b); }} let graph = new graph (); let myVertices = ['A', 'B', 'C', 'D', 'E']; myVertices.forEach((v) => { graph.addVertex(v); }); graph.addEdge('A', 'B'); graph.addEdge('B', 'C'); graph.addEdge('B', 'D'); graph.addEdge('C', 'E'); graph.addEdge('E', 'D'); graph.addEdge('D', 'A'); console.log(graph);Copy the code
The tree
Tree is a very important data structure in computer science. Tree is described as a hierarchical data abstraction model, which is often used to describe hierarchical relationships and organizational structures among data. A tree is also a non-sequential data structure.Copy the code
var tree={
value:1,
children:[
{
value:2,
children:[
{
value:3
}
]
}
]
}
Copy the codeAs shown above, we have simply implemented a tree data structure, but do you think that is enough? It is far from enough. In our tree, there are a number of commonly accepted algorithms called depth-first traversal (DFS) and breadth-first traversal (BFS). First, let’s take a DOM tree and then analyze it
As shown in the figure above, I transformed the DOM into a tree structure
Depth-first traversal (DFS)
Depth-first traversal, as its name implies, is a hierarchical traversal following depth. It traverses the DOM tree in vertical dimensions, starting from a DOM node, traversing its children until all its children have been traversed, then traversing its siblings, and so on until all its nodes have been traversed
His traversal hierarchy is as follows:
div=>ul=>li=>a=>img=>li=>span=>li=>p=>button
Copy the codeThe js code is as follows:
Var dom = {tag: 'div', children: [{tag: 'ul', children: [{tag: 'li', children: [{tag: 'a', children:] [ { tag: 'img' } ] } ] }, { tag: 'li', children: [ { tag: 'span' } ] }, { tag: 'li' } ] }, { tag: 'p' }, { tag: Function DFS(node, nodeList) {if (node) {nodelist.push (node.tag); var children = node.children; if (children) { for (var i = 0; i < children.length; DFS(children[I], nodeList); DFS(children[I], nodeList); } } } return nodeList; } DFS(dom, nodeList) console.log(nodeList)Copy the code
Breadth-first traversal (BFS)
The so-called breadth-first traversal is in the same way, that is, following the traversal of the same level. This method traverses the DOM tree in a horizontal dimension, starting from the first child node of the node, traverses all its sibling nodes, and then traverses the child nodes of the first node. After completing the traversal, it will not go further for the time being. Starts traversing the children of its sibling node in order of traversal:
div=>ul=>p=>button=>li=>li=>li=>a=>span=>img
Copy the codeThe js code is as follows:
Function BFS(node, nodeList) {function BFS(node, nodeList) { If (node) {var q = [node] while (q.length > 0) {var item = q.hift () nodelist.push (item.tag) if (node) {var item = q.hift () nodelist.push (item.tag) if (item.children) { item.children.forEach(e => { q.push(e) }) } } } } BFS(dom, nodeList) console.log(nodeList)``Copy the codeThe result is obvious
In our previous code, we have described multi-fork trees, but in data structures, there is a very important concept called binary trees
Binary tree
Binary Tree is a Tree structure. Each node has at most two branch nodes. A Binary Tree usually consists of root nodes, branch nodes, and leaf nodes. Each branch node is often referred to as a subtree.Copy the codeSo what exactly is a binary tree? If we look at a picture, we can say more than a thousand words
The above is the concept of binary tree, but, in the front, I have not seen the application of binary tree (if there is a big guy know please tell), but still does not prevent us to learn him, and in the binary tree is the most famous is the order traversal, order traversal, and order traversal
So how do we represent binary trees in our front end? We can use object to represent a binary tree
const bt = {
val: 1,
left: {
val: 2,
left: {
val: 4,
left: null,
right: null,
},
right: {
val: 5,
left: null,
right: null,
},
},
right: {
val: 3,
left: {
val: 6,
left: null,
right: null,
},
right: {
val: 7,
left: null,
right: null,
},
},
}
Copy the codeThe above data structure is a simple binary tree, which will have the value of the current node, a left subtree, and a right subtree. Next, the important part, the creation and traversal of the binary tree
Create a binary tree
// arr=[6,5,6,8,9,1,4,3,6] =[6,5,6,8,9,1,4,3,6] 4] class constructor {constructor(key) {// this. Left = null; // Right object this.right = null; // key this.key = key; } } class BinaryTree { constructor() { this.root = null; } insert(key) { const node = new BinaryTreeNode(key) if (this.root === null) { this.root = node } else { InsertNode (this.root, node)}} newNode) { if (node.key < newNode.key) { if (node.left) { this.insertNode(node.left, newNode) } else { node.left = newNode } } else { if (node.right) { this.insertNode(node.right, newNode) } else { node.right = newNode } } } } const tree = new BinaryTree(); arr.forEach(key => { tree.insert(key) }); console.log(tree)Copy the codeIn the sequence traversal
Inorder: InorderTransverse (root, arr) {if (!) {inorderTransverse(root, arr) {if (!) {inorderTransverse(root, arr) {if (! root) return; this.inorderTransverse(root.left, arr); arr.push(root.key); this.inorderTransverse(root.right, arr); } // Use const arrTransverse = [] tree. InorderTransverse (tree. Root, arrTransverse) console.log(arrTransverse)Copy the codeThe first sequence traversal
Preorder: to keep the left node preorderTransverse(root, arr) {if (! root) return; arr.push(root.key); this.preorderTransverse(root.left, arr); this.preorderTransverse(root.right, arr); }Copy the codeAfter the sequence traversal
PostorderTransverse (root, arr) {// Create a stack var stack = []; // Push the root node to the top of the stack. while (stack.length > 0) { let node = stack.pop(); // Use unshift to press the array arr.unshift(node.key); if (node.left) { stack.push(node.left); } if (node.right) { stack.push(node.right); }}} // call const arrTransverse = [] tree. PostorderTransverse (tree. Root, arrTransverse)Copy the codeEr, drill
This question comes from the force button 226, and is a popular interview question, because this is a Homebrew package management tool author, go to Google interview to write the question
//1 /2 3 // 4 5 6 7 // flip the binary tree above //===== 解 决 方 法 ====== //1, if you want to flip the binary tree, you can use the didivide and conquer idea. Function invertTree(bt) {if (! [bt.left, bt.right] = [invertTree(bt.right), invertTree(bt.left)]; return bt } console.log(invertTree(bt))Copy the codeThe heap
What is a heap? It's not even mentioned in the front end, but a heap is a special kind of complete binary treeCopy the codeIn the previous tree we introduced trees, we also introduced binomial trees, what is a complete binomial tree?
As shown in the figure above, it is a complete binary tree, which can also be called full binary tree (some literatures define full binary tree is not complete binary tree, there is no unified standard and standard definition), but complete binary tree is not necessarily full binary tree for example
In the figure above, it is a complete binary tree, but not a full binary tree. What is the definition of a complete binary tree?
If the depth of the binary tree is set as K, except for the KTH layer, the number of nodes of all other layers (1 ~ K-1) reaches the maximum number, and all nodes of the KTH layer are continuously concentrated on the left, which is a complete binary tree.Copy the codeIf the last layer is not full, then only the nodes on the right side must be missing. Then we say again, the heap is a special complete binary tree, so what are its characteristics?
- All nodes are greater than or equal to or less than their children
- If every node is greater than or equal to its children are the maximum heap
- If every node is less than or equal to its children are the minimum heap
So in JS you need to use arrays to represent a heap, why? Since the heap is a complete binary tree, each node must be filled, so that each layer can find a fixed position in the array. In this way, objects are not needed
And then somebody says, what’s the use of a heap? It’s so complicated, and in fact if we look at the structure of the heap, the heap is order 1 in time, and it can quickly find the maximum and minimum values in the heap, so let’s write a minimum heap class
Class MinHeep {constructor() {this.heap = []} // Insert (val) {this.heap. Push (val) this.shiftUp (this.heap.length) - 1)} // swap(I, Heap [v] this.heap[v] this.heap[v] this.heap[v] = temp} var temp = this.heap[I] this.heap[v] this.heap[v] = temp} // shiftUP(index) {if (index === 0) { return } var preIindex = this.getParentIndex(index) if (this.heap[preIindex] > this.heap[index]) { this.swap(preIindex, Index)}} getParentIndex(I) {return (i-1) >> 1}} var h=new MinHeep() h.insert(3) h.insert(1) h.insert(2) h.insert(7) h.insert(4) console.log(h.heap)Copy the codeSo, we’ve got the minimum heap, and if you print the array, you’ll see that yes, the top element of the heap must be the smallest
Time complexity Space complexity
I believe that many people in the brush algorithm, the most heard a word is time complexity and space complexity, so he is what?
So let’s first talk about what is an algorithm? An algorithm is a set of methods for manipulating data and solving program problems. Since it is a set of methods, it has good methods and bad methods. Therefore, people invent two dimensions to calculate good and bad, one is the time dimension and the other is the space dimension
Time dimension: Refers to the time taken to execute the current algorithm, which is usually described by "time complexity". Spatial dimension: Refers to the amount of memory required to perform the current algorithm, which is usually described as "spatial complexity".Copy the codeIn short, the more for loops you use, the more time complexity you have, the more variables you declare the more space complexity you have. Do you think that’s enough? The good guys also came up with a set of representations of time complexity and space complexity.
Said method
What does it mean by what is currently known in the industry as “big O notation”? For example
var a=1
a++
Copy the codeThe above code, we don’t have a for loop found and he has no step changes with the change of a variable, so he is called the O (1), in fact, the computing time complexity has to compare not formula, we are here not to interested please click bosses room the time and space complexity of the algorithm, a see understand)
We just need to remember that the time complexity order is:
- Constant order O (1)
- The logarithmic order O (logN)
- Linear order O (n)
- Linear log order O(nlogN)
- Squared square order O (n)
- Cubic order O (n) after
- Order N to the K.
- The index order (2 ^ n)
Time is getting more and more complicated from top to bottom, so let’s do a couple of examples just to make sense of it
for(i=1; i<=n; ++i)
{
j = i;
j++;
}
Copy the codeWe find that his time varies with n so his time complexity is O(n).
int i = 1;
while(i<n)
{
i = i * 2;
}
Copy the codeAnd since I is increasing by multiples each time it’s going to have less cycles than n, so it’s going to have logN time, and so on and so forth if if the cycle cycle is of order squared
Space complexity degree is relatively simple, space complexity is more commonly used: O(1), O(n), O(n²), to put it bluntly is how many variables you declare, such as
Var a=new Array(n) var a=new Array(n)Copy the codeAdvanced ideas
Finished looking at the basic knowledge, fine again to take stock of advanced thinking
Sorting algorithm
In our algorithm, the sorting algorithm is second to none, but also the interview disaster area, many people are hanging on the above, in fact, the sorting algorithm is quite simple after clear, it is also divided into several bubble sort, select sort, insert sort, merge sort, quick sort, search sort, etc
Bubble sort
1. Compare adjacent elements. If the first one is bigger than the second, swap them both. 2. Do the same for each pair of adjacent elements, starting from the first pair to the last pair at the end. When we do that, the last element is going to be the largest number. 3. Repeat for all elements except the last one. 4. Keep repeating the above steps for fewer and fewer elements at a time until there are no more pairs to compare.
function bubble(arr){ let tem = null; For (let I =0; i<arr.length; I++){// for(let j=0; j<arr.length-1-i; J++) {if (arr [j] > arr [j + 1]) {/ / the current item after more than a, swap places tem = arr [j]; arr[j] = arr[j+1]; arr[j+1] = tem; } } } return arr }Copy the codeBecause bubble sort has two nested cycles, its time complexity is O(n²). Due to the high time complexity, bubble sort is of poor performance in sorting algorithm, so it is basically not used in work, but only used in interviews
Selection sort
1, first find the smallest (large) element in the unsorted sequence, and store it at the beginning of the sorted sequence. 2, continue to find the smallest (large) element from the remaining unsorted elements, and then put it at the end of the sorted sequence. 3. Repeat step 2 until all elements are sorted.
Function selectSort(arr){let length = arr.length; for(let i=0; i<length-1; i++){ let min = i; for(let j=min+1; j<length; j++){ if(arr[min]>arr[j]){ min = j } } if(min! =i){ let temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } } return arr }Copy the codeSelect sort and we find that it’s also two for loops, so it’s also O(n ^ 2), which is bad
Insertion sort
1. Compare from the second number forward. 2. Those older than him go to the back, and so on straight to the end
function insertSort(arr) { let length = arr.length; for(let i = 1; i < length; i++) { let temp = arr[i]; let j = i; for(; j > 0; j--) { if(temp >= arr[j-1]) { break; } arr[j] = arr[j-1]; } arr[j] = temp;} arr[j] = temp; } return arr; } / / example let arr =,5,10,7,10,32,90,9,11,1,0,10 [2] the console. The log (insertSort (arr));Copy the codeInsert sort we find that it’s also two for loops, so it’s also O(n ^ 2), which is bad
Merge sort
2. Merge the two arrays into an ordered array, and merge the ordered array until all the subarrays are merged into a complete array
Function mergeSort(arr) {// Split array if (arr.length === 1) {return arr} const mid = math.floor (arr.length / 2) const left = arr.slice(0, mid) const right = arr.slice(mid, Arr.length) // Recursive const orderLeft = mergeSort(left) const orderRight = mergeSort(right) const res = [] while (orderLeft. Length | | orderRight. Length) {/ / use queue sorting the if digital and pressure into the array (orderLeft. Length & & orderRight. Length) { res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift()) } else if (orderLeft.length) { res.push(orderLeft.shift()) } else if (orderRight.length) { res.push(orderRight.shift()) } } return res } var arr = [1, 4, 6, 7, 9, 5] console.log(mergeSort(arr))Copy the codeAnd since splitting is a recursion, and it’s splitting in half it’s going to be O(logN) and since merging is a while loop it’s going to be O(nlogN), so merge sort is available, So the popular Firefox sort algorithm uses merge sort.
Quick sort
1, the first need to partition, from the array to any select a baseline, and then the value before and after the baseline to compare, if smaller than the baseline, then put in the left array, otherwise put in the right array 2, recursive partition of the subarray know the final and sequence of the subarray
var arr = [2, 4, 3, 5, 1] function quickSort(arr) { if (arr.length === 1 || arr.length === 0) { return arr } const left = [], Const mid = arr[0] const mid = arr[0] for (let I = 1; i < arr.length; I ++) {if (arr[I] < mid) {left.push(arr[I])} else {right.push(arr[I])}} // Recursive console.log(left, right) return [...quickSort(left), mid, ...quickSort(right)] } console.log(quickSort(arr))Copy the codeIf you look at the quicksort code, it looks a lot like merge sort. Yes, it’s diet-and-conquer, and it’s O(nlogN), and Google chrome sort uses quicksort. So what’s the difference?
The difference is that the grouping strategy is different, and the merging strategy is different. The grouping strategy of merging: assuming that the elements to be sorted are stored in an array, the first half of the array is one group and the second half is another group. Quicksort is divided according to the value of the elements, a group of elements greater than a certain value, a group of elements less than a certain value.
Quicksort already groups elements by size, while merge only needs to merge two groups. Merge sort needs to merge two ordered arrays by size
Search algorithm
Finish sorting algorithm, we come to tinker tinker search, search is also our interview high frequency test point, although the basic work is not used, but in order to install force, how can not? Now let’s look at what does search have? Commonly used on two kinds of sequential search, binary search
Sequential search
Sequential search is a very inefficient way of searching, the main idea is to traverse the target array, if you find anything, return -1
/ / mount prototypes don't have to pass two values on the Array. The prototype. SequentialSearch = function (item) {for (let I = 0; i < this.length; i+=1) { if(this[i] === item) { return i; } } return -1; }; Const res = [1,2,3,4,5]. SequentialSearch (3) console.log(res);Copy the codeWe found that the sequential search, in fact, is a simple traversal, so its time complexity is order n.
Binary search
Binary search, as the name implies, splits the array in half and searches it, which greatly improves performance by reducing the number of searches
He started first from an array and if hit element is returned as a result, if not hit, then compare the target and the size of the existing value, if the search value is less than the median, is less than the median step on the part of execution, anyway, but there must be a premise condition, array must be orderly
Array.prototype.binarySearch=function( key) { var low = 0; var high = this.length - 1; while (low <= high) { var mid = parseInt((low + high) / 2); if (key === this[mid]) { return mid; } else if (key < this[mid]) { high = mid + 1; } else if (key > this[mid]) { low = mid - 1; } else { return -1; }} var arr = [1,2,3,4,5,6,7,8]; console.log(arr.binarySearch(3));Copy the codeSince the search area is reduced by half each time, his time is order logN.
Divide and conquer thoughts
What is divide and rule?
Divide and conquer is a method, or idea, in algorithm design
He is not a specific data structure, but an idea, is with in our programming paradigm, for example we have aop programming (section programming), oop (object programming), functional programming, reactive programming, stratified thought, etc., so, our algorithm thoughts and the status of the programming thought is consistent, can be seen how much he important, is to return to of being! What exactly is divide and rule?
What he does is he takes a problem and breaks it down into smaller problems and solves them recursively, and then combines the results to solve the original problemCopy the codeAnd actually we’ve seen this divide-and-conquer idea before, our merge sort and quicksort are classic divide-and-conquer applications
Dynamic programming
Dynamic programming, similar to divide and conquer, is also a method in algorithm design. Similarly, it also decomposes a problem into overlapping sub-problems, and solves the sub-problems to achieve the purpose of solving the original problemCopy the codeSee you feel the same as partition thought here, actually they have the difference, the difference is in the decomposition, partition is the problem is decomposed into independent subproblems, there is no overlap each other, and dynamic programming is decomposed into overlapping subproblems, they are related with each other, for example, take out the classic the Fibonacci sequence, This is a typical application of dynamic programming
Fibonacci numbers
The Fibonacci sequence, also known as the Golden section sequence, was introduced by mathematician Leonardoda Fibonacci as an example of rabbit reproduction. It refers to a sequence of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34Copy the codeSo let’s look at this sequence
We can see that the current element has a special relationship with the previous two elements, and we can define this relationship as a function F, so can we conclude that F(n)=F(n-1)+F(n-2)?
So we can use one formula to find all the Fibonacci numbers, and that’s the typical use of Fibonacci numbers. Actually, the Fibonacci numbers are very useful in mathematics and life and in nature, so I’m not going to go into it here. If you’re interested, why is the Fibonacci sequence so important that almost every book on mathematics mentions it?
Er, drill
Next, let’s take a look at the classic interview question – climbing stairs
The current problem is from the force buckle 70
// Suppose you are climbing stairs. It takes n steps to get to the top. // You can climb 1 or 2 steps at a time. How many different ways can you climb to the top? Note: given n is a positive integer. // Example // Input: 2 // Output: 2 // Explanation: There are two ways to climb to the top of the building. / / 1 1 + 1 order / / 2. The 2 order / / = = = = = = = = = = = = = = = = / / we assume that only three order first, then I defined first, my last step can be a two order, may also be a first order, // If the last step is two steps, we know that there was only one way to get to the last step is two steps. // If the last step is one step, we know that there were two ways to get to the last step. // Since the number of steps in our last step is fixed, so, Var climbStairs = function (n) {var climbStairs = function (n) {var climbStairs = function (n) {// Since our formula is f(n)=f(n-1)+f(n-2), so if n is less than 2 we just return, If (n < 2) {return 1} const dp = [1, 1] // Apply the formula for (let I = 2; i < n; I++) {dp [I] = dp [I - 1) + dp} [I - 2] / / returns the current step method return dp [n]};Copy the codeGreedy algorithm
Greedy algorithm is also a method in algorithm design, he is through the local optimal selection of each stage, so as to achieve global optimalCopy the codeAnd then the truth often backfires, although both are locally optimal, but the result is not necessarily optimal, but certainly better than the worst. It is the fact that it never hits the tick and looks like it is still on the tick that makes the greedy algorithm’s design philosophy survive to this day.
Ok, then, for example, we have 1,2,5 COINS, three kinds of value demands are now we use the minimum of the face value of the coin to add up to 11 yuan, that if you use a greedy algorithm, we in order to use the least amount of COINS, whether need to choose a 5, then choose a 5, finally choose a 1, so we only need three COINS can raise $11, Of course, in this case, this is the optimal solution, so if we switch the coin, we need 1, 3, 4 coins, we need 6 dollars, and if we do the greedy algorithm, then the combination is 4+1+1, whereas the actual optimal solution is 3+3 and we only need 2 of them.
Er, drill
The current problem is from Problem 122
// Specify an array whose ith element is the price of a given stock on the ith day. // Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible. // Note: you can't participate in more than one transaction at a time (you must sell your previous shares before buying again). // Example input: [7,1,5,3,6,4] Output: 7 // Explanation: If you buy on day 2 (stock price = 1) and sell on day 3 (stock price = 5), the exchange will make a profit = 5-1 = 4. // Then buy on day 4 (stock price = 3) and sell on day 5 (stock price = 6), and the exchange makes a profit = 6-3 = 3. S //======= ========= // 1, since we can get the stock trend array at the beginning, so we know the stock result // 2, since we know the stock result, then using the greedy algorithm principle, We consider only local optimum solution / / 3, only need to traverse the entire array detection is rising day, we bought and operation, the decrease of the motionless, so never loss / / 4, the use of greedy algorithm idea is, however, I can't lose money, the advantage is easy to understand, if you are using the dynamic programming, Var maxProfit = function (prices) {var profit = 0 for (var I = 1; i < prices.length; If (TMP > 0) {profit += profit}} return profit}; if (TMP > 0) {profit += profit}} return profit};Copy the codeBacktracking algorithm
Backtracking algorithm is also an idea in algorithm design, which is a strategy to gradually find and build a solution to the problemCopy the codeThe basic idea is to find a possible way to go, if not, go back to the previous step, continue to choose another way, until the problem is solved, backtracking algorithm is a violent solution method, with a trial-and-error idea, because it is famous for its simplicity, so it is also commonly known as the universal solution method.
For example, when we are in school, we all encounter the complete permutation problem, which is to arrange 1, 2 and 3 in different order and not repeat, and then ask to figure out how many permutations there are, so this is a typical backtracking algorithm to solve the problem.
Their thinking
1. Simulate all situations recursively
2. If there is a duplicate element, go back to the previous step (colloquial for backtracking)
Collect and return all non-repeating orders
// Given a sequence without repeating digits, return all possible permutations. // input: [1,2,3] / / / / / [1, 2, 3], / / [31] 1, / /,1,3 [2], / /,3,1 [2], / /,1,2 [3]. / / 3, 2, 1] / / / / = = = = = = = = = title = = = = = = = = = = = / / 1, using backtracking algorithm / / 2, will not repeat Numbers into an array of each location at a time, if meet the conditions, Const permute = (nums) => {const res = []; var dfs = function (path) { if (path.length === 3) { res.push(path); Return} nums.forEach(element => {if (path.concat(element)) {return} DFS (path.concat(element))}); } dfs([]) console.log(res) }; permute([1, 2, 3])Copy the codeSome of the routines
Sliding window, double pointer
This question comes from the third question
// Input: s = "abcabcbb" // output: 3 // Explanation: Since the longest string without repeating characters is "ABC", its length is 3. / / = = = = = = = way = = = = = = = = / / 1, this is the need to have the answer pattern, for example, using the double pointer, Var lengthOfLongestSubstring = function (s) {var l = 0, r = 0, Max = 0; Const mapObj = new Map() while (r < s.length) {if (mapobj.has (s[r]) && mapObj.get(s[r]) >= l) { l = mapObj.get(s[r]) + 1 } max = Math.max(r - l + 1, max) mapObj.set(s[r], r) r++ } console.log(max) }; lengthOfLongestSubstring('djcqwertyuhjjkkiuy')Copy the codeBe good with Maps
This question comes from the place where the dream of the first question began. When I first saw this question, the first reaction was the violent solution method, two-layer traversal. However, referring to other people’s routines, I found that using Map can directly reduce the time complexity to O(N)
// Given an array of integers nums and a target value target, find the two integers in the array and the target values and return their array subscripts. // You can assume there is only one answer for each type of input. However, the same element in an array cannot be used twice. // Given nums = [2, 7, 11, 15], target = 9 // Because nums[0] + nums[1] = 2 + 7 = 9 1] //======= 答 案 参 考 答 案 ========= //1, There are two ways to solve this problem. 4. The idea is to archive all the elements, and when other elements come in, Var twoSum = function (nums, target) {var obj = new Map() nums.foreach ((item, I) = > {/ / if found back the if (obj) from the (nums [I])) {the console. The log ([obj. Get (nums [I]), Set (target-nums [I], I)}} else {// Record object and store subscript obj. twoSum([2, 7, 11, 15], 18)Copy the codeHow fast a pointer
This topic comes from the circular linked list of force buckle 141
This topic has a great influence on me. He changed my ideas and concepts to a great extent and made me understand that if you want to learn an algorithm well, you have to learn it by rote and memorize routines. The real algorithm ability is all out of practical practice
// input: head = [3,2,0,-4], pos = 1 // output: true // explanation: there is a ring in the list whose tail is connected to a second node. //======== solution idea ========== //1, in my initial time is also violent solution method is also the normal thinking can think of //2, through all nodes, each traversal to a node, determine whether the node has been visited before. //5, the idea is to create two Pointers, one to go two next, one to go one next, if the last two meet, /** * @param {ListNode} head * @return {Boolean} */ var head = {val: 3} var head1 = {val: 2 } var head2 = { val: 0 } var head3 = { val: -4 } head.next = head1 head1.next = head2 head2.next = head3 // head3.next = head1 var hasCycle = function (head) { var Var fast = head var fast = head var fast = head var fast = head var fast = head While (fast && fast. Next) {slow = slow. Next fast = fast.next. Return circular pointer if (slow == fast) {console.log(true) return true}} console.log(false) return false}; hasCycle(head)Copy the codeConsider the strange set of problems temporarily to this, the follow-up brush to slowly update
The last
Intermittent algorithm learnt finally finished a month, the above is my method of learning algorithm, first understand the basic knowledge of data structure, to have a purpose of brush related subject, such data structure and algorithm of the system is one of the imprinted in my mind, thought can buckle potent killed four side, unexpectedly, or wall, finally understand, Routines are popular since ancient times, want to algorithm overcome, there is no quick way, he was like memorizing words, have you read today, may forget, tomorrow want to control algorithm, only four words – hand cooked, only, that is, the more you see, naturally, because our normal thinking, is far from these problem solving routines can not think of, only to see more, can extrapolate, The future road is still very long, write this article only to record the exploration process, and cause the interest of the comrades who have not yet entered the door, wrong place hope big guy criticism, the road is long, its repair far xi, everyone refuelling!