Front-end advanced algorithm 6: a look at the queue and matching algorithm

The introduction

As for the queue data structure, according to Mr. Bottles, the front end needs to understand the queue structure mainly includes double-ended queue and sliding window, which are commonly used data structures in algorithms.

Therefore, the main contents of this section are as follows:

• Data structure: Queue
• Double-ended queue (Deque)
• Application of double-ended queues: flipping words in strings
• The sliding window
• Sliding window application: Longest common substring without repeating characters
• One last Leetcode problem: sliding window maxima

Enter the body below 👇, if you can, a like 👍 support bai 😊

Data structure: queue

A queue is similar to a stack, except that a queue is an ordered set of first-in, first-out (FIFO) principles. Its structure is similar to the following:

Common queue operations include enqueue(e) to queue, dequeue() to queue, isEmpty() to see if it isEmpty, front() to get the head element, clear() to clear the queue, and size() to get the queue length.

Code implementation

function Queue() {
  let items = []
  this.enqueue = function(e) {
    items.push(e)
  }
  this.dequeue = function() {
    return items.shift()
  }
  this.isEmpty = function() {
    return items.length === 0
  }
  this.front = function() {
    return items[0]}this.clear = function() { 
    items = [] 
  }
  this.size = function() {
    return items.length
  }
}
Copy the code

Search: Search from the head, from time complexity O(n)

Insert or delete: The time complexity of loading and unloading is O(1)

2. Dual-end Queue (Deque)

1. What is a Deque

Deque is expanded on the basis of the original queue: both the head and tail of the queue can enter and leave the queue. Its data structure is as follows:

Code implementation:

function Deque() {
  let items = []
  this.addFirst = function(e) {
    items.unshift(e)
  }
  this.removeFirst = function() {
    return items.shift()
  }
  this.addLast = function(e) {
    items.push(e)
  }
  this.removeLast = function() {
    return items.pop()
  }
  this.isEmpty = function() {
    return items.length === 0
  }
  this.front = function() {
    return items[0]}this.clear = function() { 
    items = [] 
  }
  this.size = function() {
    return items.length
  }
}
Copy the code

Let’s look at a classic two-endian queue problem 👇

2. Byte &leetcode151: Flip the word in the string

Given a string, flip each word in the string one by one.

Example 1:

Input:"the sky is blue"Output:"blue is sky the"
Copy the code

Example 2:

Input:" hello world! "Output:"world! hello"Explanation: The input string can contain extra Spaces before or after it, but cannot contain inverted characters.Copy the code

Example 3:

Input:"a good example"Output:"example good a"Explanation: If there is extra space between two words, reduce the space between the inverted words to only one.Copy the code

Description:

• Blank characters form a word.
• An input string can contain extra Spaces before or after it, but not inverted characters.
• If there is extra space between two words, reduce the space between the inverted words to only one.

Use a double-ended queue to solve the problem

• First remove the left and right Spaces of the string
• Each word in the string is read one by one and placed in turn on the heads of the two-enqueued queue
• Convert the queue to string output (delimited with Spaces)

Drawing and understanding:

Code implementation:

var reverseWords = function(s) {
    let left = 0
    let right = s.length - 1
    let queue = []
    let word = ' '
    while (s.charAt(left) === ' ') left ++
    while (s.charAt(right) === ' ') right --
    while (left <= right) {
        let char = s.charAt(left)
        if (char === ' ' && word) {
            queue.unshift(word)
            word = ' '
        } else if(char ! = =' '){
            word += char
        }
        left++
    }
    queue.unshift(word)
    return queue.join(' ')};Copy the code

See the illustration byte-LeetCode151: Flipping words in strings for more

Three, sliding window

1. What is sliding Windows

This is another important application of queues

As the name suggests, a sliding window is a sublist running on a large array, a collection of underlying elements.

Suppose there is an array [a, b, C, d, e, f, g, h] and a sliding window of size 3 sliding on it, then:

[a b c]
  [b c d]
    [c d e]
      [d e f]
        [e f g]
          [f g h]
Copy the code

In general, this window is used to slide the array within the legal range and record some useful data dynamically. In many cases, it can greatly improve the efficiency of the algorithm.

Let’s look at a classic sliding window problem 👇

2. Byte&leetcode3: the oldest string without repeating characters

Given a string, find the length of the smallest string that does not contain repeating characters.

Example 1:

Input:"abcabcbb"Output:3Because the oldest string without repeating characters is"abc", so its length is3.Copy the code

Example 2:

Input:"bbbbb"Output:1Because the oldest string without repeating characters is"b", so its length is1.Copy the code

Example 3:

Input:"pwwkew"Output:3Because the oldest string without repeating characters is"wke", so its length is3. Please note that your answer must be the length of the substring,"pwke"It's a subsequence, not a substring.Copy the code

Use an array to maintain a sliding window

Iterates through the string to see if the character is in the sliding window array

• Not in thepushInto the array
• Delete the same character in the sliding window array and the character before the same character, and then the current characterpushInto the array
• thenmaxUpdate to the length of the current oldest string

After traversing, return Max

Draw a picture to help understand:

Code implementation:

var lengthOfLongestSubstring = function(s) {
    let arr = [], max = 0
    for(let i = 0; i < s.length; i++) {
        let index = arr.indexOf(s[i])
        if(index ! = =- 1) {
            arr.splice(0, index+1);
        }
        arr.push(s.charAt(i))
        max = Math.max(arr.length, max) 
    }
    return max
};
Copy the code

Time complexity: O(N)²), whicharr.indexOf()Time is O(n),arr.splice(0, index+1)Is also O(n).

Space complexity: O(n)

See byte&leetcode3: the oldest string without repeating characters for more

Finally, try a Leetcode problem!

Leetcode239: Sliding window maximum value problem

Given an array nums and the size k of the sliding window, find the maximum number of sliding Windows.

Example:

Enter: nums = [1.3.- 1.- 3.5.3.6.7], and k =3Output:3.3.5.5.6.7] 
Copy the code

Explanation:

The maximum position of a sliding window

[1 3-1] -3 5 3 6 7 3 1 [3-1-3] 5 3 6 7 3 1 3 [-1-3 5] 3 6 7 5 1 3-1 [-3 5 3] 6 7 5 1 3-1 [5 3 6 6] 7 6 1 3-1 5 [3 6 7] 7

Tip:

You can assume that k is always valid, 1 ≤ k ≤ the size of the input array if the input array is not empty.

Try it yourself and submit your answers to github.com/sisterAn/Ja… , Aquarius will answer 😊 tomorrow

Five, past wonderful series of articles

• Front-end advanced algorithm: common algorithm problems and perfect problem solutions
• Video interview uHF online programming questions, enough to handle most companies
• 10 questions and 10 answers, with a quick introduction to front-end algorithms
• Front-end advanced Algorithm 5: Fully read the stack structure used by the front-end (+ LeetCode
• Front-end advanced algorithm 4: Linked lists are so simple
• Front-end advanced algorithm 3: Learning the LRU algorithm from the browser cache elimination strategy and Vue’s keep-alive
• Bottle jun front-end advanced algorithm camp first week summary
• Front-end advanced algorithm 2: JavaScript array from Chrome V8 source code
• Front-end advanced algorithm 1: How to analyze and count the execution efficiency and resource consumption of algorithms?

The first phase of the front-end algorithm training camp is free to join

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

Here, I not only introduce algorithms, but also combine algorithms with various front-end areas, including browsers, HTTP, V8, React, Vue source code, and so on.

Here, you can learn a big factory algorithm (Ali, Tencent, Baidu, byte, etc.) or leetcode every day, Aquarius will solve it the next day!

⬆️ scan the public account “front-end bottle Jun” and reply “algorithm” to automatically join 👍👍👍