René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"前端进阶算法6：一看就懂的队列及配套算法题","articleBody":"### 引言\r\n\r\n队列这种数据结构，据瓶子君了解，前端需要了解的队列结构主要有：双端队列、滑动窗口，它们都是算法中是比较常用的数据结构。\r\n\r\n因此，本节主要内容为：\r\n\r\n- 数据结构：队列（Queue）\r\n- 双端队列（Deque）\r\n- 双端队列的应用：翻转字符串中的单词\r\n- 滑动窗口\r\n- 滑动窗口应用：无重复字符的最长公共子串\r\n- 最后来一道 leetcode 题目：滑动窗口最大值问题\r\n\r\n下面进入正文吧👇\r\n\r\n### 一、数据结构：队列\r\n\r\n队列和栈类似，不同的是队列是先进先出 (FIFO) 原则的有序集合，它的结构类似如下：\r\n\r\n![](http://resource.muyiy.cn/image/20200314222753.png)\r\n\r\n常见队列的操作有： `enqueue(e)` 进队、 `dequeue()` 出队、 `isEmpty()` 是否是空队、 `front()` 获取队头元素、`clear()` 清空队，以及 `size()` 获取队列长度。\r\n\r\n**代码实现**\r\n\r\n```js\r\nfunction Queue() {\r\n  let items = []\r\n  this.enqueue = function(e) {\r\n    items.push(e)\r\n  }\r\n  this.dequeue = function() {\r\n    return items.shift()\r\n  }\r\n  this.isEmpty = function() {\r\n    return items.length === 0\r\n  }\r\n  this.front = function() {\r\n    return items[0]\r\n  }\r\n  this.clear = function() { \r\n    items = [] \r\n  }\r\n  this.size = function() {\r\n    return items.length\r\n  }\r\n}\r\n```\r\n\r\n**查找：从对头开始查找，从时间复杂度为 O(n)**\r\n\r\n**插入或删除：进栈与出栈的时间复杂度为 O(1)**\r\n\r\n### 二、双端队列（Deque）\r\n\r\n#### 1. 什么是 Deque \r\n\r\nDeque 在原有队列的基础上扩充了：队头、队尾都可以进队出队，它的数据结构如下：\r\n\r\n![](http://resource.muyiy.cn/image/20200426211031.png)\r\n\r\n**代码实现：**\r\n\r\n```js\r\nfunction Deque() {\r\n  let items = []\r\n  this.addFirst = function(e) {\r\n    items.unshift(e)\r\n  }\r\n  this.removeFirst = function() {\r\n    return items.shift()\r\n  }\r\n  this.addLast = function(e) {\r\n    items.push(e)\r\n  }\r\n  this.removeLast = function() {\r\n    return items.pop()\r\n  }\r\n  this.isEmpty = function() {\r\n    return items.length === 0\r\n  }\r\n  this.front = function() {\r\n    return items[0]\r\n  }\r\n  this.clear = function() { \r\n    items = [] \r\n  }\r\n  this.size = function() {\r\n    return items.length\r\n  }\r\n}\r\n```\r\n\r\n下面看一道经典的双端队列问题👇\r\n\r\n#### 2. 字节\u0026leetcode151：翻转字符串里的单词\r\n\r\n给定一个字符串，逐个翻转字符串中的每个单词。\r\n\r\n**示例 1：**\r\n\r\n```\r\n输入: \"the sky is blue\"\r\n输出: \"blue is sky the\"\r\n```\r\n\r\n**示例 2：**\r\n\r\n```\r\n输入: \"  hello world!  \"\r\n输出: \"world! hello\"\r\n解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。\r\n```\r\n\r\n**示例 3：**\r\n\r\n```\r\n输入: \"a good   example\"\r\n输出: \"example good a\"\r\n解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。\r\n```\r\n\r\n**说明：**\r\n\r\n- 无空格字符构成一个单词。\r\n- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。\r\n- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。\r\n\r\n**解题思路：使用双端队列解题**\r\n\r\n- 首先去除字符串左右空格\r\n- 逐个读取字符串中的每个单词，依次放入双端队列的对头\r\n- 再将队列转换成字符串输出（已空格为分隔符）\r\n\r\n**画图理解：**\r\n\r\n![](http://resource.muyiy.cn/image/20200416220950.png)\r\n\r\n![](http://resource.muyiy.cn/image/20200416220841.png)\r\n\r\n![](http://resource.muyiy.cn/image/20200416220859.png)\r\n\r\n**代码实现：**\r\n\r\n```js\r\nvar reverseWords = function(s) {\r\n    let left = 0\r\n    let right = s.length - 1\r\n    let queue = []\r\n    let word = ''\r\n    while (s.charAt(left) === ' ') left ++\r\n    while (s.charAt(right) === ' ') right --\r\n    while (left \u003c= right) {\r\n        let char = s.charAt(left)\r\n        if (char === ' ' \u0026\u0026 word) {\r\n            queue.unshift(word)\r\n            word = ''\r\n        } else if (char !== ' '){\r\n            word += char\r\n        }\r\n        left++\r\n    }\r\n    queue.unshift(word)\r\n    return queue.join(' ')\r\n};\r\n```\r\n\r\n更多解法详见 [图解字节\u0026leetcode151：翻转字符串里的单词](https://github.com/sisterAn/JavaScript-Algorithms/issues/18)\r\n\r\n### 三、滑动窗口\r\n\r\n#### 1. 什么是滑动窗口\r\n\r\n这是队列的另一个重要应用\r\n\r\n顾名思义，滑动窗口就是一个运行在一个大数组上的子列表，该数组是一个底层元素集合。\r\n\r\n假设有数组 [a b c d e f g h ]，一个大小为 3 的 **滑动窗口**在其上滑动，则有：\r\n\r\n```js\r\n[a b c]\r\n  [b c d]\r\n    [c d e]\r\n      [d e f]\r\n        [e f g]\r\n          [f g h]\r\n```\r\n\r\n一般情况下就是使用这个窗口在数组的 **合法区间** 内进行滑动，同时 **动态地** 记录一些有用的数据，很多情况下，能够极大地提高算法地效率。\r\n\r\n下面看一道经典的滑动窗口问题👇\r\n\r\n#### 2. 字节\u0026Leetcode3：无重复字符的最长子串\r\n\r\n给定一个字符串，请你找出其中不含有重复字符的 **最长子串** 的长度。\r\n\r\n**示例 1:**\r\n\r\n```js\r\n输入: \"abcabcbb\"\r\n输出: 3 \r\n解释: 因为无重复字符的最长子串是 \"abc\"，所以其长度为 3。\r\n```\r\n\r\n**示例 2:**\r\n\r\n```js\r\n输入: \"bbbbb\"\r\n输出: 1\r\n解释: 因为无重复字符的最长子串是 \"b\"，所以其长度为 1。\r\n```\r\n\r\n**示例 3:**\r\n\r\n```js\r\n输入: \"pwwkew\"\r\n输出: 3\r\n解释: 因为无重复字符的最长子串是 \"wke\"，所以其长度为 3。\r\n     请注意，你的答案必须是 子串 的长度，\"pwke\" 是一个子序列，不是子串。\r\n```\r\n\r\n**解题思路：** 使用一个数组来维护滑动窗口\r\n\r\n遍历字符串，判断字符是否在滑动窗口数组里\r\n\r\n- 不在则 `push` 进数组\r\n- 在则删除滑动窗口数组里相同字符及相同字符前的字符，然后将当前字符 `push` 进数组\r\n- 然后将 `max` 更新为当前最长子串的长度\r\n\r\n遍历完，返回 `max` 即可\r\n\r\n**画图帮助理解一下：**\r\n\r\n![](http://resource.muyiy.cn/image/20200425111427.png)\r\n\r\n**代码实现：**\r\n\r\n```js\r\nvar lengthOfLongestSubstring = function(s) {\r\n    let arr = [], max = 0\r\n    for(let i = 0; i \u003c s.length; i++) {\r\n        let index = arr.indexOf(s[i])\r\n        if(index !== -1) {\r\n            arr.splice(0, index+1);\r\n        }\r\n        arr.push(s.charAt(i))\r\n        max = Math.max(arr.length, max) \r\n    }\r\n    return max\r\n};\r\n```\r\n\r\n**时间复杂度：O(n\u003csup\u003e2\u003c/sup\u003e)， 其中 `arr.indexOf()` 时间复杂度为 O(n) ，`arr.splice(0, index+1)` 的时间复杂度也为 O(n)**\r\n\r\n**空间复杂度：O(n)**\r\n\r\n更多解法详见 [字节\u0026Leetcode3：无重复字符的最长子串](https://github.com/sisterAn/JavaScript-Algorithms/issues/21)\r\n\r\n最后，来尝试一道leetcode题目吧！\r\n\r\n### 四、leetcode239：滑动窗口最大值问题\r\n\r\n给定一个数组 `nums` 和滑动窗口的大小 `k`，请找出所有滑动窗口里的最大值。\r\n\r\n**示例:**\r\n\r\n```js\r\n输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3\r\n输出: [3,3,5,5,6,7] \r\n```\r\n\r\n**解释:** \r\n\r\n\u003e 滑动窗口的位置                最大值\r\n\u003e\r\n\u003e [1  3  -1] -3  5  3  6  7       3\r\n\u003e  1 [3  -1  -3] 5  3  6  7       3\r\n\u003e  1  3 [-1  -3  5] 3  6  7       5\r\n\u003e  1  3  -1 [-3  5  3] 6  7       5\r\n\u003e  1  3  -1  -3 [5  3  6] 7       6\r\n\u003e  1  3  -1  -3  5 [3  6  7]      7\r\n\r\n\r\n**提示：**\r\n\r\n你可以假设 `k` 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。\r\n\r\n可以自己尝试解答一下，欢迎将答案提交到 https://github.com/sisterAn/JavaScript-Algorithms/issues/33 ，瓶子君将明日解答😊\r\n\r\n### 五、前端算法集训营第一期免费加入啦\r\n\r\n欢迎关注「前端瓶子君」，回复「算法」自动加入，从0到1构建完整的数据结构与算法体系！\r\n\r\n在这里，瓶子君不仅介绍算法，还将算法与前端各个领域进行结合，包括浏览器、HTTP、V8、React、Vue源码等。\r\n\r\n在这里，你可以每天学习一道大厂算法题（阿里、腾讯、百度、字节等等）或 leetcode，瓶子君都会在第二天解答哟！\r\n\r\n![](http://resource.muyiy.cn/image/20200424231501.png)\r\n","author":{"url":"https://github.com/sisterAn","@type":"Person","name":"sisterAn"},"datePublished":"2020-05-07T15:51:38.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/35/JavaScript-Algorithms/issues/35"}