数组和字符串
数组
高频例题
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案
解析：
哈希表
注意到暴力枚举的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从O(N) 降低到 O(1)。
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
/*** @param {number[]} nums* @param {number} target* @return {number[]}*/var twoSum = function(nums, target) {let map = new Map();for(let i = 0; i < nums.length; i++) {if (map.has(target-nums[i])) {return [i, map.get(target-nums[i])]}map.set(nums[i],i);}return []};
三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
解析：排序 + 双指针
算法流程：
- 特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。
- 对数组进行排序。
- 遍历排序后数组：
若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
对于重复元素：跳过，避免出现重复解
令左指针L=i+1，右指针 R=n−1，当 L
若和大于 0，说明 nums[R] 太大，R 左移
若和小于 0，说明nums[L] 太小，L 右移
var threeSum = function(nums) {let res= [];const let = nums.length;// 对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []if(nums === null || len < 3) return res;nums.sort((a,b) => a - b); // 排序for (let i = 0; i < len; i++) {// 如果当前数字大于0，则三数之和一定大于0，所以结束循环if(nums[i] > 0) breakif(i > 0 && nums[i] === nums[i-1]) continue; // 去重// 双指针let l = i+1;let r = len-1;while(l < r) {const sum = nums[i] + nums[l] + nums[r];if(sum === 0) {res.push([nums[i],nums[l],nums[r]])while(l < r && nums[l] === nums[l+1]) l++; // 去重while(l < r && nums[r] === nums[r-1]) r--; // 去重l++;r--;}else if (sum < 0) l++;else if (sum > 0) r--;}}return res}
合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
解析：
方法一：直接合并后排序
最直观的方法是先将数组 nums2放进数组 nums1的尾部，然后直接对整个数组进行排序。
var merge = function(nums1, m, nums2, n) {nums1.splice(m, nums1.length - m, ...nums2);nums1.sort((a, b) => a - b);};
方法二：双指针
方法一没有利用数组 nums1与nums2已经被排序的性质。为了利用这一性质，我们可以使用双指针方法。这一方法将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。如下面的动画所示：
var merge = function(nums1, m, nums2, n) {let l1 = 0, l2 = 0, arr = [];while(l1 < m || l2 < n) {if(l2 === n) arr.push(nums1[l1++]);else if(l1 === m) arr.push(nums2[l2++]);else {if(nums1[l1] <= nums2[l2]) arr.push(nums1[l1++])else arr.push(nums2[l2++])}}for(let i = 0; i < m+n; i++) {nums1[i] = arr[i]}};
螺旋矩阵 II
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
解析：
var generateMatrix = function(n) {let num = 1;const matrix = new Array(n).fill(0).map(() => new Array(n).fill(0));let left = 0, right = n - 1, top = 0, bottom = n - 1;while (left <= right && top <= bottom) {for (let column = left; column <= right; column++) {matrix[top][column] = num;num++;}for (let row = top + 1; row <= bottom; row++) {matrix[row][right] = num;num++;}if (left < right && top < bottom) {for (let column = right - 1; column > left; column--) {matrix[bottom][column] = num;num++;}for (let row = bottom; row > top; row--) {matrix[row][left] = num;num++;}}left++;right--;top++;bottom--;}return matrix;};
知识点快照
数组的操作
本节我们重点来讲解一下数组的 4 种操作。
读取元素
读取数组中的元素，是通过访问索引的方式来读取的，索引一般从 0 开始。
在计算机中，内存可以看成一些已经排列好的格子，每个格子对应一个内存地址。一般情况下，数据会分散地存储在不同的格子中。
而对于数组，计算机会在内存中为其申请一段 连续 的空间，并且会记下索引为 0 处的内存地址。以数组 [“C”, “O”, “D”, “E”, “R”] 为例，它的各元素对应的索引及内存地址如下图所示。
假如我们想要访问索引为 2 处的元素 “D” 时，计算机会进行以下计算：
- 找到该数组的索引 0 的内存地址： 2008；
- 将内存地址加上索引值，作为目标元素的地址，即 2008 + 2 = 2010，对应的元素为 “D”，这时便找到了目标元素。
我们知道，计算内存地址这个过程是很快的，而我们一旦知道了内存地址就可以立即访问到该元素，因此它的时间复杂度是常数级别，为 O(1)。
查找元素
假如我们对数组中包含哪些元素并不了解，只是想知道其中是否含有元素 “E”，数组会如何查找元素 “E” 呢？
与读取元素类似，由于我们只保存了索引为 0 处的内存地址，因此在查找元素时，只需从数组开头逐步向后查找就可以了。如果数组中的某个元素为目标元素，则停止查找；否则继续搜索直到到达数组的末尾。
我们发现，最坏情况下，搜索的元素为 “R”，或者数组中不包含目标元素时，我们需要查找 n 次，n 为数组的长度，因此查找元素的时间复杂度为 O(N)，N。
插入元素
假如我们想在原有的数组中再插入一个元素 “S” 呢？
如果要将该元素插入到数组的末尾，只需要一步。即计算机通过数组的长度和位置计算出即将插入元素的内存地址，然后将该元素插入到指定位置即可。
然而，如果要将该元素插入到数组中的其他位置，则会有所区别，这时我们首先需要为该元素所要插入的位置 腾出 空间，然后进行插入操作。比如，我们想要在索引 2 处插入 “S”。
我们发现，如果需要频繁地对数组元素进行插入操作，会造成时间的浪费。事实上，另一种数据结构，即链表可以有效解决这个问题，我们将在另外的卡片中进行学习。
删除元素
删除元素与插入元素的操作类似，当我们删除掉数组中的某个元素后，数组中会留下 空缺 的位置，而数组中的元素在内存中是连续的，这就使得后面的元素需对该位置进行 填补 操作。
以删除索引 1 中的元素 “O” 为例，具体过程如图所示。
当数组的长度为 n 时，最坏情况下，我们删除第一个元素，共需要的步骤数为 1 + (n - 1) = n 步，其中，1 为删除操作，n - 1 为移动其余元素的步骤数。删除操作具有线性时间复杂度，即时间复杂度为 O(N)，N 为数组的长度。
二维数组简介
二维数组是一种结构较为特殊的数组，只是将数组中的每个元素变成了一维数组。
所以二维数组的本质上仍然是一个一维数组，内部的一维数组仍然从索引 0 开始，我们可以将它看作一个矩阵，并处理矩阵的相关问题。
示例
类似一维数组，对于一个二维数组 A = [[1, 2, 3, 4],[2, 4, 5, 6],[1, 4, 6, 8]]，计算机同样会在内存中申请一段 连续 的空间，并记录第一行数组的索引位置，即 A[0][0] 的内存地址，它的索引与内存地址的关系如下图所示。
注意，实际数组中的元素由于类型的不同会占用不同的字节数，因此每个方格地址之间的差值可能不为 1。
实际题目中，往往使用二维数组处理矩阵类相关问题，包括矩阵旋转、对角线遍历，以及对子矩阵的操作等。
字符串
高频例题
有效的括号
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
解析：栈的思想，弹出匹配。
var isValid = function(s) {if (s.length <= 1) return falselet arr = []for(let i = 0; i < s.length; i++) {if(s[i] === '(' || s[i] === '[' || s[i] === '{') {arr.push(s[i])} else if(s[i] === ')') {if(arr.pop() === '(') continue;else {return false}} else if(s[i] === ']') {if(arr.pop() === '[') continue;else {return false}} else if(s[i] === '}') {if(arr.pop() === '{') continue;else {return false}}}if(arr.length === 0) return trueelse {return false}};
字符串相加
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
解析：
双指针：
- 创建指针 i 指向 nums1 末位数字，j 指向 nums2 末位数字。
- i, j 数字相加，用进位就用 carry 来记录进位值，无则为 0。
- 若产生进位，则当前数字为(i+j)%10 的值。
若遍历过程中，nums1 或 nums2 当前已无数字，则用 0 补位来计算。
var addStrings = function(num1,num2) {let i = num1.length - 1, j = num2.length - 1, carry = 0, ans = [];while(i >= 0 || j >= 0 || carry !== 0) { // 最后ij都为0的情况如果产生进位也要加1let c1 = i >= 0 ? num1.charAt(i) - 0 : 0, //减0来转换成数字c2 = j >= 0 ? num2.charAt(j) - 0 : 0;let sum = c1 + c2 + carry;ans.push(sum % 10); // 除10取余carry = Math.floor(sum / 10);i--;j--;}return ans.reverse().join('');}
最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
输入：s = “babad” 输出：“bab”
动态规划
思路：定义dp[i][j]表示子串i～j是否是回文子串，循环s的子串，看是否满足s[i]，s[j]相等，如果相等，则dp[i][j]是否为回文串取决于dp[i+1][j-1]是否也是回文子串，在循环的过程中不断更新最大回文子串的长度，注意子串的长度是0或1也算回文子串
复杂度：时间复杂度O(n^2)，两层循环。空间复杂度O(n^2)，即动态规划dp数组的空间。var longestPalindrome = function(s) {let n = s.length;let res = '';let dp = Array.from(new Array(n),() => new Array(n).fill(false));//初始化数组for(let i = n-1;i >= 0;i--){//循环字符串for(let j = i;j < n;j++){//dp[i][j]表示子串i～j是否是回文子串//回文子串必须满足s[i]，s[j]相等。并且向外扩展一个字符也相等，即dp[i+1][j-1]也是回文子串//j - i < 2表示子串小于等于1也是回文串dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i+1][j-1]);if(dp[i][j] && j - i +1 > res.length){//当前回文子串比之前的大，更新最大长度res = s.substring(i,j+1);}}}return res;};
双指针：
var longestPalindrome = function(s) {let max = ''for(let i=0; i< s.length; i++) {// 分奇偶， 一次遍历，每个字符位置都可能存在奇数或偶数回文helper(i, i)helper(i, i+1)}function helper(l, r) {// 定义左右双指针while(l>=0 && r< s.length && s[l] === s[r]) {l--r++}// 拿到回文字符， 注意 上面while满足条件后多执行了一次，所以需要l+1, r+1-1const maxStr = s.slice(l + 1, r + 1 - 1);// 取最大长度的回文字符if (maxStr.length > max.length) max = maxStr}return max};
知识点快照
字符串简介
维基百科：字符串是由零个或多个字符组成的有限序列。一般记为 s = a1a2…an。它是编程语言中表示文本的数据类型。
为何单独讨论字符串类型
我们知道，字符串与数组有很多相似之处，比如使用 名称[下标] 来得到一个字符。那么我们为什么要单独讨论字符串呢？原因主要有：字符串的基本操作对象通常是字符串整体或者其子串
例如有这样一个字符串序列：I like leetcode 现在你想把这句话反向输出，可能会变成这样：
edocteel ekil I
这是我们想要的结果吗？你可能会回答不是，因为它没有任何意义。我们通常希望单词仍然维持原来的顺序，这样反向输出之后就是：
Leetcode like I
这样的结果对于我们来讲是不是更满意呢？维持单词本身的顺序使得我们方便进行更多操作，这里的每个单词就叫做字符串的「子串」，通常，我们的操作对象更多情况下是这些子串。
- 字符串操作比其他数据类型更复杂（例如比较、连接操作）
对于不同的编程语言，字符串的某些操作会有所不同。下面我们将从字符串的「比较」和「连接」操作两个方面分别进行讲解。
比较函数
字符串有它自己的比较函数（我们将在下面的代码中向你展示比较函数的用法）。
然而，存在这样一个问题：
我们可以用 “==” 来比较两个字符串吗？
这取决于下面这个问题的答案：
我们使用的语言是否支持运算符重载？
如果答案是 yes （例如 C++、Python）。我们可以使用 == 来比较两个字符串；
如果答案是 no （例如 Java），我们可能无法使用 == 来比较两个字符串。当我们使用 == 时，它实际上会比较这两个对象是否是同一个对象。
连接操作
对于不同的编程语言中，字符串可能是可变的，也可能是不可变的。不可变意味着一旦字符串被初始化，你就无法改变它的内容。
在某些语言（如 C ++）中，字符串是可变的。 也就是说，你可以像在数组中那样修改字符串。
在其他一些语言（如 Java、Python）中，字符串是不可变的。
在 字符串不可变 的语言中，进行字符串的连接操作则会带来一些问题。
显然，不可变字符串无法被修改。哪怕你只是想修改其中的一个字符，也必须创建一个新的字符串。
我们发现在 C++ 中，进行字符串连接并没有明显的性能影响。
然而，对于 Java来说，由于字符串是不可变的，因此在连接时首先为新字符串分配足够的空间，复制旧字符串中的内容并附加到新字符串。
针对 Java 中出现的此问题，我们提供了以下解决方案：
如果你确实希望你的字符串是可变的，则可以使用 toCharArray 将其转换为字符数组。
如果你经常必须连接字符串，最好使用一些其他的数据结构，如 StringBuilder 。
链表
单链表
高频例题
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
var mergeTwoLists = function(l1, l2) {const prehead = new ListNode(-1);let prev = prehead;while (l1 != null && l2 != null) {if (l1.val <= l2.val) {prev.next = l1;l1 = l1.next;} else {prev.next = l2;l2 = l2.next;}prev = prev.next;}// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可prev.next = l1 === null ? l2 : l1;return prehead.next;};
反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
var reverseList = function(head) {let pre = null, cur = head, next = head;while(cur) {next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre};
两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
思路
标签：链表
将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 00，比如 987 + 23 = 987 + 023 = 1010
每一位计算的同时需要考虑上一位的进位问题，而当前位计算结束后同样需要更新进位值
如果两个链表全部遍历完毕后，进位值为 1，则在新链表最前方添加节点 1
小技巧：对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。
var addTwoNumbers = function(l1, l2) {let pre = new ListNode(0);let cur = pre;let carry = 0;while(l1 != null || l2 != null) {let x = l1 == null ? 0 : l1.val;let y = l2 == null ? 0 : l2.val;let sum = x + y + carry;carry = Math.floor(sum / 10);sum = sum % 10;cur.next = new ListNode(sum);cur = cur.next;if(l1 != null)l1 = l1.next;if(l2 != null)l2 = l2.next;}if(carry == 1) {cur.next = new ListNode(carry);}return pre.next;};
重排链表
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
寻找链表中点 + 链表逆序 + 合并链表
注意到目标链表即为将原链表的左半端和反转后的右半端合并后的结果。
这样我们的任务即可划分为三步：
- 找到原链表的中点（参考「876. 链表的中间结点」）。
我们可以使用快慢指针来 O(N)O(N) 地找到链表的中间节点。
- 将原链表的右半端反转（参考「206. 反转链表」）。
我们可以使用迭代法实现链表的反转。
- 将原链表的两端合并。
因为两链表长度相差不超过 1，因此直接合并即可。
var reverse = function(head) {let cur = head, pre = null, next = headwhile(cur) {next = cur.nextcur.next = prepre = curcur = next}return pre}var reorderList = function(head) {let slow = head, fast = head, cur = head;while(fast !== null && fast.next !== null) {slow = slow.nextfast = fast.next.next}let rightList = slow.nextslow.next = nulllet l2 = reverse(rightList)let l1 = curwhile(l1 && l2) {let next1 = l1.next, next2 = l2.nextl1.next = l2l1 = next1l2.next = next1l2 = next2}return cur};
知识点快照
单链表简介
单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。
下面是一个单链表的例子：
蓝色箭头显示单个链接列表中的结点是如何组合在一起的。
在大多数情况下，我们将使用头结点(第一个结点)来表示整个列表。
操作
与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度。
例如，在上面的示例中，头结点是 23。访问第 3 个结点的唯一方法是使用头结点中的“next”字段到达第 2 个结点（结点 6）; 然后使用结点 6 的“next”字段，我们能够访问第 3 个结点。
你可能想知道为什么链表很有用，尽管它在通过索引访问数据时（与数组相比）具有如此糟糕的性能。 在接下来的两篇文章中，我们将介绍插入和删除操作，你将了解到链表的好处。
单链表 - 添加操作
如果我们想在给定的结点 prev 之后添加新值，我们应该：
- 使用给定值初始化新结点 cur；
- 将 cur 的 next 字段链接到 prev 的下一个结点 next ；
- 将 prev 中的 next 字段链接到 cur 。
与数组不同，我们不需要将所有元素移动到插入元素之后。因此，您可以在 O(1) 时间复杂度中将新结点插入到链表中，这非常高效。
在开头添加结点
众所周知，我们使用头结点来代表整个列表。
因此，在列表开头添加新节点时更新头结点 head 至关重要。
- 初始化一个新结点 cur ；
- 将新结点链接到我们的原始头结点 head。
- 将 cur 指定为 head 。
例如，让我们在列表的开头添加一个新结点 9 。
- 我们初始化一个新结点 9 并将其链接到当前头结点 23 。
- 指定结点 9 为新的头结点。
单链表 - 删除操作
如果我们想从单链表中删除现有结点 cur，可以分两步完成：
- 找到 cur 的上一个结点 prev 及其下一个结点 next ；
- 接下来链接 prev 到 cur 的下一个节点 next 。
在我们的第一步中，我们需要找出 prev 和 next。使用 cur 的参考字段很容易找出 next，但是，我们必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除结点的时间复杂度将是 O(N)。
空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。
示例
让我们尝试把结点 6从上面的单链表中删除。
1. 从头遍历链表，直到我们找到前一个结点 prev，即结点 23
2. 将 prev（结点 23）与 next（结点 15）链接
结点 6 现在不在我们的单链表中。
双链表
高频例题
LRU缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
哈希表 + 双向链表
LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。
这样一来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：
- 对于 get 操作，首先判断 key 是否存在：
- 如果 key 不存在，则返回−1；
- 如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
- 对于 put 操作，首先判断 key 是否存在：
- 如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
- 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。
上述各项操作中，访问哈希表的时间复杂度为 O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O(1) 时间内完成。
小贴士
在双向链表的实现中，使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。
class ListNode {constructor(key, value, next, prev) {this.key = key || ''this.value = value || ''this.next = next || nullthis.prev = prev || null}}const LRUCache = function (capacity) {this.map = new Map()this.capacity = capacitythis.dummyHead = new ListNode()this.dummyTrail = new ListNode()this.dummyHead.next = this.dummyTrailthis.dummyTrail.prev = this.dummyHead}LRUCache.prototype.addToHead = function (node) {node.prev = this.dummyHeadnode.next = this.dummyHead.nextthis.dummyHead.next.prev = nodethis.dummyHead.next = node}LRUCache.prototype.moveToHead = function (node) {this.removeNodeFromList(node)this.addToHead(node)}LRUCache.prototype.removeNodeFromList = function (node) {let tempPrev = node.prevlet tempNext = node.nexttempPrev.next = tempNexttempNext.prev = tempPrev}LRUCache.prototype.removeLRUItem = function () {let trail = this.popTail()this.map.delete(trail.key)}LRUCache.prototype.popTail = function () {let tailItem = this.dummyTrail.prevthis.removeNodeFromList(tailItem)return tailItem}LRUCache.prototype.get = function (key) {if(this.map.has(key)){let node = this.map.get(key)this.moveToHead(node)return node.value}return -1}LRUCache.prototype.put = function (key, value) {if(this.map.has(key)) {const node = this.map.get(key);node.value = value;this.moveToHead(node)} else {let newNode = new ListNode(key,value);this.addToHead(newNode)this.map.set(key,newNode)if(this.map.size > this.capacity){this.removeLRUItem()}}}
知识点快照
双链表简介
定义
双链表以类似的方式工作，但还有一个引用字段，称为“prev”字段。有了这个额外的字段，您就能够知道当前结点的前一个结点。
让我们看一个例子：
绿色箭头表示我们的“prev”字段是如何工作的。
操作
与单链表类似，我们将介绍在双链表中如何访问数据、插入新结点或删除现有结点。
我们可以与单链表相同的方式访问数据：
- 我们不能在常量级的时间内访问随机位置。
- 我们必须从头部遍历才能得到我们想要的第一个结点。
- 在最坏的情况下，时间复杂度将是 O(N)，其中 N 是链表的长度。
对于添加和删除，会稍微复杂一些，因为我们还需要处理“prev”字段。在接下来的两篇文章中，我们将介绍这两个操作。
添加操作
如果我们想在现有的结点 prev 之后插入一个新的结点 cur，我们可以将此过程分为两个步骤：
- 链接 cur 与 prev 和 next，其中 next 是 prev 原始的下一个节点；
- 用 cur 重新链接 prev 和 next。
删除操作
如果我们想从双链表中删除一个现有的结点 cur，我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。
与单链表不同，使用“prev”字段可以很容易地在常量时间内获得前一个结点。
因为我们不再需要遍历链表来获取前一个结点，所以时间和空间复杂度都是O(1)。
滑动窗口与双指针
高频例题
移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
解析：
由于题目要求删除数组中等于val 的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上。可以使用双指针：右指针 right 指向当前将要处理的元素，左指针left 指向下一个将要赋值的位置。
如果右指针指向的元素不等于val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；
如果右指针指向的元素等于 val，它不能在输出数组里，此时左指针不动，右指针右移一位。
整个过程保持不变的性质是：区间 [0,left) 中的元素都不等于val。当左右指针遍历完输入数组以后，left 的值就是输出数组的长度。
这样的算法在最坏情况下（输入数组中没有元素等于val），左右指针各遍历了数组一次。
var removeElement = function(nums, val) {const n = nums.length;let left = 0;for (let right = 0; right < n; right++) {if (nums[right] !== val) {nums[left] = nums[right];left++;}}return left;};
有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
const sortedSquares = function (nums) {let res = []for (let i = 0, j = nums.length - 1; i <= j;) {if (nums[j] * nums[j] > nums[i] * nums[i]) {res.unshift(nums[j] * nums[j])j--} else {res.unshift(nums[i] * nums[i])i++}}return res}
长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
function minSubArrayLen(target: number, nums: number[]): number {let left: number = 0, right: number = 0;let res: number = nums.length + 1;let sum: number = 0;while (right < nums.length) {sum += nums[right];if (sum >= target) {// 不断移动左指针，直到不能再缩小为止while (sum - nums[left] >= target) {sum -= nums[left++];}res = Math.min(res, right - left + 1);}right++;}return res === nums.length + 1 ? 0 : res;};
反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
var reverseString = function(s) {const n = s.length;for (let left = 0, right = n - 1; left < right; left++, right--) {[s[left], s[right]] = [s[right], s[left]];}};
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
var lengthOfLongestSubstring = function(s) {let left = 0;let long = 0;const map = new Map(), len = s.length;for(let right = 0; right < len; right++){// 遇到重复字符时还要判定 该重复字符的上一次出现位置是否在 滑动窗口左边界 left 的右边if(map.has(s[right]) && map.get(s[right]) >= left){left = map.get(s[right]) + 1; // 都满足，则更新，更新到最近出现的那个重复字符，它的上一个索引的右边}long = Math.max(long, right - left + 1); // 比较滑动窗口大小与 long 的长度map.set(s[right], right); // 无论有没有重复，每次遍历都要更新字符的出现位置}return long;};
字符串的排列
方法一：滑动窗口
由于排列不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列。
根据这一性质，记 s1的长度为n，我们可以遍历 s2中的每个长度为 n 的子串，判断子串和 s1中每个字符的个数是否相等，若相等则说明该子串是 s1的一个排列。
使用两个数组 cnt1和 cnt2， cnt1统计s1中各个字符的个数，cnt2统计当前遍历的子串中各个字符的个数。
由于需要遍历的子串长度均为 n，我们可以使用一个固定长度为 n 的滑动窗口来维护 cnt2：滑动窗口每向右滑动一次，就多统计一次进入窗口的字符，少统计一次离开窗口的字符。然后，判断cnt1 是否与 cnt2相等，若相等则意味着s1的排列之一是s2的子串。
/*** @param {string} s1* @param {string} s2* @return {boolean}*/var checkInclusion = function(s1, s2) {// 自定义方法，用于比较滑动窗口中的数据与目标数据是否相同function equal(a,b){// equal方法的比较思路：a和b 都是两个长度为26 的数组，数组当中的每个数据都对应着一个字符的数量// 例如a[0] 就代表着a 字符串当中字符'a' 的数量，a[1]就代表着字符串当中字符'b'的数量// 因此，只有在a,b 两个数组的每一个值都相等才能说明a,b 代表的字符串内的各个字符的数量相等，也只有在这种情况下equal 函数会返回true ，否则都会返回falsefor(let i =0;i<a.length;i++){if(a[i]!==b[i])return false}return true}let arrP=new Array(26).fill(0),arr=new Array(26).fill(0),len1 = s1.length,len2=s2.length// 将目标数据放入数组，之后使用该数组与滑动窗口进行对比for(let i =0;i<len1;i++) arrP[s1.charCodeAt(i)-'a'.charCodeAt()]++// 遍历整个长字符串，在字符串内部使用滑动窗口逐一访问判断for(let i =0;i<len2;i++){// 创建滑动窗口数组，滑动窗口数组的长度应与目标数组相同arr[s2.charCodeAt(i)-'a'.charCodeAt()]++// 滑动窗口创建完成之前不进行任何操作，长度不同不可能与目标数组相符if(i>=len1-1) {// 滑动窗口创建完毕之后即刻开始与目标窗口进行比对，比对一致即返回trueif(equal(arr,arrP)) return trueelse{// 比对不一致，则滑动窗口向右滑动，最左边字符退出窗口，进入下一次循坏，在下一次循环中又会将窗口外右边的第一个字符放入窗口arr[s2.charCodeAt(i-len1+1)-'a'.charCodeAt()]--}}}// 比对完成都没有发现匹配数据，则说明无匹配数据，返回falsereturn false};
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
var hasCycle = function(head) {let slow = head, fast = head;while(fast !==null && fast.next !== null) {slow = slow.nextfast = fast.next.nextif(fast == slow) return true}return false};
环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
var detectCycle = function(head) {const visited = new Set();while (head !== null) {if (visited.has(head)) {return head;}visited.add(head);head = head.next;}return null;};
链表的中间结点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
var middleNode = function(head) {let slow = head, fast = head;while(fast && fast.next) {slow = slow.nextfast = fast.next.next}return slow};
删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
采取双重遍历肯定是可以解决问题的，但题目要求我们一次遍历解决问题，那我们的思路得发散一下。
我们可以设想假设设定了双指针 p 和 q 的话，当 q 指向末尾的 NULL，p 与 q 之间相隔的元素个数为 n 时，那么删除掉 p 的下一个指针就完成了要求。
设置虚拟节点 dummyHead 指向 head
设定双指针 p 和 q，初始都指向虚拟节点 dummyHead
移动 q，直到 p 与 q 之间相隔的元素个数为 n
同时移动 p 与 q，直到 q 指向的为 NULL
将 p 的下一个节点指向下下个节点
// 版本一（快慢指针法）：function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {let newHead: ListNode | null = new ListNode(0, head);let slowNode: ListNode | null = newHead,fastNode: ListNode | null = newHead;for (let i = 0; i < n; i++) {fastNode = fastNode.next;}while (fastNode.next) {fastNode = fastNode.next;slowNode = slowNode.next;}slowNode.next = slowNode.next.next;return newHead.next;};// 版本二（计算节点总数法）：function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {let curNode: ListNode | null = head;let listSize: number = 0;while (curNode) {curNode = curNode.next;listSize++;}if (listSize === n) {head = head.next;} else {curNode = head;for (let i = 0; i < listSize - n - 1; i++) {curNode = curNode.next;}curNode.next = curNode.next.next;}return head;};
知识点快照
应用场景一
通常，我们只需要一个指针进行迭代，即从数组中的第一个元素开始，最后一个元素结束。然而，有时我们会使用两个指针进行迭代。
示例
让我们从一个经典问题开始：
反转数组中的元素。比如数组为 [‘l’, ‘e’, ‘e’, ‘t’, ‘c’, ‘o’, ‘d’, ‘e’]，反转之后变为 [‘e’, ‘d’, ‘o’, ‘c’, ‘t’, ‘e’, ‘e’, ‘l’]。
使用双指针技巧，其思想是分别将两个指针分别指向数组的开头及末尾，然后将其指向的元素进行交换，再将指针向中间移动一步，继续交换，直到这两个指针相遇。
小结
我们来总结一下，使用双指针的典型场景之一是你想要
从两端向中间迭代数组。
这时你可以使用双指针技巧：
一个指针从头部开始，而另一个指针从尾部开始。
这种技巧经常在排序数组中使用。
应用场景二
有时，我们可以使用两个不同步的指针来解决问题，即快慢指针。与情景一不同的是，两个指针的运动方向是相同的，而非相反。
示例
让我们从一个经典问题开始：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
如果我们没有空间复杂度上的限制，那就更容易了。我们可以初始化一个新的数组来存储答案。如果元素不等于给定的目标值，则迭代原始数组并将元素添加到新的数组中。
实际上，它相当于使用了两个指针，一个用于原始数组的迭代，另一个总是指向新数组的最后一个位置。
考虑空间限制
如果我们不使用额外的数组，只是在原数组上进行操作呢？
此时，我们就可以采用快慢指针的思想：初始化一个快指针 fast 和一个慢指针 slow，fast 每次移动一步，而 slow 只当 fast 指向的值不等于 val 时才移动一步。
小结
这是你需要使用双指针技巧的另一种非常常见的情况：
同时有一个慢指针和一个快指针。
解决这类问题的关键是:
确定两个指针的移动策略。
与前一个场景类似，你有时可能需要在使用双指针技巧之前对数组进行排序，也可能需要运用贪心法则来决定你的运动策略。
哈希表
高频例题
有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
t 是 s 的异位词等价于「两个字符串中字符出现的种类和次数均相等」。由于字符串只包含 26 个小写字母，因此我们可以维护一个长度为 26 的频次数组 table，s中出现的字母就加一，t中出现的字母就减一，最后遍历数组每一项是否为零。
function isAnagram(s: string, t: string): boolean {if (s.length !== t.length) return false;let helperArr: number[] = new Array(26).fill(0);let pivot: number = 'a'.charCodeAt(0);for (let i = 0, length = s.length; i < length; i++) {helperArr[s.charCodeAt(i) - pivot]++;helperArr[t.charCodeAt(i) - pivot]--;}return helperArr.every(i => i === 0);};
存在重复元素
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
function containsDuplicate(nums: number[]): boolean {let map = new Map()// nums.forEach((item) => {// if(map.has(item)) {// return true 返回也没用，forEach没有返回值// }// map.set(item, 1)// })for(let i = 0; i < nums.length; i++) {if(map.has(nums[i])) return truemap.set(nums[i],1)}return false};
两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
function intersection(nums1: number[], nums2: number[]): number[] {let res = [], map = new Map()nums1.forEach((item) => {map.set(item,1)})nums2.forEach((item) => {if(map.has(item)) {res.push(item)}})return [...new Set(res)]};
四数相加 II
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
var fourSumCount = function(nums1, nums2, nums3, nums4) {let map = {}, len = nums1.length, result = 0, sum;// 遍历前面两个数组，求和并存储到map中，和相等则map[sum]的值+1for(let i = 0; i < len; i++) {for(let j = 0; j<len;j++) {sum = nums1[i]+nums2[j]map[sum] = map[sum] ? map[sum] + 1 : 1}}// 遍历后两个数组，如果要满足四数和为0，后两个数组的和一定跟前两数组的和数值相反for(let i = 0; i < len; i++) {for(let j = 0; j < len;j++) {sum = 0 - (nums3[i] + nums4[j])if(map[sum]) {result += map[sum]}}}return result};
知识点快照
哈希表简介
哈希表（又称散列表）的原理为：借助 哈希函数，将键映射到存储桶地址。更确切地说，
- 首先开辟一定长度的，具有连续物理地址的桶数组；
- 当我们插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；
- 当我们想要搜索一个键时，哈希表将使用哈希函数来找到对应的桶，并在该桶中进行搜索。
在示例中，我们使用 y = x ％ 5 作为哈希函数，来完成插入和搜索策略。
插入：我们通过哈希函数解析键，将它们映射到相应的桶中。
例如，根据哈希函数，1987 将分配给桶 2，而 24 分配给桶 4。
搜索：我们通过哈希函数解析键，得到桶地址，然后在该存储桶中搜索。
如果我们搜索 1987，我们将使用哈希函数将 1987 映射到 2。因此我们在桶 2 中搜索，我们在那个桶中成功找到了 1987。
例如，如果我们搜索 23，将映射 23 到 3，并在桶 3 中搜索。我们发现 23 不在桶 3 中，这意味着 23 不在哈希表中。
注意到键 1987 和 2 被映射到了同一个桶中，我们称之为 哈希冲突，哈希冲突与哈希函数有关，但又难以避免。有关处理哈希冲突的办法，我们将在下一节详细介绍。
负载因子
负载因子 又叫装填因子，是哈希表的一个重要参数，它反映了哈希表的装满程度。
在上面的例子中，我们发现有的桶处于空闲状态，而有的桶产生了哈希冲突，如何解决这个问题呢？
不难想到，哈希函数是导致冲突的原因之一，更进一步，如果我们增加桶的数量，再采用合适的哈希函数，可使发生冲突的可能性大大减小。
然而，桶的个数太多则会造成大量的空间浪费。比如一个公司的电话号码共有 10 个，每个电话号码是 00000000 到 99999999 内的任意八位数字，如果我们想到一种方案，将每个可能的电话号码作为一个桶，使得电话号码与桶一一对应，则一共需要创建 10^8个桶。
实际利用桶的个数 与 桶的总数 的比值，称为负载因子。在这个实例中，负载因子太小甚至接近于 0，这样的方案显然是不现实的。
比较合理的负载因子是 0.7，如果数据量是 7，则会创建 10 个桶，以此类推。随着插入的数据量的增加，计算机会逐渐增加桶的个数，并选择合适的哈希函数，使得数据经过映射之后能均匀地分布在桶中。
哈希集合
哈希集合（Set）是一种存储「不重复值」的数据结构，有两种典型的实现方式：
- 若数据取值范围有限（通常 max - min <= 1e6），可以直接使用数组，出现的元素标记为 1 ，未出现的元素标记为 0 ；
- 方法 1 存在超内存的风险，可以直接使用set数据结构（例如：C++ unordered_set、Java HashSet、Python set等）。
若需要对给定的数据进行「判重/去重」，而不涉及到 key 与 value 间的一一映射关系，可借助 Set 这一数据结构完成。例如：
- 「判重」判断数组 nums 中是否存在重复的元素；
- 「去重」去除数组 nums 中的重复元素，并以数组形式返回。
哈希映射
哈希映射（Map）是一种键值对（key-value）数据结构，其中key「无重复」，常用于「建立 key 与 value 的一一映射关系」。Map 有两种典型的实现方式：
(1) 若 key 取值范围有限（通常 key 的最大值与最小值之差 <= 1e6），可以直接使用数组，将出现的 key 对应的元素值标记为 value，未出现的元素标记为数据中任一不存在的元素值；
(2) 方法 (1) 中的数组长度过大，存在超内存的风险，此时可以设计哈希映射，或直接使用 map 数据结构（建议此方式，例如：C++ unordered_map、Java HashMap、Python dict等）。
若需要充分利用 key 与 value 间的「一一映射关系」，即：除元素本身外的更多信息「例如：元素出现位置、元素出现次数等」，可借助 Map 这一数据结构完成。例如：
(1) 「利用元素出现位置」寻找数组 nums 中满足下标不同的两个元素之和等于 target；
(2) 「利用元素出现次数」返回数组 nums 中出现次数最多的元素（最少同理）。栈与队列
队列
高频例题
用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。 ```javascript let MyStack = function() { this.queue = []; this._queue = []; };
MyStack.prototype.push = function(x) { this.queue.push(x); };
MyStack.prototype.pop = function() { while(this.queue.length > 1){ this._queue.push(this.queue.shift()); } let ans = this.queue.shift(); while(this._queue.length){ this.queue.push(this._queue.shift()); } return ans; };
MyStack.prototype.top = function() { return this.queue.slice(-1)[0]; };
MyStack.prototype.empty = function() { return !this.queue.length; };
<a name="r6naH"></a>### 滑动窗口最大值给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。<br />返回 滑动窗口中的最大值 。```javascript/*** @param {number[]} nums* @param {number} k* @return {number[]}*/var maxSlidingWindow = function (nums, k) {class MonoQueue {queue;constructor() {this.queue = [];}enqueue(value) {let back = this.queue[this.queue.length - 1];while (back !== undefined && back < value) {this.queue.pop();back = this.queue[this.queue.length - 1];}this.queue.push(value);}dequeue(value) {let front = this.front();if (front === value) {this.queue.shift();}}front() {return this.queue[0];}}let helperQueue = new MonoQueue();let i = 0, j = 0;let resArr = [];while (j < k) {helperQueue.enqueue(nums[j++]);}resArr.push(helperQueue.front());while (j < nums.length) {helperQueue.enqueue(nums[j]);helperQueue.dequeue(nums[i]);resArr.push(helperQueue.front());i++, j++;}return resArr;};
知识点快照
队列简介
在 FIFO 数据结构中，将首先处理添加到队列中的第一个元素。
如上图所示，队列是典型的 FIFO 数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。 删除（delete）操作也被称为出队（dequeue)。 你只能移除第一个元素。
队列和广度优先搜索
广度优先搜索（BFS）的一个常见应用是找出从根结点到目标结点的最短路径。在本文中，我们提供了一个示例来解释在 BFS 算法中是如何逐步应用队列的。
栈
高频例题
用栈实现队列
var MyQueue = function() {this.stack1 = []this.stack2 = []};/*** @param {number} x* @return {void}*/MyQueue.prototype.push = function(x) {this.stack1.push(x)};/*** @return {number}*/MyQueue.prototype.pop = function() {if(this.stack2.length) {return this.stack2.pop()} else {while(this.stack1.length) {this.stack2.push(this.stack1.pop())}return this.stack2.pop()}};/*** @return {number}*/MyQueue.prototype.peek = function() {if(this.stack2.length) return this.stack2[this.stack2.length-1]else {if(this.stack1.length) {return this.stack1[0]}}};/*** @return {boolean}*/MyQueue.prototype.empty = function() {return !this.stack1.length && !this.stack2.length};
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//双指针//某一列能接的雨水量。取决于 左边最高和右边最高 中较小的那个减去当前列的高度var trap = function(arr) {let leftMax=0,rightMax=0;let left=0,right=arr.length-1;let res=0;while(left<right){leftMax=Math.max(leftMax,arr[left]);//每开始一个循环就要更新最大值rightMax=Math.max(rightMax,arr[right]);if(arr[left]<arr[right]){//left<right可以推出leftMax<rightMaxres+=leftMax-arr[left];//雨水等于较小的那个Max减去当前高度left++;}else{res+=rightMax-arr[right];//此时较小的那个就是rightMaxright--;}}return res;}
知识点快照
栈简介
在 LIFO 数据结构中，将首先处理添加到队列中的最新元素。
与队列不同，栈是一个 LIFO 数据结构。通常，插入操作在栈中被称作入栈 push 。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop ，将始终删除队列中相对于它的最后一个元素。
二叉树
二叉树的遍历
二叉树的属性
二叉树的构造
若有收获，就点个赞吧
0 人点赞
