The introduction

This material is from the bottle Gentleman advanced algorithm training camp, one algorithm question or article every day, has been updated for half a month:

  • Front-end advanced algorithm 1: How to analyze and count the efficiency and resource consumption of the algorithm?
  • Front-end advanced algorithm 2: From Chrome V8 source code to see JavaScript array
  • Front-end advanced algorithm 3: learning LRU algorithm from browser cache elimination strategy and Vue keep-Alive
  • Front-end advanced algorithm 4: the list is so simple (+ Leetcode brush problem)

And the title:

  • Leetcode88: merge two ordered arrays
  • Byte & Leetcode1: Sum of two numbers
  • Tencent: Array flatten, deduplicate, sort
  • Leetcode349: Given two arrays, write a function to calculate their intersection
  • Leetcode146: Design and implement an LRU (least recently used) caching mechanism
  • Ali algorithm problem: write a function to calculate the intersection of multiple arrays
  • Leetcode21: Merges two ordered lists
  • Leetcode141: Determine if a singly linked list has a loop
  • Diagram LeetCode206: Reverse linked list
  • Leetcode876: Find the middle node of the linked list

This section is a summary and review of the advanced algorithm training camp for half a month 👇

1. Front-end advanced algorithm 1: How to analyze and statistic the execution efficiency and resource consumption of the algorithm?

Good data structures and algorithms can greatly reduce code execution time and storage space, so how do we measure it? This section mainly introduces the algorithm performance measurement index – complexity analysis.

Complexity can be divided into:

  • Time complexity
  • Spatial complexity

1. How to express the algorithm complexity?

Complexity is usually expressed in large O notation. It does not represent the actual execution time or storage space consumption, but the trend of code execution time as data size increases (time complexity) or the trend of storage space as data size increases (space complexity), so, It is also called the asymptotic time complexity, or the time (or space) complexity for short.

Common complexity

Polynomial magnitude:

  • Constant order: O(1) : When no cyclic or recursive statements exist in the algorithm, the time complexity of any O(1) is maintained, even if thousands of lines of code exist.
  • Logarithmic order: O(logn): A brief introduction
let i=1;
while (i <= n)  {
  i = i * 2;
}
Copy the code
  • Each loopiAll times2Until thei > n, that is, the execution process is: 20, 2,1, 2,2And… , 2,kAnd… , 2,xN so the total number of executions x can be written as 2x = n, and the time complexity is order log2N). Here is the2, or any other constantk, the time complexity is also: O(log~3~n) = O(log32 * log2n) = O(log2n)
  • Linear order: O(n)
  • Linear logarithmic order: O(nlogn)
  • Square order, cubic order,… , k power order: O(n2), O(n3)… , O (nk)

Non-polynomial order:

  • Exponential order: O(2n)
  • Factorial order: O(n!)

3. Complexity division

Taking time complexity as an example, time complexity is affected by data itself and can be divided into:

  • Best time complexity: In the best case, the time complexity of executing this code
  • Worst time complexity: In the worst case, the time complexity of executing this code
  • Average time complexity: in all cases, take an average, and omit coefficients, low orders, and constants

Details: Front-end advanced algorithm 1: How to analyze and statistic the algorithm’s execution efficiency and resource consumption?

2, front-end advanced algorithm 2: from Chrome V8 source code to see JavaScript array

1. Array application in JavaScript

let arr = [1.2.3]
Copy the code

Its specific storage structure determines:

advantages

  • Random access: Data can be randomly accessed at any position in the array by subscript

disadvantages

  • Not very friendly to data deletion and insertion

Search: The time complexity of random access according to the subscript is O(1);

Insert or delete: time complexity is O(n);

Arrays are almost omnipotent in JavaScript. They can be used not only as a normal array, but also as a stack or queue.

Array:

let array = [1.2.3]
Copy the code

The stack:

let stack = [1.2.3]
/ / into the stack
stack.push(4)
/ / out of the stack
stcak.pop()
Copy the code

Queue:

let queue = [1.2.3]
/ / into the team
queue.push(4)
/ / out of the team
queue.shift()
Copy the code

2. What makes arrays unique in JavaScript

We know that in JavaScript, you can store different types of values in an array, and the array can grow dynamically, unlike other languages, like C, where you have to determine the size of the array when you create it, and if it’s full, you have to reallocate memory. Why is this nan?

In JavaScript, JSArray inherits from JSObject, or it’s just a special object that stores data internally in the form of key-value, so arrays in JavaScript can hold different types of values. It has two types of storage, fast array and slow array. When initializing an empty array, use the fast array, and the fast array uses continuous memory space. When the array reaches its maximum size, JSArray dynamically expands to store more elements. When there are too many holes in the array, the array is converted to a slow array, which stores data in the form of key-value hash tables to save memory space.

Specific fast array, dynamic expansion to: front-end advanced algorithm 2: from Chrome V8 source code to see JavaScript array

3. Front-end advanced algorithm 3: learn LRU algorithm from browser cache elimination strategy and Vue keep-Alive

1. Browser cache elimination policy

When we open a web page, https://github.com/sisterAn/JavaScript-Algorithms, for example, it will be in a real network request before query browser cache, look to whether have to request file, if you have, the browser will intercept requests, return to cache files, And end the request directly, no more download to the server. If it doesn’t exist, it goes to the server.

In fact, the browser cache is a local copy of the resource, its size is limited, when we have too many requests, the cache space will be used up, at this point, to continue to make network requests to determine which data in the cache to keep and which data to be removed, this is the browser cache cull strategy. The most common elimination strategies are FIFO (first in, first out), LFU (least used), and LRU (least recently used).

LRU (Least Recently Used) cache weeding strategy, the name means that the data is weeding out according to the historical access records of the data. The core idea is that if the data has been accessed Recently, it has a higher chance of being accessed in the future, and the data that has not been accessed Recently is preferentially weeding out.

Here’s a diagram to help us understand LRU:

2. Vue keep-alive source interpretation

When the keep-alive cache exceeds Max, the LRU algorithm is used to flush out the cache. In the implementation process, the cache object is used to store the cache component instance and the key value, and the keys array is used to store the key of the cache component. When rendering an instance to be cached in keep-Alive:

  • Determine whether the instance has been cached in the cache, cache it directly, and adjustkey 在 keys(removekeys 中 keyAnd in thekeysThe last digit of the array)
  • If there is no cache, the instance is cached, ifkeysThe length of phi is greater thanmax(The cache length exceeds the upper limit), the cache is removedkeys[0]The cache

Main implementation LRU code:

// --------------------------------------------------
// This is the LRU algorithm.
// If it is in the cache, adjust it,
// If there are none, insert (if the length exceeds Max, discard those that have not been accessed recently)
// --------------------------------------------------
// Obtain vNode component instances from the cache if the cache is hit,
// And reorder the keys to the end of the keys array
if (cache[key]) {
  vnode.componentInstance = cache[key].componentInstance;
  // make current key freshest
  remove(keys, key);
  keys.push(key);
}
// If there is no hit, put the vNode into the cache
else {
  cache[key] = vnode;
  keys.push(key);
  // prune oldest entry
  // If Max is configured and the length of the cache exceeds this. Max, delete the first one from the cache
  if (this.max && keys.length > parseInt(this.max)) {
    pruneCacheEntry(cache, keys[0], keys, this._vnode); }}Copy the code

Source code details: front-end advanced algorithm 3: learning LRU algorithm from browser cache elimination strategy and Vue keep-Alive

Four, front-end advanced algorithm 4: the list is so simple (+ Leetcode brush problem)

1. Diagram linked lists

Common linked list types are single linked list, double linked list and circular linked list, where next is the successor pointer, pointing to its successor node, prev is the precursor pointer, pointing to its precursor node.

Singly linked lists

Double linked list

Circular linked list

2. List the complexity of the linked list

Singly linked lists

Operation method Time complexity instructions
append O(n) Appends a node to the end of a linked list
search O(n) Look up any element in a linked list
insert O(n) Inserts a node anywhere in the list
remove O(n) Removes a node at any location in the list
searchNext O(1) Finds the successor node of a node
insertNext O(1) Insert a node after a node (successor node)
removeNext O(1) Delete a node after a node (successor node)

Double linked list

Operation method Time complexity instructions
search O(n) Look up any element in a linked list
insert O(n) Inserts a node anywhere in the list
remove O(n) Removes a node at any location in the list
SearchNext or searchPre O(1) Finds the successor or precursor of a node
InsertNext or insertPre O(1) Insert a successor or precursor node to a node
RemoveNext or removePre O(1) Example Delete the precursor or successor node of a node

Circular linked list

Operation method Time complexity instructions
search O(n) Look up any element in a linked list
insert O(n) Inserts a node anywhere in the list
remove O(n) Removes a node at any location in the list
searchNext O(1) Finds the successor node of a node
insertNext O(1) Insert a node after a node (successor node)
removeNext O(1) Delete a node after a node (successor node)

4: The list is so simple (+ Leetcode)

Leetcode88: merge two ordered arrays

1. The subject

Given two ordered integer arrays nums1 and nums2, please merge nums2 into numS1 to make num1 an ordered array.

Description:

Initialize nums1 and nums2 with the number of elements m and N, respectively. You can assume that NUMS1 has enough space (size greater than or equal to M + n) to hold the elements in NUMs2.

Example:

Input: nums1 = [1.2.3.0.0.0], m = 3
nums2 = [2.5.6],       n = 3Output:1.2.2.3.5.6]
Copy the code

2. Answer

答 案 :

  • nums1 、 nums2Order, if thenums2All merge intonums1, the mergednums1Length ofm+n
  • We can start from the subscriptm+n-1Fill in the position ofnums1And compare thenums1[len1] 与 nums2[len2]The maximum value is writtennums1[len], i.e.,
    • nums1[len1]>=nums2[len2] ，nums1[len--] = nums1[len1--]Here,--Because after the write is successful, the subscript is automatically suggested to continue the comparison
    • Otherwise,nums1[len--] = nums2[len2--]
  • Boundary conditions:
    • iflen1 < 0, i.e.,len2 >= 0At this time,nums1Has been rewritten,nums2We’re not done yet. We just need tonums2The remaining elements (0… Len) writenums2After writing, the merge is complete
    • iflen2 < 0At this time,nums2Have all been merged intonums1, merger completed

The time complexity is O(m+n).

Code implementation:

var merge = function(nums1, m, nums2, n) {
    let len1 = m - 1,
        len2 = n - 1,
        len = m + n - 1
    while(len2 >= 0) {
        if(len1 < 0) {
            nums1[len--] = nums2[len2--]
            continue
        }
        nums1[len--] = nums1[len1] >= nums2[len2] ? nums1[len1--]: nums2[len2--]
    }
};
Copy the code

3. More answers:Leetcode88: merge two ordered arrays

Byte & Leetcode1: sum of two numbers

1. The subject

Given an array of integers nums and a target value, find the two integers in the array whose sum is the target value and return their array indices.

You can assume that there is only one answer for each input. However, you cannot reuse the same elements in the array.

Example:

Given nums = [2.7.11.15], target = 9Because the nums [0] + nums[1] = 2 + 7 = 9So return [0.1]
Copy the code

2. Answer

答 案 :

  • Initialize amap = new Map()
  • Start with the first elementnums
  • Get the target value andnums[i]Of, i.ek = target - nums[i], the judgment difference ismapExists in
    • There is no (map.has(k) 为 false), it will benums[i]To join themap(the key tonums[i]The value foriIs used to check whether a value exists in the map and passgetMethod directly get the subscript)
    • There is (map.has(k)), returning[map.get(k), i], end of solution
  • At the end of the traversal, thennumsIf there are no two numbers in the[]

Time complexity: O(n)

Code implementation:

var twoSum = function(nums, target) {
    let map = new Map(a)for(let i = 0; i< nums.length; i++) {
        let k = target-nums[i]
        if(map.has(k)) {
            return [map.get(k), i]
        }
        map.set(nums[i], i)
    }
    return [];
};
Copy the code

3. More answers:Byte & Leetcode1: Sum of two numbers

Seven, Tencent: array flattening, deduplicate, sort

1. The subject

Known as an array: var arr = [[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10].

Write a program that flattens and divides the duplicate parts of the array, resulting in an ascending and non-duplicate array

2. The answer:

var arr = [ [1.2.2], [3.4.5.5], [6.7.8.9[11.12[12.13[14]]]],10]
/ / flat
let flatArr = arr.flat(4)
/ / to heavy
let disArr = Array.from(new Set(flatArr))
/ / sorting
let result = disArr.sort(function(a, b) {
    return a-b
})
console.log(result)
/ / [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
Copy the code

Thanks for 352800205: the Flat () method requires a node version of at least 12.0

3. More answers:Tencent: Array flatten, deduplicate, sort

Leetcode349: Given two arrays, write a function to calculate their intersection

1. The subject

Given two arrays, write a function to calculate their intersection.

Example 1:

Input: nums1 = [1.2.2.1], nums2 = [2.2] Output: [2]
Copy the code

Example 2:

Input: nums1 = [4.9.5], nums2 = [9.4.9.8.4] Output: [9.4]
Copy the code

Description:

Each element in the output must be unique. We can ignore the order of the output.

2. The answer

答 案 :

  • filterfilter
  • Setduplicate removal

Code implementation:

var intersection = function(nums1, nums2) {
    return [...new Set(nums1.filter((item) = >nums2.includes(item)))]
};
Copy the code

3. More answers:Leetcode349: Given two arrays, write a function to calculate their intersection

Leetcode146: Design and implement an LRU (least recently used) caching mechanism

1. The subject

Using your data structures, design and implement an LRU (least recently used) caching mechanism. It should support the following operations: getting data get and writing data PUT.

Get data get(key) – Gets the value of the key (always positive) if it exists in the cache, otherwise returns -1. Write data Put (key, value) – Writes data if the key does not exist. When the cache reaches its maximum capacity, it should delete the longest unused data before writing new data to make room for new data.

Advanced:

Can you do both in order one time?

Example:

LRUCache cache = new LRUCache( 2 /* Cache capacity */ );

cache.put(1.1);
cache.put(2.2);
cache.get(1);       / / returns 1
cache.put(3.3);    // This will invalidate key 2
cache.get(2);       // Return -1 (not found)
cache.put(4.4);    This operation invalidates key 1
cache.get(1);       // Return -1 (not found)
cache.get(3);       / / return 3
cache.get(4);       / / return 4
Copy the code

2. The answer

Basic solution: array + object implementation

Class vue keep-alive implementation

var LRUCache = function(capacity) {
    this.keys = []
    this.cache = Object.create(null)
    this.capacity = capacity
};

LRUCache.prototype.get = function(key) {
    if(this.cache[key]) {
        // Adjust the position
        remove(this.keys, key)
        this.keys.push(key)
        return this.cache[key]
    }
    return - 1
};

LRUCache.prototype.put = function(key, value) {
    if(this.cache[key]) {
        // Update as it exists
        this.cache[key] = value
        remove(this.keys, key)
        this.keys.push(key)
    } else {
        // If not, join
        this.keys.push(key)
        this.cache[key] = value
        // Check whether the cache has exceeded its maximum value
        if(this.keys.length > this.capacity) {
            removeCache(this.cache, this.keys, this.keys[0])}}};/ / remove the key
function remove(arr, key) {
    if (arr.length) {
        const index = arr.indexOf(key)
        if (index > - 1) {
            return arr.splice(index, 1)}}}// Remove key from cache
function removeCache(cache, keys, key) {
    cache[key] = null
    remove(keys, key)
}
Copy the code

Advanced: the Map

Map allows you to both hold key-value pairs and remember the original insertion order of the keys

var LRUCache = function(capacity) {
    this.cache = new Map(a)this.capacity = capacity
}

LRUCache.prototype.get = function(key) {
    if (this.cache.has(key)) {
        // Update as it exists
        let temp = this.cache.get(key)
        this.cache.delete(key)
        this.cache.set(key, temp)
        return temp
    }
    return - 1
}

LRUCache.prototype.put = function(key, value) {
    if (this.cache.has(key)) {
        // Update as existing (add after deletion)
        this.cache.delete(key)
    } else if (this.cache.size >= this.capacity) {
        // If not, join
        // If the cache exceeds the maximum value, remove the cache that has not been used recently
        this.cache.delete(this.cache.keys().next().value)
    }
    this.cache.set(key, value)
}
Copy the code

3. More answers:Leetcode146: Design and implement an LRU (least recently used) caching mechanism

Ten, Ali algorithm: write a function to calculate the intersection of multiple arrays

1. The subject

Requirement: Each element in the output must be unique

2. The answer

Using the Reducer function

var intersection = function(. args) {
    if (args.length === 0) {
    return[]}if (args.length === 1) {
    return args[0]}return [...new Set(args.reduce((result, arg) = > {
    return result.filter(item= > arg.includes(item))
  }))]
};
Copy the code

3. More answers:Ali algorithm problem: write a function to calculate the intersection of multiple arrays

Leetcode21: Merge two ordered lists

1. The subject

Merge the two ascending lists into a new ascending list and return. The new list is formed by concatenating all the nodes of the given two lists.

Example:

Input:1->2->4.1->3->4Output:1->1->2->3->4->4
Copy the code

2. The answer

Answer:

Determine the data structure of the problem: singly linked list

Determine the solution to the problem: Val = l2.val = next; val = next; val = next; val = next; val = next; val = next; All the way down to l1, l2 is null

Drawing realization: drawing to help understand

Determine the boundary condition: when the recursion to any list is null, simply point next to another list, no further recursion is needed

Code implementation:

function mergeTwoLists(l1, l2) {
    if(l1 === null) {
        return l2
    }
    if(l2 === null) {
        return l1
    }
    if(l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    } else {
        l2.next = mergeTwoLists(l2.next, l1)
        return l2
    }
}
Copy the code

3. More answers:Leetcode21: Merges two ordered lists

Determine whether a singly linked list has a loop

1. The subject

Given a linked list, determine whether there are rings in the list.

To represent the loop in a given list, we use the integer POS to represent where the end of the list is joined into the list (the index starts at 0). If pos is -1, there are no rings in the list.

Example 1:

Type: head = [3.2.0.4 -], pos = 1Output:trueExplanation: There is a loop in a linked list with a second node at the end.Copy the code

Example 2:

Type: head = [1.2], pos = 0Output:trueExplanation: There is a loop in a linked list, and the end of the loop is connected to the first node.Copy the code

Example 3:

Type: head = [1], pos = - 1Output:falseExplanation: There are no rings in a linked list.Copy the code

Advanced:

Can you solve this problem with O(1) (i.e., constant) memory?

2. The answer

Solution 1: marking method

The list is traversed by adding a flag bit to each node that has been traversed. When the next node has been marked, it proves that the single linked list has a loop

var hasCycle = function(head) {
    while(head) {
        if(head.flag) return true
        head.flag = true
        head = head.next
    }
    return false
};
Copy the code

Time complexity: O(n)

Space complexity: O(n)

Solution two: useJSON.stringify()Cannot serialize structures that contain circular references
var hasCycle = function(head) {
    try{
        JSON.stringify(head);
        return false;
    }
    catch(err){
        return true; }};Copy the code

Time complexity: O(n)

Space complexity: O(n)

Solution three: fast pointer (double pointer method)

If there is a loop in the list, the fast and slow Pointers will eventually point to the same node. Otherwise, the fast and slow Pointers will never meet until the fast pointer points to null

var hasCycle = function(head) {
    if(! head || ! head.next) {return false
    }
    let fast = head.next.next, slow = head.next
    while(fast ! == slow) {if(! fast || ! fast.next)return false
        fast = fast.next.next
        slow = slow.next
    }
    return true
};
Copy the code

Time complexity: O(n)

Space complexity: O(1)

3. More answers:Leetcode141: Determine if a singly linked list has a loop

Leetcode206: reverse linked lists

1. The subject

Example:

Input:1->2->3->4->5- > NULL output:5->4->3->2->1->NULL
Copy the code

Advanced: You can iterate or recursively reverse a linked list. Can you solve this problem in two ways?

2. Answer

Solution 1: iterative method

The following pointer of each node in a single linked list can be pointed to its precursor node

Drawing realization: drawing to help understand

Determine boundary conditions: When the list is NULL or there is only one node in the list, inversion is not required

Code implementation:

var reverseList = function(head) {
    if(! head || ! head.next)return head
    var prev = null, curr = head
    while(curr) {
        // For temporary storage of curr successor nodes
        var next = curr.next
        // Reverse the pointer to curr
        curr.next = prev
        // Change prev, curr
        // The node to be reversed points to the next node
        prev = curr
        curr = next
    }
    head = prev
    return head
};
Copy the code

Time complexity: O(n)

Space complexity: O(1)

Solution two: tail recursive method

Start at the beginning of the node and recursively reverse each node until null

Code implementation:

var reverseList = function(head) {
    if(! head || ! head.next)return head
    head = reverse(null, head)
    return head
};

var reverse = function(prev, curr) {
    if(! curr)return prev
    var next = curr.next
    curr.next = prev
    return reverse(curr, next)
};
Copy the code

Time complexity: O(n)

Space complexity: O(n)

Solution 3: recursive method

The next node of the current node head is recursively reversed

Drawing realization: drawing to help understand

Code implementation:

var reverseList = function(head) {
    if(! head || ! head.next)return head
    var next = head.next
    // Reverse recursively
    var reverseHead = reverseList(next)
    // Change the pointer
    next.next = head
    head.next = null
    return reverseHead
};
Copy the code

Time complexity: O(n)

Space complexity: O(n)

3. More answers:Diagram LeetCode206: Reverse linked list

Leetcode876: find the middle node of the linked list

1. The subject

Given a non-empty single linked list with head, return the middle node of the list.

If there are two intermediate nodes, the second intermediate node is returned.

Example 1:

Input:1.2.3.4.5] Output: the nodes in this list3(Serialized form: [3.4.5]) returns the value of3. (The evaluation system describes the node serialization as [3.4.5]). Note that we return an object of type ListNode, ans, as follows: ans.val =3, ans.next.val = 4, ans.next.next.val = 5, and ans.next. Next = NULL.Copy the code

Example 2:

Input:1.2.3.4.5.6] Output: the nodes in this list4(Serialized form: [4.5.6]) since the list has two intermediate nodes, the value is3 和 4We return the second node.Copy the code

Tip:

The number of nodes in a given list is between 1 and 100.

2. Solution: fast and slow pointer

The fast pointer takes two steps at a time, while the slow pointer takes one step at a time. When the fast pointer comes to the end, the slow pointer just goes to the middle

var middleNode = function(head) {
    let fast = head, slow = head
    while(fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
};
Copy the code

Time complexity: O(n)

Space complexity: O(1)

3. More answers:Leetcode876: Find the middle node of the linked list

Fifteen, the first phase of the front-end algorithm training camp free to join

Welcome to pay attention to “front bottle gentleman”, reply “algorithm” automatically join, from 0 to 1 to build a complete data structure and algorithm system!

Here, the bottle gentleman not only introduces the algorithm, but also the algorithm and front-end areas of combination, including browser, HTTP, V8, React, Vue source code, etc.

Here, you can learn a dafang algorithm (Ali, Tencent, Baidu, byte, etc.) or Leetcode every day, and you will answer it the next day!

Scan code into camp learning! If the number of qr codes has reached the upper limit, you can scan the bottom QR code and reply to the “algorithm” in the public account “Front Bottle Gentleman” to automatically pull you into the group learning

⬆️ Scan the code to follow the public account “Front-end Bottle Gentleman”, reply to “algorithm” and the account will be automatically added to 👍👍👍