引言

瓶子君又来啦，她带着前端算法来了

大厂面试越来越难，对算法的要求也越来越多，当面试官问到一个算法题，给出一份完美答案能大大提高面试官的好感度，本系列就是致力于打造一套适用于前端的算法。

往期精彩系列

• 视频面试超高频在线编程题，搞懂这些足以应对大部分公司

• 前端进阶算法5：全方位解读前端用到的栈结构（+leetcode刷题）

• 10 问 10 答，带你快速入门前端算法

• 前端进阶算法4：链表原来如此简单(+leetcode刷题）

• 前端进阶算法3：从浏览器缓存淘汰策略和Vue的keep-alive学习LRU算法

• 瓶子君前端算法集训营第一期开营啦，免费哟

• 前端进阶算法2：从Chrome  V8源码看JavaScript数组(附赠腾讯面试题)

• 前端进阶算法1：如何分析、统计算法的执行效率和资源消耗？

以及题目：

• 图解leetcode88：合并两个有序数组^[8]
• 字节&leetcode1：两数之和^[9]
• 腾讯：数组扁平化、去重、排序^[10]
• leetcode349：给定两个数组，编写一个函数来计算它们的交集^[11]
• leetcode146：设计和实现一个LRU（最近最少使用）缓存机制^[12]
• 阿里算法题：编写一个函数计算多个数组的交集^[13]
• leetcode21：合并两个有序链表^[14]
• 有赞&leetcode141：判断一个单链表是否有环^[15]
• 图解leetcode206：反转链表^[16]
• leetcode876：求链表的中间结点^[17]
• leetcode19：删除链表倒数第 n 个结点^[18]
• 图解字节&leetcode160：编写一个程序，找到两个单链表相交的起始节点^[19]
• 图解字节&leetcode151：翻转字符串里的单词^[20]
• 图解leetcode14：最长公共前缀^[21]
• 百度：实现一个函数，判断输入是不是回文字符串^[22]
• 字节&Leetcode3：无重复字符的最长子串^[23]
• 字节&leetcode155：最小栈（包含getMin函数的栈）^[24]
• 图解腾讯&leetcode20：有效的括号^[25]
• leetcode1047：删除字符串中的所有相邻重复项^[26]

本节是第四周的总结与回顾，下面开始进入正题吧！

一、百度：实现一个函数，判断输入是不是回文字符串

1. 解法一：使用API

function isPlalindrome(input) {
  if (typeof input !== 'string') return false;
  return input.split('').reverse().join('') === input;
}

2. 解法二：不使用API

function isPlalindrome(input) {
  if (typeof input !== '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
}

3. 更多题解

详见 百度：实现一个函数，判断输入是不是回文字符串^[27]

二、字节&Leetcode3：无重复字符的最长子串

1. 题目

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

2. 解法

解法一：维护数组

解题思路： 使用一个数组来维护滑动窗口

遍历字符串，判断字符是否在滑动窗口数组里

• 不在则 push 进数组
• 在则删除滑动窗口数组里相同字符及相同字符前的字符，然后将当前字符 push 进数组
• 然后将 max 更新为当前最长子串的长度

遍历完，返回 max 即可

画图帮助理解一下：

代码实现：

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
};

时间复杂度：O(n²)， 其中 arr.indexOf() 时间复杂度为 O(n) ，arr.splice(0, index+1) 的时间复杂度也为 O(n)

空间复杂度：O(n)

解法二：维护下标

解题思路： 使用下标来维护滑动窗口

代码实现：

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
};

时间复杂度：O(n²)

空间复杂度：O(n)

解法三：优化的Map

解题思路：

使用 map 来存储当前已经遍历过的字符，key 为字符，value 为下标

使用 i 来标记无重复子串开始下标，j 为当前遍历字符下标

遍历字符串，判断当前字符是否已经在 map 中存在，存在则更新无重复子串开始下标 i 为相同字符的下一位置，此时从 i 到 j 为最新的无重复子串，更新 max ，将当前字符与下标放入 map 中

最后，返回 max 即可

代码实现：

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
};

时间复杂度：O(n)

空间复杂度：O(n)

3. 更多题解

详见 字节&Leetcode3：无重复字符的最长子串^[28]

三、文章：全方位解读栈结构

1. 数据结构栈

栈是一种遵从后进先出 (LIFO / Last In First Out) 原则的有序集合，它的结构类似如下：

代码实现

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 = [] 
  }
}

查找：从栈头开始查找，时间复杂度为 O(n)

插入或删除：进栈与出栈的时间复杂度为 O(1)

2. 面试：调用栈

调用栈是 JavaScript 用来管理函数执行上下文的一种数据结构，它记录了当前函数执行的位置，哪个函数正在被执行。如果我们执行一个函数，就会为函数创建执行上下文并放入栈顶。如果我们从函数返回，就将它的执行上下文从栈顶弹出。也可以说调用栈是用来管理这种执行上下文的栈，或称执行上下文栈（执行栈）。

3. 面试：栈空间与堆空间

JavaScript 中的内存空间主要分为三种类型：

• 代码空间：主要用来存放可执行代码
• 栈空间：调用栈的存储空间就是栈空间。
• 堆空间

代码空间主要用来存放可执行代码的。栈空间及堆空间主要用来存放数据的。接下来我们主要介绍栈空间及堆空间。

当调用栈中执行完成一个执行上下文时，需要进行垃圾回收该上下文以及相关数据空间，存放在栈空间上的数据通过 ESP 指针来回收，存放在堆空间的数据通过副垃圾回收器（新生代）与主垃圾回收器（老生代）来回收。

4. 详情

详细请看 前端进阶算法5：全方位解读前端用到的栈结构（+leetcode刷题）^[29]

四、字节&leetcode155：最小栈（包含getMin函数的栈）

1. 题目

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

2. 解法

在常数时间内检索到最小元素的栈，即仅需保证 getMin 的时间复杂度为 O(1) 即可

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

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

// 出栈
MinStack.prototype.pop = function() {
    let num = this.items.pop() 
    this.min = Math.min(...this.items)
    return num
};

// 获取栈顶元素
MinStack.prototype.top = function() {
    if(!this.items.length) return null
    return this.items[this.items.length -1] 
};

// 检索栈中的最小元素
MinStack.prototype.getMin = function() {
    return this.min
};

时间复杂度：进栈O(1)，出栈O(n)，获取栈顶元素O(1)，获取最小元素O(1)

空间复杂度：O(n)

3. 更多题解

详见 字节&leetcode155：最小栈（包含getMin函数的栈）^[30]

五、图解腾讯&leetcode20：有效的括号

1. 题目

给定一个只包括 '(' ，')' ，'{' ，'}' ，'[' ，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

2. 解法：利用栈结构

解题思路： 将字符串中的字符依次入栈，遍历字符依次判断：

• 首先判断该元素是否是 { 、 ( 、 [ ，直接入栈
• 否则该字符为 } 、 ) 、 ] 中的一种，如果该字符串有效，则该元素应该与栈顶匹配，例如栈中元素有 ({， 如果继续遍历到的元素为 ), 那么当前元素序列为 ({) 是不可能有效的，所以此时与栈顶元素匹配失败，则直接返回 false ，字符串无效

当遍历完成时，所有已匹配的字符都已匹配出栈，如果此时栈为空，则字符串有效，如果栈不为空，说明字符串中还有未匹配的字符，字符串无效

画图帮助理解一下：

代码实现：

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
};

时间复杂度：O(n)

空间复杂度：O(n)

3. 更多题解

详见 图解腾讯&leetcode20：有效的括号^[31]

六、leetcode1047：删除字符串中的所有相邻重复项

1. 题目

给出由小写字母组成的字符串 S ，重复项删除操作 会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1. <= S.length <= 20000
2. S 仅由小写英文字母组成。

2. 解法：利用栈

解题思路： 遍历字符串，依次入栈，入栈时判断与栈头元素是否一致，如果一致，即这两个元素相同相邻，则需要将栈头元素出栈，并且当前元素也无需入栈

解题步骤： 遍历字符串，取出栈头字符，判断当前字符与栈头字符是否一致

• 不一致，栈头字符进栈，当前字符进栈
• 一致，即栈头字符与当前字符相同相邻，都不需要进栈，直接进入下次遍历即可

遍历完成后，返回栈中字符串

代码实现：

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('')
};

时间复杂度：O(n)

空间复杂度：O(n)