Stack –

1. Stack application scenarios

Scenario 1: Switch from decimal to binary

  • The remainder that comes out after is going to come out first
  • By pushing the remainder one by one, reverse output can be achieved

Scenario 2: Valid parentheses

  • The more advanced the left parenthesis, the more advanced the corresponding left parenthesis.
  • Open parentheses on the stack, close parentheses off the stack, and finally empty stack is legal.

Scenario 3: Function call stack

  • The function called last is executed first.
  • The JS counting interpreter uses stacks to control the order of calls.

2. Stack actual combat

1. Valid parentheses

20. Valid parentheses – LeetCode (leetcode-cn.com)

Ideas:

  • For open parentheses that are not closed, the further back the open parentheses are, the further forward the corresponding close parentheses are
  • To satisfy lifO, consider using stacks

Steps to solve the problem:

  • Create a new stack.
  • Scan the string, encounter the left parenthesis on the stack, encounter and stack bracket type match the right parenthesis out of the stack, the type cannot match directly judged illegal.
  • Finally empty stack is legal, otherwise illegal
var isValid = function(s) {
    // Optimization point: If the string length is odd, return false
    if(s.length % 2= = =1) return false
    // create a stack
    const stack = []
    for(let i=0; i<s.length; i++){const c = s[i]
        //2.1 Check whether the parenthesis is left, then push the stack
        if(c === '(' || c === '{' || c === '['){
            stack.push(c);
        } else{
        If the parentheses match the same parentheses, the same parentheses will be removed from the stack; if the parentheses match the same, the different parentheses will be pushed onto the stack
            const t = stack[stack.length - 1]
            if(
                (t === '(' && c ===') ') ||
                (t === '{' && c ==='} ') ||
                (t === '[' && c ==='] ') 
            ){
                stack.pop()
            } else{
                return false}}}//3. Check whether the stack is empty. Return true if it is empty, false otherwise
    return stack.length === 0;
};
Copy the code

3. Summary of stack

  • A stack is a lifO data structure
  • There is no stack in JavaScript, but you can use all the functionality of Array.
  • Stack common operations: push(push), pop out of the stack, stack[stack.length-1]

– the queue

  • A fifO data structure.
  • There are no queues in JavaScript, but you can do everything with Array

1. Application scenarios of queues

Scene 1: Queue for lunch in canteen

  • Only one window is left in the canteen.
  • First in, first out, order guaranteed.

Scenario 2: Task queues in JS asynchrony

  • Js is single-threaded and cannot handle concurrent tasks in asynchro.
  • Use task queues to process asynchronous tasks sequentially.

Scenario 3: Calculate the number of recent requests

  • Join the team if there is a request, the request sent before 3000ms is out of the team
  • The length of the queue is the number of recent requests
Input: inputs = [[], [1], [100], [3001], [3002]] output: [null, 1, 2, 3]Copy the code

2. Platoon combat

1. Number of recent requests

933. Recent Number of requests – LeetCode (leetcode-cn.com)

Ideas:

  • The earlier a request is made, the earlier it is not within the last 3000ms
  • For fifO, consider using queues

Steps to solve the problem:

  • Let’s create a queue

  • Join the queue when there is a request, and send the request before 3000ms out of the queue

  • The length of the queue is the number of recent requests

var RecentCounter = function() {
    this.queue = []
};

/ * * *@param {number} t
 * @return {number}* /
RecentCounter.prototype.ping = function(t) {
    this.queue.push(t)
    while(this.queue[0] < t - 3000) {this.queue.shift()
    }
    return this.queue.length;
};
Copy the code

3. Queue summary

  • A queue is a first-in, first-out data structure.
  • There are no queues in JavaScript, but you can Array everything you do
  • Queue operations: push, Shift, queue[0]

– list

What is a linked list

  • A list of multiple elements
  • The elements are stored discontiguously, connected by the next pointer.

2. The difference between arrays and linked lists

  • Arrays: Adding and removing non-beginning and end elements often requires moving elements
  • Linked list: Add and remove non-beginning and end elements, no need to move elements, just change the point to next.

3. Linked list in JS

  • There are no linked lists in JavaScript
  • You can use Object to simulate linked lists
const a = {val:'a'}
const b = {val:'b'}
const c = {val:'c'}
const d = {val:'d'}
a.next = b;
b.next = c
c.next = d

// Iterate over the list
let p = a;
while(p){
    console.log(p.val);
    p = p.next
}
Copy the code

4. Practice lists

1. Delete linked lists

237. Remove nodes from linked Lists – LeetCode (leetcode-cn.com)

Answer:

  • The deleted node cannot be obtained directly.
  • The deleted node is transferred to the next node.
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
};
Copy the code

2. Reverse the linked list

206. Reverse Linked Lists – Force Links (LeetCode) (leetcode-cn.com)

Answer:

  • Reverse the two nodes: point next of n+1 to n
  • Reverse multiple nodes: Double pointer traverses the list, repeating the above operation.

Steps to solve the problem:

  • Two Pointers traverse the linked list one after the other
  • Reversed double pointer
var reverseList = function(head) { let p1 = head let p2 = null while(p1){ const temp = p1.next p1.next = p2 p2 = p1 p1 =  temp } return p2 };Copy the code

3. Add two numbers

2. Add two numbers – LeetCode (leetcode-cn.com)

Ideas:

  • Elementary school math problem, simulation addition operation
  • You need to walk through the list

Steps to solve the problem:

  • Create an empty linked list
  • Iterate over the two lists to be added, simulating the addition operation, appending the units digit to the new list, the tens digit to the new list, and the tens digit to be added next.
var addTwoNumbers = function (l1, l2)
{
    const l3 = new ListNode(0)
    let p1 = l1
    let p2 = l2
    let p3 = l3
    let carry = 0;
    while(p1 || p2){
        const v1 = p1 ? p1.val :0
        const v2 = p2 ? p2.val :0
        const val = v1 + v2 + carry;
        carry = Math.floor(val / 10)
        p3.next = new ListNode(val % 10);
        if(p1) p1 = p1.next
        if(p2) p2 = p2.next
        p3 = p3.next
    }
    if(carry){
        p3.next = new ListNode(carry)
    }
    return l3.next
};
Copy the code

4. Delete the duplicate elements in the sorted list

83. Delete duplicate elements from sorted lists – LeetCode (leetcode-cn.com)

Ideas:

  • Because lists are ordered, all repeating elements must be adjacent
  • Iterate through the list and delete the next element if the current element is found to have the same value as the next element

Steps to solve the problem:

  • Iterate through the list and find that the current element is the same as the next element, and delete the next element value
  • After traversal, return to the head of the original list
var deleteDuplicates = function(head) {
    let p = head
    while(p&&p.next){
        if(p.val === p.next.val){
            // Remove the latter term
            p.next = p.next.next
        } else{
            p = p.next
        }
    }
    return head
};
Copy the code

5. Circular lists

141. Circular Lists – Force Links (LeetCode) (leetcode-cn.com)

Ideas:

  • Two people start at the same time from the starting point of the circular playground, and the fast one is sure to pass the slow one lap
  • Use a slow pointer to traverse the list. If the Pointers can meet, the list is circular.

Steps to solve the problem:

  • Traverse the list with a fast pointer and a slow pointer, returning true if the Pointers can meet
  • After traversal, return false if no encounter has occurred
var hasCycle = function(head) {
    let p1 = head;
    let p2 = head;
    while(p1 && p2 && p2.next){
        p1 = p1.next;
        p2 = p2.next.next;
        if(p1 === p2) return true
    }
    return false
};
Copy the code

6. Prototype chain in JS

1. Introduction to the prototype chain

  • The essence of a prototype chain is a linked list
  • The nodes of the prototype chain are various prototype objects.
  • Stereotype chains link various stereotype objects through the __ proto __ attribute

2. What does the prototype chain look like

-> represents __ proto __ links

  • obj -> Object.prototype -> null
  • func -> Fuction.prototype -> Object.prototype -> null
  • arr -> Array.prototype -> Object.prototype -> null

Knowledge:

  1. A instanceof B is true if A can find b. prototype along the prototype chain

  2. If no x property is found on the A object, the x property is searched along the stereotype chain.

Object.prototype.x = 'x'
Function.prototype.y = 'y'
const func = () = > {};
console.log(func.x);//x
console.log(func.y);//y
Copy the code

Hand write an instanceof:

1

Solution: Iterate through the prototype chain of A, returning true if b. prototype is found, false otherwise

const Myinstanceof = (A,B) = >{
    let p = A
    while(p){
        if(p === B.prototype){
            return true;
        }
        p = p.__proto__;
    }
    return false;
}
Copy the code

7. Front-end and linked list: Use the linked list to retrieve JSON node values

const json ={
    a: {b: {c:1}},
    d: {e:2}}const path = ['a'.'b'.'c']
let p = json
path.forEach(k= >{
    p = p[k];
})
//p:1
Copy the code

5. Linked list summary

  • The linked list elements are not stored contiguously and are connected by next
  • There are no linked lists in JavaScript, so you can simulate linked lists with Object
  • Linked list common operations: modify next, traversal the list
  • The JS prototype chain is also a linked list, connected by __ proto __
  • You can use a linked list to get the value of the JSON node

Set –

1. What is a set

  • A kind ofUnordered and uniqueThe data structure of.
  • ES6 has a collection called Set.
  • Common de-duplication operations of sets: de-duplication, to determine whether an element is in the set, and to find the intersection

2. 4. Smart water bottle

1. Intersection of sets

349. Intersection of two Arrays – Force buckle (LeetCode) (leetcode-cn.com)

Ideas:

  • Find intersection and unordered unique
  • Using the collection

Steps to solve the problem:

  • Deduplicate nums1 with sets
  • Iterate through nums1 to filter for values that nums2 also contains
var intersection = function(nums1, nums2) {
    let set = new Set(nums1)
    let set2 = new Set(nums2)
    return [...set].filter(item= > set2.has(item))
};
Copy the code

3. Set operation

  • Use Set objects: new, add, delete, has, size
  • Iterative Set: multiple iterative methods, Set and Array interconversion, intersection/difference Set

The specific operation can be seen in the following code:

let MySet = new Set(a);/ / the add method
MySet.add(1)
MySet.add(5)
MySet.add(5)
MySet.add('some text')
let o = {a: 1.b: 2}
MySet.add(o)
MySet.add({a:1.b:2})

/ / from the method
const has = MySet.has('some text')

/ / delete method
MySet.delete(5)

// The iterative method
for(let item of MySet) console.log(item);
for(let item of MySet.keys()) console.log(item);
for(let item of MySet.values()) console.log(item);
for(let [key,value] of MySet.entries()) console.log(key,value);

//Array and Set interrotate

/ / Set the switch Array
// 1
const myArr1 = [...MySet]

// 2. Array array. from method
const myArr2 = Array.from(MySet)

/ / Array transformation Set
const MySet2 = new Set([1.2.3.4])


// find the set of intersection and difference
/ / intersection
const intersection = new Set([...MySet].filter(x= > MySet2.has(x)))

/ / difference set
const difference = new Set([...MySet].filter(x= >! MySet2.has(x)))Copy the code

– a dictionary

1. What is a dictionary?

  • Like collections, a dictionary is a data structure that stores unique values, but it is a data structure that stores unique valuesKey/value pairIn the form of
  • ES6 has a dictionary named Map.
  • Dictionary common operations: add, delete, change and check key – value pairs.
const m = new Map(a)/ / to add
m.set('a'.'aa')
m.set('b'.'bb')

/ / delete
m.delete('b') // Delete by key
// m.clear() // delete all

/ / change
m.set('a'.'aaa')

/ / check
m.get('a')
Copy the code

2. Dictionary practice

1. Intersection of two arrays

349. Intersection of two Arrays – Force buckle (LeetCode) (leetcode-cn.com)

Ideas:

  • Find both nums1 and nums2
  • Create a dictionary mapping to record the values in NUMs1.
  • Iterate through nums2 to find values that are also in nums1.

Steps to solve the problem:

  • Create a new dictionary, iterate through NUMs1, and populate the dictionary.
  • Iterate through NUMs2, select the value of the dictionary as it encounters it, and delete it from the dictionary.
var intersection = function(nums1, nums2) {
    let map = new Map()
    nums1.forEach(n= > {
        map.set(n,true)})const res = []
    nums2.forEach(n= > {
        if(map.get(n)){
            res.push(n)
            map.delete(n)
        }
    })
    return res
}

// Time complexity O(m + n)
// Space complexity is O(m)
Copy the code

2. Valid parentheses

20. Valid parentheses – LeetCode (leetcode-cn.com)

Dictionary optimization stack judgment:

var isValid = function(s) {
    if(s.length % 2= = =1) return false;
    const stack = [];
    const map = new Map(a); map.set('('.') ');
    map.set('{'.'} ');
    map.set('['.'] ');
    for(let i = 0; i < s.length; i++){const c = s[i]
        if(map.has(c)){
            stack.push(c)
        } else{
            const t = stack[stack.length - 1];
            if(map.get(t) === c){
                stack.pop();
            } else{
                return false}}}return stack.length === 0
}
Copy the code

3. Add two numbers

1. Sum of two numbers – LeetCode (leetcode-cn.com)

  • Think of NUMs as kissers.
  • Think of target as a matching condition.
  • Set up a marriage agency with a dictionary to store the numbers and subscripts of your loved ones

Problem solving mechanism:

  • Create a new dictionary as a marriage agency.
  • Nums in the value, one by one to introduce the object, there is no suitable on the first registration, there is a suitable hand success.
var twoSum = function(nums, target) {
    const map = new Map(a);for (let i = 0; i < nums.length; i++) {
        const a = target - nums[i]
        if (map.has(a)) {
            return [map.get(a),i]
        }
        else{
            map.set(nums[i],i)
        }
    }
};
// The time complexity is O(n). The space complexity is O(n).
Copy the code

4. The oldest string without repeating characters

3. The largest string without repeating characters – LeetCode (leetcode-cn.com)

Ideas:

  • Start by finding all substrings that do not contain repeating characters
  • Find the substring with the largest length and return its length

Steps:

  • Maintains a sliding window with double Pointers for clipping substrings
  • Keep moving the right pointer, and when it encounters a repeating character, move the left pointer to the next digit of the repeating character
  • Process, record the length of all Windows and return the maximum value.
var lengthOfLongestSubstring = function(s) {
  let left = 0
  let res = 0
  const map = new Map(a)for(let right = 0; right<s.length; right++){if(map.has(s[right]) && map.get(s[right]) >= left){
          left = map.get(s[right]) + 1 // Same slide one bit
      }
      res = Math.max(res,right - left + 1)
      map.set(s[right],right)
  }
  return res
};
// Time complexity O(n) space complexity O(m) m is the length of the non-repeating substring
Copy the code

5. Minimum coverage substring

76. Minimum Coverage substring – Force buckle (LeetCode) (leetcode-cn.com)

Ideas:

  • So let’s find all the substrings that contain T
  • Find the smallest substring and return it

Steps:

  • Maintain a sliding window with double Pointers
  • Move the right pointer to find the substring containing T, and move the left pointer to minimize the length of the substring containing T
var minWindow = function(s, t) {
    let l = 0;
    let r = 0;
    const need = new Map(a)for(let c of t){
        need.set(c , need.has(c)? need.get(c) + 1 : 1) // Determine how many T characters are required
    } 
    let needType = need.size; // The Settings need to be all kinds
    let res = ' ';
    while(r < s.length){
        const c = s[r];
        if(need.has(c)){ // If the desired string is found
            need.set(c,need.get(c) - 1); // If you find it, subtract 1
            if(need.get(c) === 0) needType-- // The type is subtracted by 1
        }
        while(needType === 0) {// If the type number is found completely, do the following
            const newRes = s.substring(l , r+1); // Get the desired string
            if(! res || newRes.length < res.length) res = newResconst c2 = s[l];
            if(need.has(c2)){
                need.set(c2 , need.get(c2) + 1);
                if(need.get(c2) === 1) needType++
            }
            l++
        }
        r++
    }
    return res
};
// Time complexity O(n+m) space complexity O(m)
Copy the code

3. Dictionary summary

  • Like a marriage, a dictionary is a data structure that stores unique values, but it is a data structure that stores unique valuesKey/value pairIn the form of
  • ES6 has a dictionary named Map
  • Dictionary operations: add, delete, change and check key – value pairs

Tree –

1. What is a tree?

  • An abstract model of layered data
  • Common trees in front-end work include: DOM tree, cascading selection, tree control……
  • There are no trees in js, but you can build trees from arrays in Object.

2. What is depth/breadth first traversal?

  • Depth-first traversal: Search as deep a branch of the tree as possible
  • Breadth-first traversal: Visits the node closest to the root node first

Depth-first traversal formula:

  • Accessing the root node
  • Children of root node are traversed depth-first one by one
const tree = {
    val:'a'.children: [{val:'b'.children:[
                {
                    val:'d'.children:[]
                },
                {
                    val:'e'.children:[]}],}, {val:'c'.children:[
                {
                    val:'f'.children:[]
                },
                {
                    val:'g'.children:[]}],}]}const dfs = (root) = > {
    console.log(root.val);
    // root.children.forEach((child) => {dfs(child)})
    root.children.forEach(dfs)
}
dfs(tree) // a b d e c f g
Copy the code

Breadth-first traversal formula:

  • Create a queue and queue the root node
  • Put the head out of the team to visit.
  • Team up the opposing children one by one
  • Repeat steps 2 and 3 until the queue is empty.
const tree = {
    val:'a'.children: [{val:'b'.children:[
                {
                    val:'d'.children:[]
                },
                {
                    val:'e'.children:[]}],}, {val:'c'.children:[
                {
                    val:'f'.children:[]
                },
                {
                    val:'g'.children:[]}],}]}const bfs = (root) = >{
    const q = [root];
    while(q.length > 0) {const n = q.shift()
        console.log(n.val);
        n.children.forEach(child= >{
            q.push(child);
        });
    }
}

bfs(tree); // a b c d e f g
Copy the code

3. What is a binary tree?

  • Each node in the tree can have a maximum of two child nodes.
  • In JS, Object is usually used to simulate binary trees.
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}},}module.exports = bt;
Copy the code

Sequential traversal calculation formula:

  • Accessing the root node
  • Preemptive traversal of the left subtree of the root node
  • Preemptive traversal of the right subtree of the root node

The recursive version:

const bt = require('./bt');

const preorder = (root) = > {
    if(! root)return;
    console.log(root.val);
    preorder(root.left);
    preorder(root.right);
}

preorder(bt); // Root: 1 2 4 5 3 6 7
Copy the code

Non-recursive version:

const preorder = (root) = > {
    if(! root)return;
    const stack = [root]
    while(stack.length){
        const n = stack.pop();
        console.log(n.val);
        if(n.right) stack.push(n.right)
        if(n.left) stack.push(n.left)
    }
}
Copy the code

Middle order traversal calculation formula:

  • For the root nodeOn the leftSubtrees are traversed in order.
  • accessThe rootnode
  • For the root noderightSubtrees are traversed in order.
const bt = require('./bt')
const inorder = (root) = > {
    if(! root)return 
    inorder(root.left)
    console.log(root.val);
    inorder(root.right)
}
inorder(bt) //4 2 5 1 6 3 7 
Copy the code

Non-recursive version:

const inorder = (root) = > {
    if(! root)return 
    const stack = []
    let p = root;
    while(stack.length || p){
        while(p){
            stack.push(p)
            p = p.left;
        }
        const n = stack.pop()
        console.log(n.val); p = n.right; }}Copy the code

After the sequence traversal calculation formula:

  • A post-order traversal of the left subtree of the root node is performed
  • A post-order traversal is performed on the right subtree of the root node
  • Accessing the root node
const bt = require('./bt')

const postorder = (root) = >{
    if(! root)return;
    postorder(root.left)
    postorder(root.right)
    console.log(root.val);
}
postorder(bt); // 4
Copy the code

Non-recursive version:

const postorder = (root) = > {
    // 1. Left and right roots --> root right and left
    if(! root)return;
    const outputStack = [];
    const stack = [root];
    while(stack.length){
        const n = stack.pop()
        outputStack.push(n)
        if(n.left) stack.push(n.left)
        if(n.right) stack.push(n.right)
    }
    while(outputStack.length){
        const n = outputStack.pop()
        console.log(n.val); }}Copy the code

4. The Jungle Book

1. Maximum depth of tree

104. Maximum Depth of binary trees – Force buckle (LeetCode) (leetcode-cn.com)

Ideas:

  • Maximum depth, consider using depth-first traversal
  • In the depth-first traversal process, the hierarchy of each node is recorded and the largest hierarchy can be found

Steps to solve the problem:

  • Create a new variable to record the maximum depth
  • Depth-first traverses the entire tree, recording the hierarchy of each node while constantly refreshing the maximum depth variable
  • The maximum depth variable at the end of the walk
var maxDepth = function(root) {
   let res = 0;
   const dfs = (n,l) = > {
       if(! n)return;
       if(! n.left && ! n.right) res =Math.max(res,l)
       dfs(n.left,l+1)
       dfs(n.right,l+1)
   }
   dfs(root,1)
   return res
};
// Space complexity O(log(n)) at best, O(n) at worst
Copy the code

2. Minimum tree depth

Ideas:

  • Find the minimum depth, consider the breadth first traversal.
  • During breadth-first traversal, the traversal stops when a leaf node is encountered and returns to the node level.

Steps to solve the problem:

  • Breadth-first traverses the entire tree and records the hierarchy of each node.
  • When a leaf node is encountered, return to the node level and stop traversal.
var minDepth = function(root) {
    if(root === null) return 0
   const q = [[root,1]].while(q.length){
       const [n,l] = q.shift();
       if(! n.left && ! n.right)return l;
       if(n.left) q.push([n.left,l+1]);
       if(n.right) q.push([n.right,l+1]); }};// Time O(n), space O(n)
Copy the code

3. Sequence traversal of binary tree

102. Sequential Traversal of binary Trees – LeetCode (leetcode-cn.com)

Ideas:

  • The sequence traversal order is breadth-first traversal.

  • However, the hierarchy of the current node needs to be recorded during traversal so that it can be added to different arrays.

Steps to solve the problem:

  • Breadth-first traversal of a binary tree
  • As you traverse, you record the hierarchy of each node and add it to a different array.
 var levelOrder = function(root) {
    if(! root)return [];
    const q = [root]
    const res = []
    while(q.length){
        let len = q.length;
        res.push([]);
        while(len--){ // Ensure at the same level
            const n = q.shift()
            res[res.length -1].push(n.val);
            if(n.left) q.push(n.left)
            if(n.right) q.push(n.right)
        }
    }
    return res
};
Copy the code

4. Middle order traversal of binary tree

94. Middle Order Traversal of binary Trees – LeetCode (leetcode-cn.com)

 / / iteration
 var inorderTraversal = function(root) {
    const res = []
    const stack = []
    let p = root;
    while(stack.length || p){
        while(p){
            stack.push(p)
            p = p.left
        }
        const n = stack.pop()
        res.push(n.val)
        p = n.right
    }
    return res;
};
/ / the recursive version
var inorderTraversal = function(root) {
    const res = []
    const rec = (n) = >{
        if(! n)return;
        rec(n.left)
        res.push(n.val)
        rec(n.right);
    };
    rec(root)
    return res
};
Copy the code

5. Sum of paths

112. Sum of paths – LeetCode (leetcode-cn.com)

Ideas:

  • During depth-first traversal, the sum of node values of the current path is recorded.
  • At the leaf node, determine whether the node value of the current path is equal to the target value.

Steps to solve the problem:

  • Depth first traverses the binary tree. At the leaf node, judge whether the sum of the node values of the current path is equal to the target value. If yes, return true

  • If there is no match, false is returned

var hasPathSum = function(root, targetSum) {
    if(! root)return false;
    let res = false
    const dfs = (n,s) = >{
        if(! n.left && ! n.right && s=== targetSum) res =true
        if(n.left) dfs(n.left,s+n.left.val)
        if(n.right) dfs(n.right,s+n.right.val)
    }
    dfs(root,root.val)
    return res
};
// The time complexity is O(n) and the space complexity is O(n) because of recursion
Copy the code

6. Traverse all the values of the JSON node

const json = {
    a: {b: {c:1}},
    d: [1.2]}const dfs = (n,path) = >{
    console.log(n,path);
    Object.keys(n).forEach(k= >{
        dfs(n[k],path.concat(k));
    })
}
dfs(json,[]) 
Copy the code

Output:

{ a: { b: { c: 1}},d: [ 1.2]} {[]b: { c: 1}} ['a' ]
{ c: 1 } [ 'a'.'b' ]
1 [ 'a'.'b'.'c' ]
[ 1.2 ] [ 'd' ]
1 [ 'd'.'0' ]
2 [ 'd'.'1' ]
Copy the code

5. Front end and tree: Render tree components of Antd

Js part of the React + ANTD component tree

const {Tree} = antd;

const {TreeNode} = Tree;

const json = [
    {
        title:'一'.key:'1'.children: [{title:'三' , key:'3'.children] : []}}, {title:'二'.key:'2'.children: [{title:'four'.key:'4'.children: []}}]]class Demo extends React.Component {
    dfs = (n) = >{
        return (
            <TreeNode title={n.title} key={n.key}>
                {n.children.map(this.dfs)}
            </TreeNode>)}render(){
        return(
            <Tree>
                {json.map(this.dfs)}
            </Tree>
        )
    }
}

ReactDOM.render(<Demo />,mountNode)
Copy the code

6. Chapter summary

  • Tree is an abstract model of hierarchical data, which is widely used in the front end
  • Common tree operations: depth/breadth first traversal, middle first and order first traversal……

– figure

1. What is the picture

  • Figure isThe network structureAbstract model, is a set of abstract modelsedgeOf the connectionnode
  • A graph can represent any binary relationship: a road, a flight…..
  • Js has no diagrams, but you can build diagrams with Object and Array
  • Graph representation: adjacency matrix, adjacency list, incidence matrix…..

Adjacency matrix:

Adjacency list:

  • Graph common operations: depth first traversal, breadth first traversal

2. Depth-first and breadth-first traversal of the graph

What is depth/breadth first traversal?

  • Depth-first traversal: Search the deepest possible branch of the graph
  • Breadth-first traversal: Visits the node closest to the root node first

/ / to describe figure
const graph = {
    0: [1.2].1: [2].2: [0.3].3: [3]}module.exports = graph
Copy the code

Depth-first traversal formula

  • Access the root node.
  • For the root nodeAdjacent nodes that have not been visitedDepth-first traversal is carried out one by one.

Depth-first code:

const graph = require('./graph')
const visted = new Set(a);const dfs = (n) = >{
    console.log(n);
    visted.add(n);
    graph[n].forEach(c= > {
        if(! visted.has(c)){ dfs(c) } }); } dfs(2)
Copy the code

Breadth-first iteration formula:

  • Create a queue and queue the root node
  • Take the team head and visit.
  • Head of the teamAdjacent nodes that have not been visitedThe team
  • Repeat steps 2 and 3 until the queue is empty
const graph = require('./graph')

const visited = new Set()
visited.add(2);
const q = [2];
while(q.length){
    const n = q.shift();
    console.log(n);
    graph[n].forEach(c= > {
        if(! visited.has(c)){ q.push(c) visited.add(c) } }); }Copy the code

3. The actual picture

1. Significant digits

65. Significant Numbers – LeetCode (leetcode-cn.com)

Ideas:

Steps to solve the problem:

  • Build a graph that represents the state
  • Iterate through the string and follow the graph, returning false if there is no way to go to a node
  • At the end of the walk, return true if 3/5/6 is reached, false otherwise.
var isNumber = function(s) {
    const graph = {
        0: {'blank':0.'sign':1.'. ':2.'digit':6},
        1: {'digit':6.'. ':2},
        2: {'digit':3},
        3: {'digit':3.'e':4},
        4: {'digit':5.'sign':7},
        5: {'digit':5},
        6: {'digit':6.'. ':3.'e':4},
        7: {'digit':5}};let state = 0;
    for(c of s.trim()){
        if(c >= '0' && c <= '9'){
            c = 'digit';
        } else if(c === ' '){
            c = 'blank';
        } else if(c ==='+' || c ===The '-'){
            c ='sign';
        } else if(c === 'E'){
            c = 'e'
        }
        state = graph[state][c];
        if(state === undefined) return false
    }
    
    if(state === 3 || state === 5 || state === 6) {return true
    }
    return false
};
// Time complexity O(n) space complexity O(1)
Copy the code

2. Pacific Atlantic running water

417. Pacific Atlantic Current Problems – LeetCode (leetcode-cn.com)

Ideas:

  • Think of a matrix as a graph.
  • If you traverse the map upstream from the coastline, wherever you go, you’ll flow to some Pacific coordinate

Steps to solve the problem:

  • Create two new matrices to record the coordinates of energy flow to the two oceans
  • From the shoreline, multiple tubes are lined up while depth traverses the map, filling the above matrix in the process.
  • Walk through the two matrices and find the flow to the two oceanic coordinates
var pacificAtlantic = function(heights) {
    if(! heights||! heights[0]) return []
    const m = heights.length
    const n = heights[0].length
    const flow1 = Array.from({length:m},() = > new Array(n).fill(false))
    const flow2 = Array.from({length:m},() = > new Array(n).fill(false))

    const dfs = (r,c,flow) = >{
        flow[r][c] = true;
        [[r-1,c],[r+1,c],[r,c-1],[r,c+1]].forEach(([nr,nc]) = >{
            if(
                // Make sure it's in the matrix
                nr >= 0 && nr < m &&
                nc >= 0 && nc < n &&
                // Prevent dead loops! flow[nr][nc] &&// Be sure to swim against the current
                heights[nr][nc] >= heights[r][c]
             ){
                 dfs(nr,nc,flow)
             }
        })
    };
    // Up the river along the shoreline
    for(let r = 0; r<m; r++){ dfs(r,0,flow1)
        dfs(r,n-1,flow2)
    }

    for(let c = 0; c<n; c++){ dfs(0,c,flow1)
        dfs(m-1,c,flow2)
    }
    // Collect the coordinates that can flow to both oceans
    const res = []
    for(let r = 0; r<m; r++){for(let c = 0; c<n; c++){if(flow1[r][c]&&flow2[r][c]){
                res.push([r,c])
            }
        }
    }
    return res
};
Copy the code

Figure 3. Cloning

133. Clone – LeetCode (leetcode-cn.com)

Ideas:

  • Copying all Nodes
  • Copy all the edges

Answer:

  • Depth or breadth first traverses all nodes
  • Copy all the nodes and store them
  • Connect the copied nodes according to the method of the original picture

Depth-first traversal of the graph:

var cloneGraph = function (node){
    if(! node)return;
    const visited  = new Map(a)const dfs = (n) = >{
        const nCopy = new Node(n.val)
        visited.set(n,nCopy);
        (n.neighbors || []).forEach(ne= >{
            if(! visited.has(ne)){ dfs(ne) } nCopy.neighbors.push(visited.get(ne)) }) }; dfs(node);return visited.get(node)
}
// Time complexity O(n) space complexity O(n)
Copy the code

Breadth-first traversal of the graph:

var cloneGraph = function (node){
    if(! node)return;
    const visited  = new Map()
    visited.set(node,new Node(node.val))
    const q = [node];
    while(q.length){
        const n = q.shift()
        n.neighbors.forEach(ne= >{
            if(! visited.has(ne)){ q.push(ne) visited.set(ne,new Node(ne.val))
            }
            visited.get(n).neighbors.push(visited.get(ne))
        })
    }
    return visited.get(node)
}
Copy the code

4. Summary of the graph

  • Figure isThe network structureAbstract model, is a set of abstract modelsedgeConnected node
  • Graphs can represent any binary relationship, such as roads, flights….. .
  • Js has no diagrams, but you can build diagrams with Object and Array.
  • Graph representation: adjacency matrix, adjacency list……
  • Common operations for graphs: depth-first/breadth-first traversal

Heap –

1. What is a heap?

  • The pile is a special oneComplete binary tree.
  • All nodes are greater than or equal to (maximum heap) or less than or equal to (minimum heap) its children.
  • Js arrays are commonly used to represent the heap

  • The position of the left child node is 2 index + 1.

  • The position of the child node on the right is 2 index + 2.

  • Parent node position (index-1)/2

  • The heap can find the maximum and minimum values efficiently and quickly, time complexity: O(1)

  • Find the KTH largest (small) element.

2. Minimal heap class

  • In a class, declare an array to hold elements.
  • Main methods: insert, delete heap top, get heap top, get heap size.

Insert –

  • Insert the value at the bottom of the heap, at the end of the array.
  • Then move up: swap the value with its parent until the parent is less than or equal to the inserted value.
  • The heap of size K inserts elements in time O(logk)

– Delete the heap top

  • Replace the top of the heap with an element at the end of the array (removing the top directly breaks the heap structure)
  • Then move down: the new heap top swaps its children until the children are greater than or equal to the new heap top.
  • The time complexity for removing the top of a heap of size K is O(logk).

– Gets the top and size of the heap

  • Get the top of the heap: Returns the head of the array.
  • Get the heap size: Returns the length of the array
class MinHeap {
    constructor(){
        this.heap = []
    }
    swap(i1,i2){ // Switch operations
        const temp = this.heap[i1]
        this.heap[i1] = this.heap[i2]
        this.heap[i2] = temp
    }
    getPartIndex(i){ // Get the parent node operation
        return Math.floor((i - 1) / 2) 
        // return (i - 1) >> 1;
    }
    getLeftIndex(i){
        return i * 2 + 1;
    }
    getRightIndex(i){
        return i * 2 + 2;
    }
    shiftUp(index){ // Upshift algorithm
        if(index == 0) { return; }
        const parentIndex = this.getPartIndex(index) // Get the subscript of the child node
        if(this.heap[parentIndex] > this.heap[index]){ // If the parent node is larger than the child node
            this.swap(parentIndex, index)
        }
    }
    shiftDown(index){ // Down algorithm
        const leftIndex = this.getLeftIndex(index);
        const RightIndex = this.getRightIndex(index);
        if(this.heap[leftIndex] < this.heap[index]){
            this.swap(leftIndex,index)
            this.shiftDown(leftIndex)
        }
        if(this.heap[RightIndex] < this.heap[index]){
            this.swap(RightIndex,index)
            this.shiftDown(RightIndex)
        }
    }
    insert(value){ // Insert operations
        this.heap.push(value); 
        this.shiftUp(this.heap.length -1); / / move upwards
        this.shiftUp(parentIndex);
    }
    pop(){ // Delete operation
        this.heap[0] = this.heap.pop();
        this.shiftDown(0)}peek() { // Get the header operation
        return this.heap[0];
    }
    size() { // Get the size operation
        return this.heap.length; }}Copy the code

3. The KTH maximum element problem

  • Build a minimal heap and insert the elements in sequence into the heap.
  • When the heap capacity exceeds K, the opposite top is removed.
  • After insertion, the top of the heap is the KTH largest element.

215. The KTH largest element in an array – LeetCode (leetcode-cn.com)

Ideas:

  • See “KTH largest element”
  • Consider choosing the minimum heap

Steps to solve the problem:

  • Build the minimum heap and insert the values of the array in turn into the heap
  • When the size of the heap exceeds K, the heap top is removed.
  • After insertion, the top of the heap is the KTH largest element
var findKthLargest = function(nums, k) {
    const h = new MinHeap();
    nums.forEach(n= > {
        h.insert(n)
        if(h.size() > k) h.pop();
    })
    return h.peek();
};
// Time O(nlogk) space O(k)
Copy the code

4. The first K high-frequency elements

347. The first K High frequency Elements – Force buckle (LeetCode) (leetcode-cn.com)

Brute force cracking:

var topKFrequent = function(nums, k) {
    const map = new Map()
    nums.forEach(n= > {
        map.set(n,map.has(n) ? map.get(n) + 1 : 1)})const list = Array.from(map).sort((a,b) = > b[1]- a[1])
    return list.slice(0,k).map(n= > n[0])};Copy the code

Stack solution:

class MinHeap {
    constructor(){
        this.heap = []
    }
    swap(i1,i2){ // Switch operations
        const temp = this.heap[i1]
        this.heap[i1] = this.heap[i2]
        this.heap[i2] = temp
    }
    getPartIndex(i){ // Get the parent node operation
        return Math.floor((i - 1) / 2) 
        // return (i - 1) >> 1;
    }
    getLeftIndex(i){
        return i * 2 + 1;
    }
    getRightIndex(i){
        return i * 2 + 2;
    }
    shiftUp(index){ // Upshift algorithm
        if(index == 0) { return; }
        const parentIndex = this.getPartIndex(index) // Get the subscript of the child node
        if(this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value){ // If the parent node is larger than the child node
            this.swap(parentIndex, index)
            this.shiftUp(parentIndex); }}shiftDown(index){ // Down algorithm
        const leftIndex = this.getLeftIndex(index);
        const RightIndex = this.getRightIndex(index);
        if(this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value){
            this.swap(leftIndex,index)
            this.shiftDown(leftIndex)
        }
        if(this.heap[RightIndex] && this.heap[RightIndex].value < this.heap[index].value){
            this.swap(RightIndex,index)
            this.shiftDown(RightIndex)
        }
    }
    insert(value){ // Insert operations
        this.heap.push(value); 
        this.shiftUp(this.heap.length -1); / / move upwards
    }
    pop(){ // Delete operation
        this.heap[0] = this.heap.pop();
        this.shiftDown(0)}peek() { // Get the header operation
        return this.heap[0];
    }
    size() { // Get the size operation
        return this.heap.length; }}var topKFrequent = function(nums, k) {
    const map = new Map()
    nums.forEach(n= > {
        map.set(n,map.has(n) ? map.get(n) + 1 : 1)})const h = new MinHeap();
   map.forEach((value,key) = > {
       h.insert({value,key});
       if(h.size() > k){
           h.pop()
       }
   })
   return h.heap.map(a= > a.key)
};
// Time O(n*logK) space O(n)
Copy the code

Sort –

1. What are sort and search?

  • Sort: Turn an out-of-order array into an ascending or descending array.
  • Search: Finds the index of an element in an array.
  • Sort in js: the sort method of arrays.
  • Js search: array indexOf method.

2. The main sorting and search algorithms in the front end

– Sorting algorithm

  • Bubble sort O(n^2)

  • Merge sort O of n^2

  • Selection sort O(n^2)

  • Quick sort order n logN

  • Insert sort order n logN

    .

– Search algorithm

  • Sequential search

  • Binary search

    .

3. Bubble sort

  • Compare all adjacent elements and swap them if the first is larger than the second.
  • After one round, I guarantee that the last number is the largest.
  • performn - 1Round, you can complete the sort.
Array.prototype.bubbleSort = function () {
    for (let i = 0; i < this.length - 1; i++) {
        for (let j = 0; j < this.length - 1 - i; j++) {
            if(this[j]>this[j+1]) {const temp = this[j];
                this[j] = this[j+1]
                this[j+1] = temp
            }
        } 
    }
};

const arr = [5.4.3.2.1];
arr.bubbleSort();

Copy the code

Time complexity of bubble sort:

  • Two nested loops
  • Time complexity O(n^2)

4. Select sort

  • Find the minimum value in the number and select it to place it in the second place.
  • Then find the second-smallest value, select it and place it in the second place.
  • And so on n minus 1 rounds.
Array.prototype.selectionSort = function () {
    for (let i = 0; i < this.length; i++) {
        let indexMin = i;
        for (let j = 0; j < this.length; j++) {
            if (this[j] < this[indexMin]) {
                indexMin = j
            }
        }
        if(indexMin ! == i) {const temp = this[0];
            this[0] = this[indexMin];
            this[indexMin] = temp; }}}// Select sort time complexity O(n^2)
const arr = [5.4.3.2.1]
arr.selectionSort();
Copy the code

5. Insert sort

  • Let’s start with the second term and go ahead
  • Anything bigger than that goes to the back
  • And so on down to the last number
Array.prototype.insertionSort = function () {
    for (let i = 1; i < this.length; i++) {
        const temp = this[i]
        let j = i;
        while (j > 0) {
            if (this[j - 1] > temp) {
                this[j] = this[j - 1];
            } else {
                break;
            }
            j--
        }
        this[j] = temp
    }
};

const arr = [5.4.3.2.1]
arr.insertionSort();
// Time complexity O(n^2)
Copy the code

6. Merge sort

  • Divide: Divide an array in half and recursively divide subarrays until they are separated into individual numbers.
  • Combine: Combine two numbers into an ordered array, and then combine ordered arrays until all subarrays are combined into a complete array
  • Create an empty res array to hold the sorted array.
  • Compares the heads of two ordered arrays, with the smaller one pushed out into the RES.
  • If both arrays still have values, repeat step 2.
Array.prototype.megeSort = function () {
    const rec = (arr) = > {
        if (arr.length === 1) return;
        const mid = Math.floor(arr.length / 2);
        const left = arr.slice(0, mid);
        const right = arr.slice(mid, arr.length);
        const orderLeft = rec(left);
        const orderRight = rec(right);
        const res = []
        while (orderLeft.length || orderRight.length) {
            if (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;
    }
    const res = rec(this)
    / / copy
    res.forEach((n, i) = > {
        this[i] = n; })}// Time complexity O(logN)
// Time complexity O(n)
// Time complexity: O(n*logN)
Copy the code

7. Quicksort

  • Partition: From any “base” of the array, so the elements smaller than the base are in front of the base, and the elements larger than the base are placed after the base.
  • Recursively: Partition the subarray before and after the base recursively.
Array.prototype.quickSort = function () {
    const rec = (arr) = > {
        if (arr.length === 1) return arr;
        const left = []
        const right = [];
        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]); }}return [...res(left), mid, ...rec(right)]
    }
    const res = rec(this)
    res.forEach((n, i) = > {
        this[i] = n
    })
}
// Time complexity
// Recursive time complexity O(logN)
// Partition O(n)
// Total time complexity O(nlogN)
Copy the code

8. Sequential search

  • Through the array
  • Find the element that corresponds to the target and return its subscript
  • Returns -1 if not found
Array.prototype.sequentialSearch = function (item) {
    for (let i = 0; i < this.length; i++) {
        if (this[i] === item) {
            returni; }}return -1
}
// Iterating through the array is a loop operation
// Time complexity: O(n)
Copy the code

Binary search

  • Start at the middle element of the array, and if the middle element happens to be the target value, the search ends.
  • If the target value is greater or less than the middle element, the search is performed on the half of the array that is greater or less than the middle element.
Array.prototype.binarySearch = function (item) {
    let low = 0;
    let high = this.length - 1;
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const element = this[mid];
        if (element < item) {
            low = mid + 1;
        } else if (element > item) {
            high = mid - 1;
        } else {
            returnmid; }}return -1;
}

// The range is halved each time
// Time complexity: O(logN).
Copy the code

10. Strength buckle actual combat

1. Merge two linked lists

21. Merge two ordered lists – LeetCode (leetcode-cn.com)

Ideas:

  • Similar to merging two ordered arrays in merge sort.
  • Substituting an array for a linked list solves this problem.

Steps to solve the problem:

  • Create a new linked list as the result.
  • Use a pointer to traverse two ordered lists, and compare the current nodes of the two lists. The smaller one is connected to the new list, and move the pointer one step back.
  • List traversal ends, returns a new list.
var mergeTwoLists = function(l1, l2) {
   const res = new ListNode(0);
   let p = res;
   let p1 = l1;
   let p2 = l2;
   while(p1 && p2){
       if(p1.val < p2.val){
           p.next = p1
           p1 = p1.next
       } else{
           p.next = p2;
           p2 = p2.next;
       }
       p = p.next;
   }
   if(p1){
       p.next = p1
   }
   if(p2){
       p.next = p2
   }
   return res.next
};
// Time complexity O(m + n) space complexity O(1)
Copy the code

2. Guess the number size

Ideas:

  • Binary search
  • Call the GUESS function to determine if the intermediate element is the target value.

Steps to solve the problem:

  • Start at the middle element of the array, and if the middle element happens to be the target value, the search process ends.
  • If the target value is greater than or less than the middle element, it looks in the half of the array that is greater than or less than the middle element.
 var guessNumber = function(n) {
   let low = 1;
   let high = n;
   while(low<=high){
       const mid = Math.floor((low + high) / 2);
       const res = guess(mid);
       if(res === 0) {return mid;
       } else if(res === 1){
           low = mid + 1;
       } else {
           high = mid - 1; }}};Copy the code

– Divide and rule

1. What is divide and rule?

  • Divide and conquer isAlgorithm designIs a way of.
  • It will be a problempointsInto multiple small questions similar to the original question,Recursive solutionSmall problem, then will resultusAnd solve the original problem.

Scenario 1: Merge sort

  • Split: Splits an array down the middle.
  • Solution: Merge sort of two subarrays recursively.
  • Merge: Merges ordered subarrays.

Scenario 2: Quicksort

  • Divide: Select base to divide an array into two subarrays.
  • Solution: Recursively quicksort two subarrays.
  • Merge: Merges two subarrays.

2. Guess the number size (binary search)

374. Guess the size of the number – LeetCode (leetcode-cn.com)

Ideas:

  • Binary search also has the characteristics of “division, solution and combination”.
  • Consider the option of divide and conquer.

Steps to solve the problem:

  • Divide: calculates the intermediate elements and splits the array.
  • Solution: Recursively performs binary search on larger or smaller arrays.
  • Concatenate: This step is not required because it is returned when found in the subarray.
var guessNumber = function(n) {
    const rec = (low,high) = >{
        if(low>high) return;
        const mid = Math.floor((low + high) / 2)
        const res = guess(mid);
        if(res === 0) {return mid
        } else if(res === 1) {return rec(mid + 1, high);
        }else{
            return rec(1,mid-1); }};return rec(1,n);
};
// Event complexity O(logn) Space complexity O(logn)
Copy the code

3. Flipping binary trees (HomeBrew guy flipped his car that year)

  • First flip the left and right subtrees, and then switch the subtrees.

  • It conforms to the characteristics of “divide, solve and combine”.

  • Consider divide and conquer

Steps to solve the problem:

  • Points: Get the left and right subtrees.
  • Solution: Recursively flip the left and right subtrees.
  • Combine: switch the flipped left and right subtrees to the root node.
var invertTree = function(root) {
    if(! root)return null;
    return {
        val:root.val,
        left:invertTree(root.right),
        right:invertTree(root.left)
    }
};
// Event complexity (number of accesses)O(n), space complexity O(h),h is the height of the tree
Copy the code

4. Same tree

100. Same Tree – LeetCode (leetcode-cn.com)

Ideas:

  • Two trees: the root node has the same value, the left subtree has the same value, and the right subtree has the same value.
  • It conforms to the characteristics of “divide, solve and combine”.
  • Consider the option of divide and conquer.

Steps to solve the problem:

  • Points: Gets the left and right subtrees of two trees.
  • Solution: Recursively determine whether the left and right subtrees of two trees are the same.
  • Combine: Combine the above results, and if the root values are the same, the tree is the same.
var isSameTree = function(p, q) {
    if(! p && ! q)return true;
    if(p && q && p.val === q.val && isSameTree(p.left,q.left)
    && isSameTree(p.right,q.right)) {
        return true;
    }
    return false
}
// Time complexity O(n) space complexity O(n)
Copy the code

5. Symmetric binary trees

101. Symmetric Binary Trees – Force Buckle (LeetCode) (leetcode-cn.com)

Ideas:

  • To whether the left and right subtrees are mirrors.
  • The decomposition is as follows: Whether the left subtree of tree 1 and the right subtree of tree 2 are mirrored, and whether the right subtree of tree 1 and the left subtree of tree 2 are mirrored.
  • In line with the characteristics of “divide, solve and combine”, the choice of divide and conquer is considered.

Steps to solve the problem:

  • Points: Gets the left and right subtrees of two trees.

  • Solution: Recursively determine whether the left subtree of tree 1 and the right subtree of tree 2 are mirror images, and whether the right subtree of tree 1 and the left subtree of tree 2 are mirror images.

  • Combined: If all the above are true and the root values are the same, the two trees are mirrored.

var isSymmetric = function(root) {
    if(! root)return true;
    const isMirror = (l,r) = > {
        if(! l && ! r)return true;
        if(l && r && l.val === r.val &&
        isMirror(l.left,r.right) &&
        isMirror(l.right,r.left) 
        ){
            return true;
        }
        return false;
    };
    return isMirror(root.left,root.right);
};
// Time complexity O(n) Space complexity O(n) height of the tree
Copy the code

– Dynamic programming

1. What is dynamic programming?

  • Dynamic programming isAlgorithm designIs a way of
  • It breaks down a problem intooverlappingTo solve the original problem by repeatedly solving the subproblem

  • Define subproblem: F(n) = F(n-1) + F(n-2)
  • Repeat: loop from 2 to n to execute the above formula.

2. Stair climbing problems

70. Climbing stairs – LeetCode (leetcode-cn.com)

Ideas:

  • Climbing to the NTH step can be done by climbing 1 step on the n-1 step, or 2 steps on the n-2 step.
  • F(n) = F(n-1) + F(n-2)
  • Use dynamic programming.

70. Climb stairs – LeetCode (leetcode-cn.com)

  • Define subproblem: F(n) = F(n-1) + F(n-2)
  • Repeat: loop from 2 to n to execute the above formula.
var climbStairs = function(n) {
   if(n < 2) return 1;
   const dp = [1.1];
   for(let i = 2; i <= n; i++){ dp[i] = dp[i -1] + dp[i - 2]}return dp[n]
};
// Time complexity O(n) temporary variable array space complexity O(n)

// Change the empty array to two variables to reduce space complexity to O(1)
var climbStairs = function(n) {
   if(n < 2) return 1;
   let dp0 = 1;
   let dp1 = 1;
   for(let i = 2; i <= n; i++){const  temp = dp0;
      dp0 = dp1;
      dp1 = dp0 + temp;
   }
   return dp1
};
Copy the code

3. Robbery

198. Robbery – LeetCode (leetcode-cn.com)

Ideas:

  • F (k) = the maximum amount that can be stolen from the previous K houses.

  • Ak is the amount of money for the KTH house.

  • F (k) = Max (f (k – 2) + Ak, f (k – 1)).

  • Consider dynamic programming

Steps to solve the problem:

  • Define the subproblem: f(k) = Max (f(k-2)+Ak,f(k-1)).
  • Repeat: loop from 2 to n to execute the above formula.
var rob = function(nums) {
    if(nums.length === 0) return 0
    const dp = [0,nums[0]].for(let i =2; i<=nums.length; i++){ dp[i] =Math.max(dp[i-2] + nums[i - 1],dp[i - 1])}return dp[dp.length - 1]};Copy the code

– Greedy algorithms

1. What is a greedy algorithm?

  • The greedy algorithm isAlgorithm designOne of the methods in.
  • Looking forward to going through each stageLocal optimumSelection, so as to achieve global optimization.
  • The results andIt's not necessarily optimal.

2. Change

455. Distribution of Cookies – LeetCode (leetcode-cn.com)

Ideas:

  • Local optimal: not only can satisfy the children, but also the smallest consumption.
  • The “smaller cookie” was first distributed to the child with the “least appetite.”

Steps to solve the problem:

  • Sort the biscuit array and appetite array in ascending order.
  • Walk through the array of cookies to find the one that fits the first child
  • Then continue to traverse the cookies to find satisfying second, third and….. Cookies for n children.
var findContentChildren = function(g, s) {
    const sortFunc = function(a,b) {
        return a -b
    }
    g.sort(sortFunc);
    s.sort(sortFunc);
    let i = 0;
    s.forEach(n= > {
        if(n >= g[i]){
            i++
        }
    })
    return i;
};
Copy the code

3. Stock buying problems

122. The Best Time to Buy and Sell Stocks II – LeetCode (leetcode-cn.com)

Ideas:

  • Premise: God knows the future price.
  • Local optimal: close on the good, see the bad do not move, do not make any long-term plan

Steps to solve the problem:

  • Create a new variable to count total profits.
  • Iterate over the price array, if the current price
var maxProfit = function(prices) {
    let profit = 0;
    for(let i =1; i < prices.length; i++){if(prices[i] > prices[i - 1]){
            profit += prices[i] - prices[i - 1]; }}return profit
};
Copy the code

– Backtracking algorithm

1. What is the backtracking algorithm

  • The backtracking algorithm isAlgorithm designIs a way of.
  • The backtracking algorithm is oneprogressiveLook for strategies for building problem solving.
  • The backtracking algorithm starts with a possible action, and if it doesn’t work, it backtracks and selects another action until the problem is solved.

2. What problems are suitable for backtracking algorithm?

  • There are many roads.
  • On these roads, there areEnds,, there areA way out.
  • It is often necessary to recursively simulate all paths.

3. The whole arrangement

  • Recursively simulate all the situations.
  • Backtrack when you encounter situations that contain repeating elements
  • Collect all the cases that reached the recursive end point and return

46. Full Permutation – LeetCode (leetcode-cn.com)

Ideas:

  • Requirements: 1, all permutations 2, no repeated elements
  • There is a way out, there is a dead end
  • Consider backtracking algorithm

Steps to solve the problem:

  • There’s a recursion that simulates everything.
  • Backtrack when you encounter situations that contain repeating elements.
  • Collect all cases that arrive recursively and return
var permute = function(nums) {
    const res = [];
    const backtrack = (path) = >{ // return the function
        if(path.length === nums.length){ // Return the same length
            res.push(path);
            return;
        }
        nums.forEach(n= > {
            if(path.includes(n)){ // Cannot contain exactly the same number
                return;
            }
            backtrack(path.concat(n));
        })
    }
    backtrack([])
    return res;
};
// Time complexity O(n!) Space complexity O(n)
Copy the code

4. Subset problem

78. Subset – LeetCode (leetcode-cn.com)

Ideas:

  • Requirements: 1. All subsets; 2. No repeating elements
  • There is a way out, there is a dead end.
  • Consider using backtracking algorithms.

Steps to solve the problem:

  • Recursively simulate everything
  • Make sure the numbers are the ones that follow.
  • Collect all cases that reach the recursive end point and return.
var subsets = function(nums) {
    const res =[]
    const backtrack = (path,l,start) = >{
        if(path.length === l){
            res.push(path)
            return;
        } 
        for(leti = start; i<nums.length; i++){ backtrack(path.concat(nums[i]),l,i+1)}};for(let i =0; i<=nums.length; i++){ backtrack([],i,0)}return res
};
Copy the code

End –

– Knowledge architecture

  • Data structures: stack, queue, linked list, set, dictionary, tree, graph, heap.
  • Algorithm: linked list/tree/graph traversal, array sorting and search
  • Algorithm design ideas: divide and conquer, dynamic programming, greed, backtracking.

– Key points and Difficulties

  • Data structures: All data structures are important, but the most relevant front-end ones are linked lists and trees.
  • Algorithm: linked list/tree/graph traversal, array sorting and search…..
  • Design idea: divide and rule, dynamic planning, greed, backtracking.

– Experience

  • To understand data structures and algorithmsThe characteristics ofandApplication scenarios.
  • Implement it once in JS, preferably in a second or third language.
  • Learn to analyzeTime/space complexity.
  • Extract the front end and algorithm junction points forWork of actual combat.

– Development Suggestions

  • moreBrush the topic, you’d better guarantee more than 300 lines.
  • Summarize a variety ofroutine,The template.
  • More than meetThe source codeReact, Lodash, V8……
  • moreIn actual combatData structures and algorithms are used to work.