Front-end advanced algorithm: common algorithm and perfect problem solution

The introduction

Here comes Ms. Bottle again, with her front-end algorithm 👏👏👏

Big factory interview is more and more difficult, the requirements of the algorithm is more and more, when the interviewer asks an algorithm question, give a perfect answer can greatly improve the impression of the interviewer, this series is dedicated to create a set of applicable to the front-end algorithm.

Past wonderful series of articles:

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

Summary of three communication group brush questions:

Video interview uHF online programming questions. This is enough for most companies
10 questions and 10 answers, a quick introduction to front-end algorithms
Summary of the first week of the advanced algorithm camp

Topics (topics will only be posted in the “Front-end Advanced Algorithm Training Camp” every morning at 9:00am) :

An array of articles:

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

List article:

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
Leetcode19: deletes the NTH node from the reciprocal of the linked list
Diagram Byte & LeetCode160: Write a program to find the starting node where two single linked lists intersect

String:

Diagram byte & Leetcode151: Flips the words in a string
Leetcode14: longest common prefix
Baidu: implement a function to determine whether the input is a palindrome string
Byte &Leetcode3: The oldest string with no duplicate characters

Stack article:

Byte & LeetCode155: minimum stack (stack containing getMin function)
Figure Tencent & LeetCode20: valid parentheses
Leetcode1047: Removes all adjacent duplicates from a string

This section is a summary and review of the fourth week, so let’s get started! 👇 👇 👇

Baidu: a function to determine whether the input is a palindrome string

Solution 1: Use an API

function isPlalindrome(input) {
  if (typeofinput ! = ='string') return false;
  return input.split(' ').reverse().join(' ') === input;
}
Copy the code

Solution 2: No API

function isPlalindrome(input) {
  if (typeofinput ! = ='string') return false;
  let i = 0, j = input.length - 1
  while(i < j) {
      if(input.charAt(i) ! == input.charAt(j))return false
      i ++
      j --
  }
  return true
}
Copy the code

3. More problems

Implement a function to determine whether the input is a palindrome string

Byte &Leetcode3: the oldest string with no duplicate characters

1. The subject

Given a string, find the longest string that does not contain repeating characters.

Example 1:

Input:"abcabcbb"Output:3Explanation: Because the most common string with no duplicate characters is"abc", so its length is zero3.Copy the code

Example 2:

Input:"bbbbb"Output:1Explanation: Because the most common string with no duplicate characters is"b", so its length is zero1.Copy the code

Example 3:

Input:"pwwkew"Output:3Explanation: Because the most common string with no duplicate characters is"wke", so its length is zero3. Note that your answer must be the length of the substring,"pwke"It's a subsequence, not a substring.Copy the code

2. The solution

Solution 1: Maintain arrays

Use an array to maintain the sliding window

Iterates over the string to see if the characters are in the sliding window array

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

After traversal, return Max

To help you 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()The time complexity is O(n),arr.splice(0, index+1)The time complexity of is also O(n).

Space complexity: O(n)

Solution 2: maintain subscripts

Use subscript to maintain the sliding window

Code implementation:

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

Time complexity: O(n)²)

Space complexity: O(n)

Solution 3: Optimized Map

答案 :

Map is used to store the characters that have been traversed. Key is the character and value is the subscript

Use I to mark the non-repeating substring start index and j to mark the current traversal character index

Iterate over the string to determine whether the current character already exists in the map. If yes, update the starting substring with no repetition, the substring I is the next position of the same character. At this time, the substring from I to j is the latest without repetition

Finally, return Max

Code implementation:

var lengthOfLongestSubstring = function(s) {
    let map = new Map(), max = 0
    for(let i = 0, j = 0; j < s.length; j++) {
        if(map.has(s[j])) {
            i = Math.max(map.get(s[j]) + 1, i)
        }
        max = Math.max(max, j - i + 1)
        map.set(s[j], j)
    }
    return max
};
Copy the code

Time complexity: O(n)

Space complexity: O(n)

3. More problems

See byte &Leetcode3: Maximum string with no duplicate characters

Three, the article: comprehensive interpretation of the stack structure

1. Data structure stack

A stack is an ordered collection that follows the LIFO/Last In First Out principle. Its structure is similar to the following:

Code implementation

function Stack() {
  let items = []
  this.push = function(e) { 
    items.push(e) 
  }
  this.pop = function() { 
    return items.pop() 
  }
  this.isEmpty = function() { 
    return items.length === 0 
  }
  this.size = function() { 
    return items.length 
  }
  this.clear = function() { 
    items = [] 
  }
}
Copy the code

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

Insert or Delete: The time complexity between the stack and the stack is O(1)

2. Interview: call stack

The call stack is a data structure used by JavaScript to manage the execution context of a function. It records where a function is currently executing and which function is being executed. If we execute a function, the execution context for the function is created and put on the top of the stack. If we return from a function, we pop its execution context off the top of the stack. It can also be said that the call stack is the stack used to manage this execution context, or execution context stack (execution stack).

Interview: Stack space vs. heap space

There are three main types of memory Spaces in JavaScript:

Code space: Mainly used to store executable code
Stack space: The storage space of the call stack is the stack space.
Heap space

Code space is mainly used to store executable code. The stack space and the heap space are mainly used to store data. Next we will focus on stack space and heap space.

When an execution context is completed in the call stack, the context and related data space need to be garbage collected. The data stored in the stack space is collected by the ESP pointer, and the data stored in the heap space is collected by the secondary garbage collector (new generation) and the primary garbage collector (old generation).

Details of 4.

In detail, see the front-end advanced algorithm 5: full interpretation of the front-end used stack structure (+ Leetcode brush problem)

Byte & LeetCode155: minimum stack (including getMin function stack)

1. The subject

Design a stack that supports push, pop, and top operations and can retrieve the smallest element in constant time.

push(x)— Push element x onto the stack.
pop()Delete the top element of the stack.
top()Get the top element on the stack.
getMin()Retrieve the smallest element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(2 -);
minStack.push(0);
minStack.push(- 3); minStack.getMin(); - > to return- 3.minStack.pop(); minStack.top(); - > to return0.minStack.getMin(); - > to return- 2.
Copy the code

2. The solution

Retrieve the stack of the smallest element in constant time, that is, only need to ensure the time complexity of getMin is O(1)

var MinStack = function() {
    this.items = []
    this.min = null
};

/ / into the stack
MinStack.prototype.push = function(x) {
    if(!this.items.length) this.min = x 
    this.min = Math.min(x, this.min)
    this.items.push(x) 
};

/ / out of the stack
MinStack.prototype.pop = function() {
    let num = this.items.pop() 
    this.min = Math.min(... this.items)return num
};

// Get the top element of the stack
MinStack.prototype.top = function() {
    if(!this.items.length) return null
    return this.items[this.items.length - 1]};// Retrieve the smallest element in the stack
MinStack.prototype.getMin = function() {
    return this.min
};
Copy the code

Time complexity: push O(1), exit O(n), get top element O(1), get minimum element O(1)

Space complexity: O(n)

3. More problems

See byte & LeetCode155: Minimum stack (including getMin function stack)

Tencent & LeetCode20: valid parentheses

1. The subject

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘string, to determine whether a string is effective.

A valid string must meet the following requirements:

The opening parenthesis must be closed with a closing parenthesis of the same type.
The opening brackets must be closed in the correct order.

Note that an empty string can be considered a valid string.

Example 1:

Input:"()"Output:true
Copy the code

Example 2:

Input:"[the] {} ()"Output:true
Copy the code

Example 3:

Input:"(]"Output:false
Copy the code

Example 4:

Input:"([]"Output:false
Copy the code

Example 5:

Input:"{[]}"Output:true
Copy the code

2. Solution: use stack structure

The characters in the string are pushed on the stack, and the characters are traversed.

First determine whether the element is{ 、 ( 、 [, directly push the stack
Otherwise, the character is} 、 ) 、 ]If the string is valid, then the element should match the top of the stack, such as the stack element({If the element to which we continue to iterate is), then the current sequence of elements is({)Can not be valid, so the match with the top element of the stack fails, and returns directlyfalseInvalid string

If the stack is empty, the string is valid. If the stack is not empty, there are unmatched characters in the string, and the string is invalid

To help you understand:

Code implementation:

var isValid = function(s) {
    let map = {
        '{': '} '.'(': ') '.'[': '] '
    }
    let stack = []
    for(let i = 0; i < s.length ; i++) {
        if(map[s[i]]) {
            stack.push(s[i])
        } else if(s[i] ! == map[stack.pop()]){return false}}return stack.length === 0
};
Copy the code

Time complexity: O(n)

Space complexity: O(n)

3. More problems

See the illustration Tencent & LeetCode20: Valid parentheses

Leetcode1047: Remove all adjacent duplicates from a string

1. The subject

Given the lowercase character string S, the deduplication operation selects two adjacent, identical letters and deletes them.

The deduplication operation is repeated on S until the deletion cannot continue.

Returns the final string after all deduplications have been completed. The answer is guaranteed to be unique.

Example:

Input:"abbaca"Output:"ca"Explanation: For example, in"abbaca"In, we can delete"bb"Since the letters are adjacent and identical, this is the only duplicate item that can be deleted at this time. And then we get the string"aaca"Of which there is only"aa"You can perform a de-duplication operation, so the last string is"ca".Copy the code

Tip:

<= S.length <= 20000
SConsists of lowercase letters only.

2. Solution: use stack

If it is consistent, that is, the two elements are the same and adjacent, then the head element needs to be out of the stack, and the current element does not need to be pushed

Problem solving steps: walk through the string, take out the stack header character, determine whether the current character and the stack header character is consistent

Inconsistent, stack header character pushes, current character pushes
Consistent, that is, the stack header character and the current character are the same adjacent, do not need to enter the stack, directly into the next traversal

When the traversal is complete, the string on the stack is returned

Code implementation:

var removeDuplicates = function(S) {
    let stack = []
    for(c of S) {
        let prev = stack.pop()
        if(prev ! == c) { stack.push(prev) stack.push(c) } }return stack.join(' ')};Copy the code

Time complexity: O(n)

Space complexity: O(n)

3. More problems

See LeetCode1047: Remove all adjacent duplicates in a string

Seven, front-end algorithm training camp first free to join

Build a complete data structure and algorithm system from 0 to 1!

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 the code to join the group. If the group number has reached the online limit, follow the public account “Front-end Bottle Gentleman” and reply to the “algorithm” to automatically join the group

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

Front-end advanced algorithm: common algorithm and perfect problem solution

The introduction

Baidu: a function to determine whether the input is a palindrome string

Solution 1: Use an API

Solution 2: No API

3. More problems

Byte &Leetcode3: the oldest string with no duplicate characters

1. The subject

2. The solution

Solution 1: Maintain arrays

Solution 2: maintain subscripts

Solution 3: Optimized Map

3. More problems

Three, the article: comprehensive interpretation of the stack structure

1. Data structure stack

2. Interview: call stack

Interview: Stack space vs. heap space

Details of 4.

Byte & LeetCode155: minimum stack (including getMin function stack)

1. The subject

2. The solution

3. More problems

Tencent & LeetCode20: valid parentheses

1. The subject

2. Solution: use stack structure

3. More problems

Leetcode1047: Remove all adjacent duplicates from a string

1. The subject

2. Solution: use stack

3. More problems

Seven, front-end algorithm training camp first free to join

Related Posts

A lexical analyzer with jQuery (1)

Chapter 3 of Flutter Construction of Flutter engineering environment

CSS3 Animation Transition