高级前端进阶
引言
现在大厂面试几乎都会问到算法，回答不上来会让你在面试官前大打折扣。前端怎么进阶算法喃？
这里汇总了瓶子君前端进阶算法的资料，从 0 到 1 构建完整的前端数据结构与算法体系。
本周已经不单是简单的链表操作（一般链表的问题可以考虑使用快慢指针），开始涉及五大常用算法策略、二叉树、Trie树、队列等，这里仅作为入门，后面会详细介绍，发散思维，你会发现面试中的算法、开发中的算法真的很 easy。
往期精彩系列
以及题目（群内每日一题，瓶子君第二天解答）：
图解leetcode88：合并两个有序数组[1] 字节&leetcode1：两数之和[2] 腾讯：数组扁平化、去重、排序[3] leetcode349：给定两个数组，编写一个函数来计算它们的交集[4] leetcode146：设计和实现一个LRU（最近最少使用）缓存机制[5] 阿里算法题：编写一个函数计算多个数组的交集[6] leetcode21：合并两个有序链表[7] 有赞&leetcode141：判断一个单链表是否有环[8] 图解leetcode206：反转链表[9] leetcode876：求链表的中间结点[10] leetcode19：删除链表倒数第 n 个结点[11] 图解字节&leetcode160：编写一个程序，找到两个单链表相交的起始节点[12] 图解字节&leetcode151：翻转字符串里的单词[13] 图解leetcode14：最长公共前缀[14]
因微信公众号不支持外链，点击底部「阅读原文」，查看整个系列！
本节是第三周的总结与回顾，下面开始进入正题吧！???
一、图解字节&leetcode14：最长公共前缀
1. 题目
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
2. 答案
解法一：逐个比较
解题思路： 从前往后一次比较字符串，获取公共前缀
画图帮助理解一下：
代码实现：
var longestCommonPrefix = function(strs) {
if (strs === null || strs.length === 0) return "";
let prevs = strs[0]
for(let i = 1; i < strs.length; i++) {
let j = 0
for(; j < prevs.length && j < strs[i].length; j++) {
if(prevs.charAt(j) !== strs[i].charAt(j)) break
}
prevs = prevs.substring(0, j)
if(prevs === "") return ""
}
return prevs
};
时间复杂度：O(s)，s 是所有字符串中字符数量的总和
空间复杂度：O(1)
解法二：仅需最大、最小字符串的最长公共前缀
解题思路： 获取数组中的最大值及最小值字符串，最小字符串与最大字符串的最长公共前缀也为其他字符串的公共前缀，即为字符串数组的最长公共前缀
例如 abc 、 abcd 、ab 、ac ，最小 ab 与最大 ac 的最长公共前缀一定也是 abc 、 abcd 的公共前缀
画图帮助理解一下：
代码实现：
var longestCommonPrefix = function(strs) {
if (strs === null || strs.length === 0) return "";
if(strs.length === 1) return strs[0]
let min = 0, max = 0
for(let i = 1; i < strs.length; i++) {
if(strs[min] > strs[i]) min = i
if(strs[max] < strs[i]) max = i
}
for(let j = 0; j < strs[min].length; j++) {
if(strs[min].charAt(j) !== strs[max].charAt(j)) {
return strs[min].substring(0, j)
}
}
return strs[min]
};
时间复杂度：O(n+m)，n是数组的长度， m 是字符串数组中最短字符的长度
空间复杂度：O(1)
解法三：分治策略 归并思想
分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。
这道题就是一个典型的分治策略问题：
问题：求多个字符串的最长公共前缀 分解成多个相似的子问题：求两个字符串的最长公共前缀 子问题可以简单求解：两个字符串的最长公共前缀求解很简单 原问题的解为子问题解的合并：多个字符串的最长公共前缀为两两字符串的最长公共前缀的最长公共前缀，我们可以归并比较两最长公共前缀字符串的最长公共前缀，知道最后归并比较成一个，则为字符串数组的最长公共前缀： LCP(S1, S2, ..., Sn) = LCP(LCP(S1, Sk), LCP(Sk+1, Sn))
画图帮助理解一下：
以 abc 、 abcd 、ab 、ac 为例：
代码实现：
var longestCommonPrefix = function(strs) {
if (strs === null || strs.length === 0) return "";
return lCPrefixRec(strs)
};
// 若分裂后的两个数组长度不为 1，则继续分裂
// 直到分裂后的数组长度都为 1，
// 然后比较获取最长公共前缀
function lCPrefixRec(arr) {
let length = arr.length
if(length === 1) {
return arr[0]
}
let mid = Math.floor(length / 2),
left = arr.slice(0, mid),
right = arr.slice(mid, length)
return lCPrefixTwo(lCPrefixRec(left), lCPrefixRec(right))
}
// 求 str1 与 str2 的最长公共前缀
function lCPrefixTwo(str1, str2) {
let j = 0
for(; j < str1.length && j < str2.length; j++) {
if(str1.charAt(j) !== str2.charAt(j)) {
break
}
}
return str1.substring(0, j)
}
时间复杂度：O(s)，s 是所有字符串中字符数量的总和
空间复杂度：O(m*logn)，n是数组的长度，m为字符串数组中最长字符的长度
解法四：Trie 树（字典树）
Trie 树，也称为字典树或前缀树，顾名思义，它是用来处理字符串匹配问题的数据结构，以及用来解决集合中查找固定前缀字符串的数据结构。
解题思路： 构建一个 Trie 树，字符串数组的最长公共序列就为从根节点开始遍历树，直到：
遍历节点存在超过一个子节点的节点
或遍历节点为一个字符串的结束字符
为止，走过的字符为字符串数组的最长公共前缀
画图帮助理解一下：
构建一个 Trie 树，以 abc 、 abcd 、ab 、ac 为例：
代码实现：
var longestCommonPrefix = function(strs) {
if (strs === null || strs.length === 0) return "";
// 初始化 Trie 树
let trie = new Trie()
// 构建 Trie 树
for(let i = 0; i < strs.length; i++) {
if(!trie.insert(strs[i])) return ""
}
// 返回最长公共前缀
return trie.searchLongestPrefix()
};
// Trie 树
var Trie = function() {
this.root = new TrieNode()
};
var TrieNode = function() {
// next 放入当前节点的子节点
this.next = {};
// 当前是否是结束节点
this.isEnd = false;
};
Trie.prototype.insert = function(word) {
if (!word) return false
let node = this.root
for (let i = 0; i < word.length; i++) {
if (!node.next[word[i]]) {
node.next[word[i]] = new TrieNode()
}
node = node.next[word[i]]
}
node.isEnd = true
return true
};
Trie.prototype.searchLongestPrefix = function() {
let node = this.root
let prevs = ''
while(node.next) {
let keys = Object.keys(node.next)
if(keys.length !== 1) break
if(node.next[keys[0]].isEnd) {
prevs += keys[0]
break
}
prevs += keys[0]
node = node.next[keys[0]]
}
return prevs
}
时间复杂度：O(s+m)，s 是所有字符串中字符数量的总和，m为字符串数组中最长字符的长度，构建 Trie 树需要 O(s) ，最长公共前缀查询操作的复杂度为 O(m)
空间复杂度：O(s)，用于构建 Trie 树
leetcode[15]
3. 更多解法请看 图解字节&leetcode14：最长公共前缀[16]
二、图解字节&leetcode151：翻转字符串里的单词
1. 题目
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
无空格字符构成一个单词。 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
2. 答案
解法一：正则 + JS API
var reverseWords = function(s) {
return s.trim().replace(/\s+/g, ' ').split(' ').reverse().join(' ')
};
解法二：双端队列（不使用 API）
双端队列，故名思义就是两端都可以进队的队列
解题思路：
首先去除字符串左右空格 逐个读取字符串中的每个单词，依次放入双端队列的对头 再将队列转换成字符串输出（已空格为分隔符）
画图理解：
代码实现：
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(' ')
};
leetcode[17]
3. 更多解法请看 图解字节&leetcode151：翻转字符串里的单词[18]
三、图解字节&leetcode160：编写一个程序，找到两个单链表相交的起始节点
1. 题目
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
注意：
如果两个链表没有交点，返回 null. 在返回结果后，两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
2. 答案
解法一：标记法(简单但空间复杂度为O(n)，不符合，仅做参考)
解题思路： 两次遍历，先遍历一个链表，给链表中的每个节点都增加一个标志位，然后遍历另外一个链表，遍历到第一个已被标志过的节点为两链表相交的起始节点。
若遍历完都没有发现已被标志过的节点，则两链表不相交，返回 null
var getIntersectionNode = function(headA, headB) {
while(headA) {
headA.flag = true
headA = headA.next
}
while(headB) {
if (headB.flag) return headB
headB = headB.next
}
return null
};
时间复杂度：O(n)
空间复杂度：O(n)
解法二：双指针法
解题思路： 如果 A、B 两链表相交，则 A 、B 自相交点往后的链表是一致的。
我们可以尝试消除 A、B 链表的长度差，同步遍历上图中的方框里的节点，判断是否有相同节点，若有相同则是两链表相交，返回第一个相同节点 即可。否则返回 null ，两链表不相交。
解题步骤：
同步遍历 A、B 链表 pA、pB，直到遍历完其中一个链表（短链表），如上图，设A为长链表那么此时 A、B 两遍表的长度差就为 pA到链尾的长度，此时可以把pB指向长链表的表头headA，继续同步遍历，直到遍历完长链表此时， headA到pB的长度就为两链表的长度差，pB到链表的长度与headB到链尾的长度一致此时，可将 pA指向headB，然后同步遍历pB及pA，直到有相交节点，返回相交节点，否则返回null
画图帮助理解：
var getIntersectionNode = function(headA, headB) {
// 清除高度差
let pA = headA, pB = headB
while(pA || pB) {
if(pA === pB) return pA
pA = pA === null ? headB : pA.next
pB = pB === null ? headA : pB.next
}
return null
};
时间复杂度：O(n)
空间复杂度：O(1)
leetcode[19]
3. 更多解法请看 图解字节&leetcode160：编写一个程序，找到两个单链表相交的起始节点[20]
四、leetcode19：删除链表倒数第 n 个结点
1. 题目
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
2. 解法：快慢指针
解题思路： 需要删除链表中的倒数第 n 个节点，我们需要知道的就是倒数第 n+1 个节点，然后删除删除倒数第 n+1 节点的后继节点即可
步骤：
使用 2 个指针：
fast快指针提前走n+1步slow指针指向当前距离fast倒数第n个节点， 初始为head
然后， fast 、 slow 同步向前走，直到 fast.next 为 null
此时，fast 为最后一个节点，slow 就是倒数第 n+1 个节点，此时问题就变更为删除链表中的 slow 的后继节点
但存在一个问题，当链表长度为 n 时，fast 是前进不到 n+1 个节点位置的，所以此时有两种解决思路：
创建一个头节点 preHead，设置preHead.next = head，这样就可以解决以上问题，删除倒数第n个节点后，返回的preHead.next即可另外一种是， fast快指针提前走n步后，判断fast.next是否为null，即fast是否是最后一个节点，如果是，则head为倒数第n个节点，此时问题可以简化为删除头节点；如果不是，fast = fast.next，fast再前进一步，slow为倒数第n+1个节点，也解决了以上问题。
解决方案一：添加 preHead 节点
var removeNthFromEnd = function(head, n) {
let preHead = new ListNode(0)
preHead.next = head
let fast = preHead, slow = preHead
// 快先走 n+1 步
while(n--) {
fast = fast.next
}
// fast、slow 一起前进
while(fast && fast.next) {
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
return preHead.next
};
解决方案二：单独处理倒数第 n 节点
var removeNthFromEnd = function(head, n) {
let fast = head, slow = head
// 快先走 n 步
while(--n) {
fast = fast.next
}
if(!fast.next) return head.next
fast = fast.next
// fast、slow 一起前进
while(fast && fast.next) {
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
return head
};
时间复杂度：O(n)
空间复杂度：O(1)
leetcode[21]
3. 更多解法请看 leetcode19：删除链表倒数第 n 个结点[22]
五、leetcode876：求链表的中间结点
1. 题目
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
给定链表的结点数介于 1 和 100 之间。
2. 解法：快慢指针
解题思路： 快指针一次走两步，慢指针一次走一步，当快指针走到终点时，慢指针刚好走到中间
var middleNode = function(head) {
let fast = head, slow = head
while(fast && fast.next) {
slow = slow.next
fast = fast.next.next
}
return slow
};
时间复杂度：O(n)
空间复杂度：O(1)
leetcode[23]
3. 更多解法请看 leetcode876：求链表的中间结点[24]
六、图解leetcode206：反转链表
1. 题目
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
2. 答案
解法一：迭代法
解题思路： 将单链表中的每个节点的后继指针指向它的前驱节点即可
画图实现： 画图帮助理解一下
确定边界条件： 当链表为 null 或链表中仅有一个节点时，不需要反转
代码实现：
var reverseList = function(head) {
if(!head || !head.next) return head
var prev = null, curr = head
while(curr) {
// 用于临时存储 curr 后继节点
var next = curr.next
// 反转 curr 的后继指针
curr.next = prev
// 变更prev、curr
// 待反转节点指向下一个节点
prev = curr
curr = next
}
head = prev
return head
};
时间复杂度：O(n)
空间复杂度：O(1)
解法二：尾递归法
解题思路： 从头节点开始，递归反转它的每一个节点，直到 null ，思路和解法一类似
代码实现：
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)
};
时间复杂度：O(n)
空间复杂度：O(n)
解法三：递归法
解题思路： 不断递归反转当前节点 head 的后继节点 next
画图实现： 画图帮助理解一下
代码实现：
var reverseList = function(head) {
if(!head || !head.next) return head
var next = head.next
// 递归反转
var reverseHead = reverseList(next)
// 变更指针
next.next = head
head.next = null
return reverseHead
};
时间复杂度：O(n)
空间复杂度：O(n)
leetcode[25]
3. 更多解法请看 leetcode206：反转链表[26]
七、前端算法集训营第一期免费加入啦
快来加入我们吧，在这里从0到1构建完整的数据结构与算法体系！
在这里，瓶子君不仅介绍算法，还将算法与前端各个领域进行结合，包括浏览器、HTTP、V8、React、Vue源码等。
在这里，你可以每天学习一道大厂算法题（阿里、腾讯、百度、字节等等）或 leetcode，瓶子君都会在第二天解答哟！
因微信公众号不支持外链，点击「阅读原文」，查看整个系列！
