揭秘B站智能防挡弹幕的原理与实现
相信大家一定都经常看视频，尤其是年轻人最爱的B站或者爱奇艺，腾讯等等长短视频。是当下民众快消文化的一种体现。近期有时间，给大家分享下智能防挡弹幕的实现及原理。希望大家能喜欢。
最近年底了，有点忙，拖更了一个月进阶算法之排序和搜索排序和搜索是什么？排序：把某个乱序的数组变成升序或者降序的数组搜索：找出数组中某个元素的下标JS中的排序和搜索JS中的排序：数组的sort方法JS中的搜索：数组的indexOf方法排序算法：冒泡排序选择排序插入排序归并排序快速排序...搜索算法顺序搜索二分搜索...JavaScript实现：冒泡排序冒泡排序的思路比较所有相邻元素，如果第一个比第二个大，则交换他们一轮下来，可以保证最后一个数是最大的执行n-1轮，就可以完成排序各类排序的思路动画演示 https://visualgo.net/zh冒泡排序的时间复杂度两个嵌套循环时间复杂度：O（n^2）// 冒泡排序 Array.prototype.bubbleSort = function () { console.log(this); for (let i = 0; i < this.length - 1; i += 1) { for (let j = 0; j < this.length - 1 - i; j += 1) { console.log(this[j], this[j + 1]) if (this[j] > this[j + 1]) { const temp = this[j]; this[j] = this[j + 1]; this[j + 1] = temp; } } } }; const arr = [5, 4, 3, 2, 1] arr.bubbleSort();JavaScript实现：选择排序找到数组中的最小值，选中它并将其放置在第一位接着找到第二小的值，选中它并将其放置在第二位以此类推，执行n - 1 轮选择排序的时间复杂度两个嵌套循环时间复杂度：O（n^2）// 选择排序的实现 Array.prototype.selectionSort = function () { for (let i = 0; i < this.length - 1; i += 1) { let indexMin = i; for (let j = i; j < this.length; j += 1) { if (this[j] < this[indexMin]) { indexMin = j; } } if (indexMin !== i) { const temp = this[i]; this[i] = this[indexMin]; this[indexMin] = temp; } } }; const arr = [5, 4, 3, 2, 1] arr.selectionSort();JavaScript实现：插入排序从第二个数开始往前比比它大就往后排以此类推进行到最后一个数插入排序的时间复杂度两个嵌套循环时间复杂度：O（n^2）// 插入排序的实现 Array.prototype.insertionSort = function () { for (let i = 1; i < this.length; i += 1) { const temp = this[i]; let j = i; while (j > 0) { if (this[j - 1] > temp) { this[j] = this[j - 1]; } else { break; } j -= 1; } this[j] = temp; } }; const arr = [5, 4, 3, 2, 1] arr.insertionSort();JavaScript实现：归并排序分：把数组劈成两半，在递归地对子数组进行"分"操作，直到分成一个个单独的数合：把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组合并两个有序数组新建一个空数组res，用于存放最终排序后的数组比较两个有序数组的头部，较小者出队并推入res中如果两个数组还有值，就重复第二步归并排序的时间复杂度分的时间复杂度是O（logN）合的时间复杂度：O（n）时间复杂度：O（nlogN）// 归并排序的实现 Array.prototype.mergeSort = function () { // 分 const rec = (arr) => { if (arr.length === 1) { return arr; } const mid = Math.floor(arr.length / 2); // 获取中间下标 const left = arr.slice(0, mid); // 获取左边数组 const right = arr.slice(mid, arr.length); // 获取右边数组 const orderLeft = rec(left); // 左边数组有序 const orderRight = rec(right); // 右边数组有序 const res = []; while (orderLeft.length || orderRight.length) { if (orderLeft.length && orderRight.length) { // 比较队头 res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift()); } else if (orderLeft.length) { res.push(orderLeft.shift()); } else if (orderRight.length) { res.push(orderRight.shift()); } } return res; } const res = rec(this); res.forEach((n, i) => { this[i] = n; }) } const arr = [5, 4, 3, 2, 1]; arr.mergeSort();JavaScript实现：快速排序分区：从数组中任意选择一个“基准”，所有比基准小的元素放在基准前面，比基准大的元素放在基准的后面递归：递归地对基准前后的子数组进行分区快速排序的时间复杂度递归的时间复杂度是O（logN）分区操作的时间复杂度：O（n）时间复杂度：O（nlogN）// 快速排序的实现 Array.prototype.quickSort = function () { const rec = (arr) => { if (arr.length === 1) { return arr; } const left = []; const right = []; const mid = arr[0]; for (let i = 1; i < arr.length; i += 1) { if (arr[i] < mid) { left.push(arr[i]); } else { right.push(arr[i]); } } return [...rec(left), mid, ...rec(right)]; } const res = rec(this); res.forEach((n, i) => { this[i] = n; }); } const arr = [2, 4, 5, 3, 1]; arr.quickSort(); console.log(arr)JavaScript实现：顺序搜索遍历数组找到跟目标值相等的元素，就返回它的下标遍历结束后，如果没有搜索到目标值，就返回-1顺序搜索的时间复杂度遍历数组是一个循环操作时间复杂度：O（n）// 顺序搜索的实现 Array.prototype.sequentialSearch = function (item) { for (let i = 0; i < this.length; i += 1) { if (this[i] === item) { return i; } } return -1; } const res = [1, 2, 3, 4, 5].sequentialSearch(3);Javascript实现：二分搜索从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束如果目标值大于或者小于中间元素，则在大于或小于中间元素的那一半数组中搜索二分搜索的时间复杂度每一次比较都使搜索范围缩小一半时间复杂度：O（logN）// 二分搜索的实现 Array.prototype.binarySearch = function (item) { let low = 0; let high = this.length - 1; while (low <= high) { const mid = Math.floor((low + high) / 2); const element = this[mid]; if (element < item) { low = mid + 1; } else if (element > item) { high = mid - 1; } else { return mid; } } return -1; } const res = [1, 2, 3, 4, 5].binarySearch(5);LeetCode #21 合并两个有序链表将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例：输入：1->2->4, 1->3->4输出：1->1->2->3->4->4解题思路：与归并排序中的合并两个有序数组很相似将数组替换成链表就能解决此题解题步骤：新建一个新链表，作为返回结果用指针遍历两个有序链表，并比较两个链表的当前节点，较小者先接入新链表，并将指针后移一步链表遍历结束，返回新链表复杂度：时间复杂度：O（n）即链表1和链表2的长度之和空间复杂度：O（1）/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var mergeTwoLists = function(l1, l2) { const res = new ListNode(0); // 新建新链表 let p = res; let p1 = l1; // 指针1：不停指向新链表的最后一个节点。 let p2 = l2; while(p1 && p2){ // 链表1当前节点值小于链表2当前节点值 if(p1.val < p2.val){ p.next = p1; // p1接到新链表最后一个节点上 p1 = p1.next; // 移动 }else{ p.next = p2; // p2接到新链表最后一个节点上 p2 = p2.next; } p = p.next; // 保证p永远指向新链表最后一个节点上 } if(p1){ p.next = p1; } if(p2){ p.next = p2; } return res.next; // 输出链表的头部上一个节点 };LeetCode #374 猜数字大小猜数字游戏的规则如下：每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：-1：我选出的数字比你猜的数字小 pick < num1：我选出的数字比你猜的数字大 pick > num0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num示例 ：输入：n = 10, pick = 6输出：6输入：n = 1, pick = 1输出：1输入：n = 2, pick = 1输出：1输入：n = 2, pick = 2输出：2提示：1 <= n <= 2^31 - 11 <= pick <= n解题思路：二分搜索调用guess函数，来判断中间元素是否是目标值解题步骤：从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束如果目标值大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找复杂度：时间复杂度：O（logN）空间复杂度：O（1）/** * Forward declaration of guess API. * @param {number} num your guess * @return -1 if num is lower than the guess number * 1 if num is higher than the guess number * otherwise return 0 * var guess = function(num) {} */ /** * @param {number} n * @return {number} */ var guessNumber = function(n) { let low = 1; let high = n; while(low <= high){ const mid = Math.floor((low + high) / 2); const res = guess(mid); // console.log('mid', mid); // console.log('res', res); if(res === 0){ return mid; } else if (res === 1){ low = mid + 1; } else { high = mid - 1; } } };排序与搜索-章节总结排序和搜索是什么？排序：把某个乱序的数组变成升序或者降序的数组搜索：找出数组中某个元素的下标JS中的排序和搜索JS中的排序：数组的sort方法JS中的搜索：数组的indexOf方法排序算法：冒泡排序 O(n²)选择排序 O(n²)插入排序 O(n²)归并排序 O(nlogn)快速排序 O(nlogn)搜索算法顺序搜索 O(n)二分搜索 O(logn)阶段性思考Chrome 最新的Array.prototype.sort用的是什么排序算法？用二分搜索算法求x的平方根。题目链接：http://leetcode-cn.com/problems/sqrtx/
堆是什么？堆是一种特殊的完全二叉树所有的节点都大于等于(最大堆)或小于等于（最小堆）它的子节点JS中的堆JS中通常用数组表示堆左侧子节点的位置是 2 * index + 1右侧子节点的位置是 2 * index + 2父节点位置是（index - 1）/ 2 的商堆的应用堆能高效。快速地找出最大值和最小值，时间复杂度：O（1）找出第k个最大（小）元素第k个最大（最小）元素构建一个最小（最大）堆，并将元素依次插入堆中当堆的容量超过k，就删除堆顶插入结束后，堆顶就是第k个最大元素JavaScript 实现最小堆类实现步骤：在类里，声明一个数组，用来装元素主要方法：插入，删除堆顶，获取堆顶，获取堆大小插入：将值插入堆的底部，即数组的尾部然后上移：将这个值和它的父节点进行交换，直到父节点小于等于这个插入的值大小为k的堆中插入元素的时间复杂度为O（logK）删除堆顶用数组尾部元素替换堆顶（直接删除堆顶会破坏堆结构）然后下移：将新堆顶和它的子节点进行交换，直到子节点大于等于这个新堆顶大小为k的堆中删除堆顶的时间复杂度为O（logK）获取堆顶和堆的大小获取堆顶：返回数组的头部获取堆的大小：返回数组的长度// 最小堆实现 class MinHeap{ constructor(){ this.heap = []; } // 交换 swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } getParentIndex(i){ // return Math.floor((i - 1) / 2) // 进阶写法，二进制操作，二进制右移一位，即除以2 // 父节点位置是（index - 1）/ 2 的商 return (i - 1) >> 1; } getLeftIndex(i){ // 左侧子节点的位置是 2 * index + 1 return i * 2 + 1; } getRightIndex(i){ // 右侧子节点的位置是 2 * index + 2 return i * 2 + 2; } shiftUp(index){ if(index == 0){ //如果是堆顶，就不再上移 return; } const parentIndex = this.getParentIndex(index); if(this.heap[parentIndex] > this.heap[index]){ this.swap(parentIndex, index); this.shiftUp(parentIndex); } } shiftDown(index){ const leftIndex = this.getLeftIndex(index); const rightIndex = this.getRightIndex(index); if(this.heap[leftIndex] < this.heap[index]){ this.swap(leftIndex, index); this.shiftDown(leftIndex); } if(this.heap[rightIndex] < this.heap[index]){ this.swap(rightIndex, index); this.shiftDown(rightIndex); } } // 插入 insert(value){ this.heap.push(value); // 上移（保证堆的结构正确） this.shiftUp(this.heap.length-1); } pop(){ this.heap[0] = this.heap.pop(); this.shiftDown(0); } // 获取堆顶 peek(){ return this.heap[0]; } // 获取堆的大小 size(){ return this.heap.length; } } const h = new MinHeap(); h.insert(3); h.insert(2); h.insert(1); h.pop();LeetCode #215 数组中的第k个最大元素在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例:输入: [3,2,1,5,6,4] 和 k = 2输出: 5输入: [3,2,3,1,2,4,5,5,6] 和 k = 4输出: 4解题思路：看大“第k个最大元素”考虑使用最小堆解题步骤：构建一个最小堆，并依次把数组的值插入堆中当堆的容量超过k，就删除堆顶插入结束后，堆顶就是第k个最大元素复杂度：时间复杂度：O（n * logk） （上移和下移操作是递归操作）空间复杂度：O（k）（实现的是堆，数组的就是它的空间复杂度）/** * @param {number[]} nums * @param {number} k * @return {number} */ // 最小堆实现 class MinHeap{ constructor(){ this.heap = []; } // 交换 swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } getParentIndex(i){ // return Math.floor((i - 1) / 2) // 进阶写法，二进制操作，二进制右移一位，即除以2 // 父节点位置是（index - 1）/ 2 的商 return (i - 1) >> 1; } getLeftIndex(i){ // 左侧子节点的位置是 2 * index + 1 return i * 2 + 1; } getRightIndex(i){ // 右侧子节点的位置是 2 * index + 2 return i * 2 + 2; } shiftUp(index){ if(index == 0){ //如果是堆顶，就不再上移 return; } const parentIndex = this.getParentIndex(index); if(this.heap[parentIndex] > this.heap[index]){ this.swap(parentIndex, index); this.shiftUp(parentIndex); } } shiftDown(index){ const leftIndex = this.getLeftIndex(index); const rightIndex = this.getRightIndex(index); if(this.heap[leftIndex] < this.heap[index]){ this.swap(leftIndex, index); this.shiftDown(leftIndex); } if(this.heap[rightIndex] < this.heap[index]){ this.swap(rightIndex, index); this.shiftDown(rightIndex); } } // 插入 insert(value){ this.heap.push(value); // 上移（保证堆的结构正确） this.shiftUp(this.heap.length-1); } pop(){ this.heap[0] = this.heap.pop(); this.shiftDown(0); } // 获取堆顶 peek(){ return this.heap[0]; } // 获取堆的大小 size(){ return this.heap.length; } } var findKthLargest = function(nums, k) { const heap = new MinHeap(); // 把数组中的值依次插入到堆中 nums.forEach(n => { heap.insert(n); // 当发现堆的大小超过k，部分元素出去 if(heap.size() > k){ heap.pop(); } }) // console.log(heap) return heap.peek(); };LeetCode #347 前k个高频元素给定一个非空的整数数组，返回其中出现频率前 k 高的元素。示例:输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2]输入: nums = [1], k = 1输出: [1]提示：你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。你可以按任意顺序返回答案解题思路一：（统计所有的元素出现的频率）：利用map记录所有元素出现的频率对map进行转数组，然后降序排序然后通过找出k之前的频率返回出对应的元素复杂度：时间复杂度：O（nlogn），原生排序最优的时间复杂度是 O（nlogn）。不符合题目要求空间复杂度：O（n）/** * @param {number[]} nums * @param {number} k * @return {number[]} */ var topKFrequent = function(nums, k) { // 实现： 统计所有元素出现的次数 const map = new Map(); nums.forEach(n => { map.set(n, map.has(n) ? map.get(n) + 1 : 1); }) /** * 排序 * 1. map 转数组 * 2. 降序排序 */ const list = Array.from(map).sort((a,b) => b[1] - a[1]); // console.log(list) // console.log(map); return list.slice(0, k).map(n=>{ return n[0] }) };解题思路二：（堆的思路）建立一个最小堆把元素及频率插入到堆中按照频率排序复杂度：时间复杂度：O（n logk）。因为1<= k <= n 所以 n logk < n * logn。符合题意空间复杂度：O（n）。字典复杂度是n 堆的复杂度是k ，k<n/** * @param {number[]} nums * @param {number} k * @return {number[]} */ // 最小堆实现 class MinHeap{ constructor(){ this.heap = []; } // 交换 swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } getParentIndex(i){ // return Math.floor((i - 1) / 2) // 进阶写法，二进制操作，二进制右移一位，即除以2 // 父节点位置是（index - 1）/ 2 的商 return (i - 1) >> 1; } getLeftIndex(i){ // 左侧子节点的位置是 2 * index + 1 return i * 2 + 1; } getRightIndex(i){ // 右侧子节点的位置是 2 * index + 2 return i * 2 + 2; } shiftUp(index){ if(index == 0){ //如果是堆顶，就不再上移 return; } const parentIndex = this.getParentIndex(index); if(this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value){ this.swap(parentIndex, index); this.shiftUp(parentIndex); } } shiftDown(index){ const leftIndex = this.getLeftIndex(index); const rightIndex = this.getRightIndex(index); if(this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value){ this.swap(leftIndex, index); this.shiftDown(leftIndex); } if(this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value){ this.swap(rightIndex, index); this.shiftDown(rightIndex); } } // 插入 insert(value){ this.heap.push(value); // 上移（保证堆的结构正确） this.shiftUp(this.heap.length-1); } pop(){ this.heap[0] = this.heap.pop(); this.shiftDown(0); } // 获取堆顶 peek(){ return this.heap[0]; } // 获取堆的大小 size(){ return this.heap.length; } } var topKFrequent = function(nums, k) { // 实现： 堆的思路，最小堆 const map = new Map(); nums.forEach(n => { map.set(n, map.has(n) ? map.get(n) + 1 : 1) }) const heap = new MinHeap(); map.forEach((value, key)=>{ heap.insert({value, key}); // 保证最小堆的尺寸永远小于k if(heap.size() > k){ // 剔除最小的 heap.pop(); } }) // console.log(heap) return heap.heap.map(obj => obj.key) };LeetCode #23 合并k个排序链表给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。示例 1：输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6示例 2：输入：lists = []输出：[]示例 3：输入：lists = [[]]输出：[] 提示：k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= listsi <= 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4解题思路：新链表的下一个节点一定是k个链表头中的最小节点考虑选择使用最小堆解题步骤：构建一个最小堆，并依次把链表头插入堆中弹出堆顶接到输出链表，并将堆顶所在链表的新链表头插入堆中堆元素全部弹出，合并工作就完成了。复杂度：时间复杂度：O（n * logk）空间复杂度：O（k）/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ // 最小堆实现 class MinHeap{ constructor(){ this.heap = []; } // 交换 swap(i1, i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } getParentIndex(i){ // return Math.floor((i - 1) / 2) // 进阶写法，二进制操作，二进制右移一位，即除以2 // 父节点位置是（index - 1）/ 2 的商 return (i - 1) >> 1; } getLeftIndex(i){ // 左侧子节点的位置是 2 * index + 1 return i * 2 + 1; } getRightIndex(i){ // 右侧子节点的位置是 2 * index + 2 return i * 2 + 2; } shiftUp(index){ if(index == 0){ //如果是堆顶，就不再上移 return; } const parentIndex = this.getParentIndex(index); if(this.heap[parentIndex] && this.heap[parentIndex].val > this.heap[index].val){ this.swap(parentIndex, index); this.shiftUp(parentIndex); } } // 下移 shiftDown(index){ const leftIndex = this.getLeftIndex(index); const rightIndex = this.getRightIndex(index); if(this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[index].val){ this.swap(leftIndex, index); this.shiftDown(leftIndex); } if(this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val){ this.swap(rightIndex, index); this.shiftDown(rightIndex); } } // 插入 insert(value){ this.heap.push(value); // 上移（保证堆的结构正确） this.shiftUp(this.heap.length-1); } // 弹出堆顶 pop(){ if(this.size() === 1){ return this.heap.shift(); } const top = this.heap[0]; this.heap[0] = this.heap.pop(); this.shiftDown(0); return top; } // 获取堆顶 peek(){ return this.heap[0]; } // 获取堆的大小 size(){ return this.heap.length; } } /** * @param {ListNode[]} lists * @return {ListNode} */ var mergeKLists = function(lists) { // 输出链表 const res = new ListNode(0); let p = res; // 声明指针，接入输入链表 // 新建最小堆 const heap = new MinHeap(); // 把链表的头部节点都放在最小堆中 lists.forEach(list => { // 循环所有链表 if(list){ heap.insert(list); } }) while(heap.size()){ // 弹出堆顶，即链表们中头部节点最小值 const n = heap.pop(); p.next = n; p = p.next; // 指针向下走 if(n.next){ // 最小节点的next 插入到堆中 heap.insert(n.next); } } return res.next; };堆-章节总结堆是一种特殊的完全二叉树所有的节点都大于等于（最大堆）或者小于等于（最小堆）它的子节点JS中通常用数组表示堆堆能高效，快速地找出最大值和最小值，时间复杂度：O（1）找出第k个最大（小）元素
图是什么？图是网络结构的抽象模型，是一组由边连接的节点图可以表示任何二元关系，比如道路、航班。JS中没有图，但是可以用Object和Array构建图图的表示法：邻接矩阵，邻接表，关联矩阵{ "V1"：["V2", "V3", "V4"], "V2": [], "V3": ["V4"], "V4": ["V1"] }图的常用操作深度优先遍历：尽可能深的搜索图的分支广度优先遍历：先访问离根节点最近的节点图的深度优先遍历的算法口诀访问根节点对根节点的没访问过的相邻节点挨个进行深度优先遍历图的广度优先遍历的算法口诀新建一个队列，把根节点入队把队头出队并访问把队头的没访问过的相邻节点入队重复第二三步，直到队列为空// graph.js const graph ={ 0: [1, 2], 1: [2], 2: [0, 3], 3: [3] } module.exports = graph;// 图的深度优先遍历实现 const graph= require('./graph'); // 用来记录已访问过的节点 const visited = new Set(); const dfs = (n)=>{ console.log(n); visited.add(n); graph[n].forEach(c => { // 拿到所有相邻节点 if(!visited.has(c)){ // 还未访问过的相邻接点 dfs(c); } }); }; dfs(2);// 图的广度优先遍历实现 const graph = require('./graph') const visited = new Set(); visited.add(2); const queue = [2]; while(queue.length){ const n = queue.shift(); console.log(n); graph[n].forEach(c => { if(!visited.has(c)){ queue.push(c); visited.add(c); } }); }LeetCode #65 有效的数组LeetCode #417 太平洋大西洋水流问题给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。提示：输出坐标的顺序不重要m 和 n 都小于150 示例：给定下面的 5x5 矩阵: 太平洋 ~ ~ ~ ~ ~ ~ 1 2 2 3 (5) * ~ 3 2 3 (4) (4) * ~ 2 4 (5) 3 1 * ~ (6) (7) 1 4 5 * ~ (5) 1 1 2 4 * * * * * * 大西洋返回：[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).解题思路：把矩阵想象成图（有向图）从海岸线逆流而上遍历图，所到之处就是可以流到某个大洋的坐标解题步骤：新建两个矩阵，分别记录能流到两个大洋的坐标从海岸线，多管齐下，同时深度优先遍历图，过程中填充上边的那个矩阵遍历两个矩阵，找出能流到两个大洋的坐标复杂度：时间复杂度O（m * n）空间复杂度O（m * n）/** * @param {number[][]} matrix * @return {number[][]} */ var pacificAtlantic = function(matrix) { if(!matrix || !matrix[0]){ return []; } const m = matrix.length; const n = matrix[0].length; // 构建数组的两种方法1. Array.from({length:n}) 2. new Array(n) const flow1 = Array.from({length: m}, ()=> {return new Array(n).fill(false)}); // 能流到太平洋的矩阵 const flow2 = Array.from({length: m}, ()=> {return new Array(n).fill(false)}); // 能流到大西洋的矩阵 const dfs = (row, cow, flow)=>{ // 行，列 flow[row][cow] = true; [[row-1, cow], [row+1, cow], [row, cow-1], [row, cow+1]].forEach(([nextrow, nextcow])=>{ // 相邻的上，下，左，右四个节点的数组遍历 if( //保证下一个节点在矩阵中 nextrow >= 0 && nextrow < m && nextcow >= 0 && nextcow < n && // 防止死循环，即保证未访问过该节点 !flow[nextrow][nextcow] && // 保证逆流而上 matrix[nextrow][nextcow] >= matrix[row][cow] ){ dfs(nextrow, nextcow, flow) } }) }; // 沿着海岸线逆流而上 for(let row=0; row<m; row++){ dfs(row, 0 ,flow1); // 从第一行到最后一行，保证第一列，流到太平洋 dfs(row, n-1, flow2); // 遍历最后一列的格子，流到大西洋 传flow2 } for(let cow=0; cow<n; cow++){ dfs(0, cow, flow1); // 遍历第一行，太平洋 dfs(m-1, cow, flow2); // 遍历最后一行，大西洋 } // 收集能流到两个大洋的坐标 const res = []; for(let row=0; row<m; row++){ // 遍历所有行 for(let cow=0; cow<n; cow++){ // 遍历所有列 if( flow1[row][cow] && // 能流到太平洋 flow2[row][cow] // 能流到大西洋 ){ res.push([row,cow]) } } } // console.log(flow1) // console.log(flow2) return res; };LeetCode #133 克隆图给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。class Node { public int val; public List<Node> neighbors; }测试用例格式：简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。示例1：输入：adjList = [[2,4],[1,3],[2,4],[1,3]] 输出：[[2,4],[1,3],[2,4],[1,3]] 解释： 图中有 4 个节点。 节点 1 的值是 1，它有两个邻居：节点 2 和 4 。 节点 2 的值是 2，它有两个邻居：节点 1 和 3 。 节点 3 的值是 3，它有两个邻居：节点 2 和 4 。 节点 4 的值是 4，它有两个邻居：节点 1 和 3 。示例 2：输入：adjList = [[]]输出：[[]]解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。示例3：输入：adjList = []输出：[]解释：这个图是空的，它不含任何节点。示例4：输入：adjList = [[2],[1]]输出：[[2],[1]] 提示：节点数不超过 100 。每个节点值 Node.val 都是唯一的，1 <= Node.val <= 100。无向图是一个简单图，这意味着图中没有重复的边，也没有自环。由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。图是连通图，你可以从给定节点访问到所有节点。解题思路：拷贝所有节点拷贝所有的边解题步骤：深度或广度优先遍历所有的节点拷贝所有的节点，存储起来将拷贝的节点，按照原图的连接方法进行连接复杂度：深度优先遍历时间复杂度：O（n）空间复杂度：O（n）广度优先遍历时间复杂度：O（n）空间复杂度：O（n）/** * // Definition for a Node. * function Node(val, neighbors) { * this.val = val === undefined ? 0 : val; * this.neighbors = neighbors === undefined ? [] : neighbors; * }; */ /** * @param {Node} node * @return {Node} */ var cloneGraph = function(node) { if(!node){ return; } const visited = new Map(); // 记录映射关系 // 深度优先遍历实现 const dfs = (node) => { // console.log(node.val) // 访问节点 // 拷贝每一个节点 const nCopy = new Node(node.val); // 节点存放到已访问, 建立映射关系 visited.set(node, nCopy); (node.neighbors || []).forEach(nodeneighbors=>{ // 如果没有neighbors 转换成[] if(!visited.has(nodeneighbors)){ dfs(nodeneighbors); } // 拷贝所有的边 nCopy.neighbors.push(visited.get(nodeneighbors)); }) }; dfs(node); // 给定节点的拷贝 作为对克隆图的引用返回。 return visited.get(node) };/** * // Definition for a Node. * function Node(val, neighbors) { * this.val = val === undefined ? 0 : val; * this.neighbors = neighbors === undefined ? [] : neighbors; * }; */ /** * @param {Node} node * @return {Node} */ var cloneGraph = function(node) { if(!node){ return; } const visited = new Map(); // 记录映射关系 visited.set(node, new Node(node.val)) // 广度优先遍历实现 const queue = [node]; while(queue.length){ const n = queue.shift(); // 拿出对头并访问 // console.log(n.val); (n.neighbors || []).forEach(nodeneighbors=>{ // 访问所有邻居节点 if(!visited.has(nodeneighbors)){ queue.push(nodeneighbors); // 拷贝节点 visited.set(nodeneighbors, new Node(nodeneighbors.val)); } // 拷贝边 visited.get(n).neighbors.push(visited.get(nodeneighbors)); }) } return visited.get(node) // 给定节点的拷贝 作为对克隆图的引用返回。 };图-章节总结图是网络结构的抽象模型，是一组由边连接的节点图可以表示任何二元关系，比如道路，航班.技术要点JS中没有图，但是可以用Object和Array构件图图的表示法：邻接矩阵，邻接表...图的常用操作：深度、广度优先遍历思考用图画出你的朋友圈
树是什么？一种分层数据的抽象模型前端工作中常见的树包括：DOM树，级联选择、树形控件JS中没有树，但是可以用Object和Array构建树树的常用操作：深度/广度优先遍历、先中后序遍历什么是树的深度/广度优先遍历？深度优先遍历：尽可能深的搜索树的分支广度优先遍历：先访问离根节点最近的节点深度优先遍历算法口诀访问根节点对根节点的children挨个进行深度优先遍历const tree = { val: 'a', children: [ { val: 'b', children: [ { val: 'd', children: [] }, { val: 'e', children: [] } ] }, { val: 'c', children: [ { val: 'f', children: [] }, { val: 'g', children: [] } ] } ] } const dfs = (root) => { console.log(root.val); // root.children.forEach((child)=>{ // dfs(child) // }) // 优化写法 root.children.forEach(dfs) } dfs(tree)广度优先遍历算法口诀新建一个队列，把根节点入队把对头出队并访问把对头的children挨个入队重复第二三步，知道队列为空const tree = { val: 'a', children: [ { val: 'b', children: [ { val: 'd', children: [] }, { val: 'e', children: [] } ] }, { val: 'c', children: [ { val: 'f', children: [] }, { val: 'g', children: [] } ] } ] } const bfs = (root)=>{ const queue = [root]; while(queue.length>0){ const n = queue.shift(); console.log(n.val) n.children.forEach(child=>{ queue.push(child); }) } } bfs(tree)二叉树的先中后遍历二叉树是什么？树中每个节点最多只能有两个子节点在JS中通常用Object来模拟二叉树先序遍历算法口诀访问根节点对根节点的左子树进行先序遍历对根节点的右子树进行先序遍历// 二叉树 bt.js const bt = { val: 1, left: { val: 2, left: { val: 4, left: null, right: null }, right: { val: 5, left: null, right: null } }, right: { val: 3, left: { val: 6, left: null, right: null }, right: { val: 7, left: null, right: null } } } module.exports = bt;// 先序遍历 const bt = require('./bt'); const preorder = (root)=> { if(!root){ return; } console.log(root.val) preorder(root.left); preorder(root.right); } preorder(bt); // 1 2 4 5 3 6 7中序遍历算法口诀对根节点的左子树进行中序遍历访问根节点对根节点的右子树进行中序遍历// 中序遍历 const bt = require('./bt'); const inorder = (root)=>{ if(!root){ return; } inorder(root.left); console.log(root.val); inorder(root.right); } inorder(bt) // 4 2 5 1 6 3 7后续遍历算法口诀对根节点的左子树进行后续遍历对根节点的右子树进行后续遍历访问根节点// 后续遍历 const bt = require('./bt'); const postorder = (root)=>{ if(!root){ return; } postorder(root.left); postorder(root.right); console.log(root.val); } // postorder(bt) // 4 5 2 6 7 3 1二叉树的先中后序遍历(非递归版)// 先序遍历（非递归版）核心思路用堆栈，因为在函授中调用另一个函数其实就是连续的调用堆栈，即递归版的原理 const preorderPlus = (root) =>{ if(!root){ return; } const stack = [root]; while(stack.length){ const n = stack.pop(); // 最开始访问根节点的值，循环到以后就是部分子树的根节点 console.log(n.val); // 栈：后进先出 所以需要先推right if(n.right){// 递归右子树 stack.push(n.right); } if(n.left){ // 递归左子树 stack.push(n.left); } } } preorderPlus(bt)// 中序遍历（非递归版） const inorderPlus = (root)=>{ if(!root){ return; } // 核心思路：遍历所有左子树->根节点->右子树 const stack = []; let p = root; // 指针 while(stack.length || p){ // 循环1,2,3,4 while(p){ // 1.把所有子树丢入栈中 stack.push(p); p = p.left; } // 2.弹出最尽头的节点 const n = stack.pop(); // 3.访问最尽头的节点 console.log(n.val); // 4.访问右节点（指针指向右节点） p = n.right; } } inorderPlus(bt)// 后续遍历（非递归版） const postorderPlus = (root)=>{ // 核心思路： // 1. 把后续遍历的顺序倒置(左右根->根右左，与先序遍历很像) // 2. 把先序遍历的访问操作，改成入栈操作 // 3. 利用栈的后进先出特性，子节点逆序输出 if(!root){ return; } const outputStack = []; // 做倒置操作的堆栈 const stack = [root]; // 函数调用堆栈 while(stack.length){ // 根右左 const n = stack.pop(); outputStack.push(n); if(n.left){ stack.push(n.left); } if(n.right){ stack.push(n.right); } } while(outputStack.length){ // 倒序输出 const n = outputStack.pop(); console.log(n.val); } } postorderPlus(bt) LeetCode #104 二叉树的最大深度给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例：给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7返回它的最大深度 3 。解题思路：求最大深度，考虑使用深度优先遍历在深度优先遍历过程中，记录每个节点所在层级，找出最大层级即可。解题步骤：新建一个变量记录最大深度深度优先遍历整棵树，并记录每个节点的层级，同时不断刷新最大深度这个变量。遍历结束返回最大深度的变量复杂度：时间复杂度：O（n）空间复杂度：最坏 O（n）最好 O（logN） （隐形调用了函数堆栈）/** * @param {TreeNode} root * @return {number} */ var maxDepth = function(root) { let deepMax = 0; const dfs = (node, level)=>{ // level即节点所处层级 if(!node){ return; } if(!node.left && !node.right){ // 只在叶子节点时计算最大深度 deepMax = Math.max(deepMax, level) } dfs(node.left, level + 1); dfs(node.right, level + 1); }; dfs(root,1); return deepMax; };LeetCode #111 二叉树的最小深度给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。示例输入：root = [3,9,20,null,null,15,7]输出：2输入：root = [2,null,3,null,4,null,5,null,6]输出：5提示：树中节点数的范围在 [0, 105] 内-1000 <= Node.val <= 1000解题思路：求最小深度，考虑使用广度优先遍历在广度优先遍历过程中，遇到叶子节点，停止遍历，返回节点层级解题步骤：广度优先遍历整颗树，并记录每个节点的层级遇到叶子节点，返回节点层级，停止遍历复杂度：时间复杂度：O（n）空间复杂度：O（n）/** * @param {TreeNode} root * @return {number} */ var minDepth = function(root) { if(!root) { return 0; } const queue = root, 1; // 新建队列，并把根节点传入 while(queue.length){ const [node, level] = queue.shift(); // 拿出队头，并访问 if(!node.left && !node.right){ // 如果是叶子节点 return level } if(node.left){ queue.push([node.left, level + 1]); // 当前节点的孩子节点加入对列 } if(node.right){ queue.push([node.right,level + 1]); } } };LeetCode #102 二叉树的层序遍历给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。示例：二叉树：[3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7返回其层次遍历结果：[ [3], [9,20], [15,7] ]解题思路：层序遍历顺序就是广度优先遍历不过在遍历时候需要记录当前节点所处的层级，方便将其添加到不同的数组中解题步骤：广度优先遍历（用队列）遍历过程中，记录每个节点的层级，并将其添加到不同的数组中复杂度：时间复杂度：O（n）广度优先遍历空间复杂度：O（n）/** * @param {TreeNode} root * @return {number[][]} */ var levelOrder = function(root) { if(!root){ // 保证root节点不为空 return []; } // 广度优先遍历 const queue = root, 0; // 节点，层级 const res = []; while (queue.length) { const [node, level] = queue.shift(); // 节点出队，并记录每个节点的层级 // console.log(node.val, level) // 访问节点 if(!res[level]){ // res[level]没值的话，先push一个数组 // 把节点的值按照层级分别push到不同数组，返回 res.push([node.val]) }else{ res[level].push(node.val); } // 将节点的孩子节点推进队列 if(node.left){ queue.push([node.left, level + 1]) } if(node.right){ queue.push([node.right, level + 1]) } } return res; };优化方案：/** * @param {TreeNode} root * @return {number[][]} */ var levelOrder = function(root) { if(!root){ // 保证root节点不为空 return []; } const queue = [root]; const res = []; while (queue.length) { let len = queue.length; res.push([]); while(len--){// 优化：保证每次while循环时，老一层级的节点都出队列，其节点的孩子节点们都入队。即保证queue中只有同级节点 const node = queue.shift(); res[res.length - 1].push(node.val); if(node.left){ queue.push(node.left) } if(node.right){ queue.push(node.right) } } } return res; };LeetCode #94 二叉树的中序遍历给定一个二叉树的根节点 root ，返回它的 中序 遍历。示例：输入：root = [1,null,2,3]输出：[1,3,2]输入：root = []输出：[]输入：root = [1]输出：[1]输入：root = [1,2]输出：[2,1]输入：root = [1,null,2]输出：[1,2]提示：树中节点数目在范围 [0, 100] 内-100 <= Node.val <= 100/** * @param {TreeNode} root * @return {number[]} */ var inorderTraversal = function(root) { // 递归版 const res = []; const rec = (node)=>{ if(!node){ return; } // 中序遍历 左根右 rec(node.left); // 左子树 res.push(node.val); // 根节点 rec(node.right); // 右子树 } rec(root); return res; };优化方案：/** * @param {TreeNode} root * @return {number[]} */ var inorderTraversal = function(root) { // 迭代版 const res = []; const stack = []; // 模拟递归堆栈 let point = root; // 指针 while(stack.length || point){ // 整体大循环 while(point){ // 把所有的左节点推入栈中 stack.push(point) point= point.left; } const node = stack.pop(); // 访问节点，即出栈 res.push(node.val); point = node.right; // 指针指向右节点 } return res; };LeetCode #112 路径总和给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。示例: 给定如下二叉树，以及目标和 sum = 22 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。解题思路：在深度优先遍历的过程中，记录当前路径的节点值的和在叶子节点处，判断当前路径的节点值的和是否等于目标值解题步骤：深度优先遍历二叉树，在叶子节点处，判断当前路径的节点值的和是否等于目标值，是九返回true遍历结束，如果没有匹配到，就返回false复杂度：时间复杂度 O（n）空间复杂度 O（n）/** * @param {TreeNode} root * @param {number} sum * @return {boolean} */ var hasPathSum = function(root, sum) { if(!root){ return false; } let res = false; const dfs = (node,sumAcc) => { // console.log(node.val, sumAcc) if(!node.left && !node.right && sumAcc === sum){ res = true; } if(node.left){ dfs(node.left, sumAcc + node.left.val) } if(node.right){ dfs(node.right, sumAcc + node.right.val) } } dfs(root, root.val); return res; };前端与树：遍历JSON的所有节点值用途：清洗JSONconst json = { a: { b: { c: 1 } }, d: [1, 2] } const dfs = (node, path) => { console.log(node, path); // 访问当前节点 Object.keys(node).forEach(k=>{ // 获取所有key，即所有孩子节点 dfs(node[k], path.concat(k)); }) } dfs(json, []);前端与树：渲染Antd的树组件// CodePen 模拟树组件 const { Tree } = antd; const { TreeNode } = Tree; const json = [ { title: "一", key: "1", children: [{title:"三",key:"3",children:[ {title:"五",key:"5",children:[]} ]}] }, { title: "二", key: "2", children: [{title:"四",key:"4",children:[]}] }, ] class Demo extends React.Component { dfs = (node)=>{ return ( <TreeNode title={node.title} key={node.key}> {node.children.map(this.dfs)} </TreeNode> ) } render() { const tProps = { treeDefaultExpandAll: true, style: { width: '100%', }, }; return ( <Tree {...tProps}> {json.map(this.dfs)} </Tree> ); } } ReactDOM.render(<Demo />, mountNode);树-总结树是一种分层数据的抽象模型，在前端广泛应用树的常用操作：深度、广度优先遍历，先中后序遍历...
字典是什么？与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储ES6中有字典，名为Map字典的常用操作：键值对的增删改查const m = new Map(); // 增 m.set('a', 'aa'); // key : value m.set('b', 'bb'); // 删 m.delete('b'); // m.clear(); // 删除所有 // 改 m.set('a', 'aaaa') // 查 m.get('a')LeetCode #349 两个数组的交集给定两个数组，编写一个函数来计算它们的交集。示例 1：输入：nums1 = [1,2,2,1], nums2 = [2,2]输出：[2]示例 2：输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出：[9,4] 说明：输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。解题思路：求nums1和nums2都有的值用字典建立一个映射关系，记录nums1里有的值遍历nums2，找出nums1里边也有的值解题步骤：新建一个字典，遍历nums1，填充字典遍历nums2，遇到字典里的值就选出，并从字典里删除（防止重复）复杂度：时间复杂度：O（m+n）空间复杂度：O（m）/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var intersection = function(nums1, nums2) { const map = new Map(); nums1.forEach(n=>{ map.set(n,true) }) const res = [] nums2.forEach(n=>{ if(map.get(n)){ res.push(n); map.delete(n); } }) return res; };LeetCode #20 有效的括号给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例 1:输入: "()"输出: true示例 2:输入: "()[]{}"输出: true示例 3:输入: "(]"输出: false示例 4:输入: "([)]"输出: false示例 5:输入: "{[]}"输出: true解题思路：利用map建立括号的字典集将之前的复杂的判断条件改写解题步骤：复杂度：1.时间复杂度：O（n）2.空间复杂度：O（n）/** * @param {string} s * @return {boolean} */ var isValid = function(s) { if(s.length %2 === 1) { return false } const stack = []; const map = new Map(); map.set("(",")"); map.set("[","]"); map.set("{","}"); for(let i = 0; i<s.length; i+=1){ const c = s[i]; if(map.has(c)){ stack.push(c); }else{ const top = stack[stack.length-1]; if( map.get(top) === c ){ stack.pop(); }else{ return false; } } } return stack.length === 0; };LeetCode #1 两数之和给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。示例:给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]方法一：var twoSum = function(nums, target) { let result = [] for(let i=0; i<nums.length; i++){ for(let j=i+1; j<nums.length;j++){ if(nums[i]+nums[j] == target){ result.push(i) result.push(j) } } } return result };方法二：/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { const map = new Map(); for(let i=0; i<nums.length;i++){ const n = nums[i] const n2 = target-n; if(map.has(n2)){ return [map.get(n2), i] }else{ map.set(n, i); } } };LeetCode #3 无重复字符的最长子串给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。示例 :输入: "abcabcbb"输出: 3解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。解题思路：先找出所有的不包含重复字符的字串找出长度最大那个字串，返回其长度即可解题步骤：用双指针维护一个滑动窗口，用来剪切字串不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位过程中，记录所有窗口的长度，并返回最大值复杂度：时间复杂度 O（n）空间复杂度 O（m）m即字符串中不重复的个数/** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function(s) { // 左右指针 let left = 0; let res = 0; const map = new Map(); for(let right=0; right<s.length; right++){ if(map.has(s[right]) && map.get(s[right]) >= left){ // 如果遇到重复字符，左指针移动到右指针下一位 && map中的重复字符下标必须在窗口中 left = map.get(s[right]) + 1; } res = Math.max(res, right - left + 1); // 新窗口的右指针与res的较大值 map.set(s[right], right); } return res; };LeetCode #76 最小覆盖子串【Hard】给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。示例 ：输入：s = "ADOBECODEBANC", t = "ABC"输出："BANC"输入：s = "a", t = "a"输出："a" 提示：1 <= s.length, t.length <= 105s 和 t 由英文字母组成进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？解题思路：先找出所有的包含T的字串找出长度最小的那个字串，返回解题步骤：用双指针维护一个滑动窗口，用来枚举所有子串移动右指针，找到包含T的字串，移动左指针，尽量减少包含T的子串的长度复杂度：时间复杂度 O（n+m）n是s的长度, m是t的长度空间复杂度 O（m）m是t里边不同字符的个数/** * @param {string} s * @param {string} t * @return {string} */ var minWindow = function(s, t) { // 创建左右指针 let left = 0; let right = 0; const need = new Map(); for(let c of t){ need.set(c, need.has(c) ? need.get(c) + 1 :1); } // console.log(need); let needType = need.size; let res = ''; // 移动右指针 while(right < s.length){ const c = s[right] // 获取右指针当前的字符 if(need.has(c)){ // 如果右指针在我们当前的列表里面 need.set(c, need.get(c)-1); // need中要减去1 // 满足t所有的都在need if(need.get(c) === 0){ needType -= 1; } } while(needType === 0){ // 缩小字符串范围 // console.log(s.substring(left, right+1)) // 所有子串 const newRes = s.substring(left, right+1) if(!res || newRes.length < res.length){ // 找出长度最小的子 如果res为空 则先赋值给它newRes res = newRes; } const c2 = s[left]; //左指针当前的字符 if(need.has(c2)){ need.set(c2, need.get(c2)+1); // 需求增加 if(need.get(c2) === 1){ // 重新需要这个字符 needType += 1; // 更新needtype } } left += 1; } right += 1; // 判断移动右指针时，滑动窗口（子串）包含t的所有字符：用字典 } return res };字典-章节总结与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储ES6中有字典，名为Map（映射）字典的常用操作：键值对的增，删，改，查思考在实际工作中使用字典完成一次映射操作的场景有一次需求需要自己对DOM树进行遍历，由于遍历的规则可能导致重复访问节点，就用Map将访问过的DOM节点映射为true，然后处理节点前进行判断。const visited = new Map(); visited.set(node, true); ... if (!visited.get(node)) { // 当前节点未访问过，进行处理 }用Chrome的Profile工具或者其他任意前端性能测试工具，测试Map和Object频繁增删操作的性能，谁高谁低？https://www.cnblogs.com/shikelong/p/4179607.htmlhttps://www.sohu.com/a/270479773_216613
集合是什么？一种无序且唯一的数据结构ES6中有集合，名为Set集合的常用操作：去重，判断某元素是否在集合中，求交集Coding Part// 去重 const arr = [1,1,2,2]; const arr2 = [...new Set(arr)]; // 判断元素是否在集合中 const set = new Set(arr); const has = set.has(2); // 求交集 const set2 = new Set([2,3]); const set3 = new Set([...set].filter(item => set2.has(item)))LeetCode #349 给定两个数组，编写一个函数来计算它们的交集。示例输入：nums1 = [1,2,2,1], nums2 = [2,2]输出：[2]输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出：[9,4] 说明：输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。解题思路：求交集且无序唯一解题步骤：用集合对nums1去重, 用new Set( )遍历nums1，筛选出nums2也包含的值 用includes复杂度：时间复杂度：O（n²）或O（mn）空间复杂度：O（n）/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var intersection = function(nums1, nums2) { return [...new Set(nums1)].filter(item=> nums2.includes(item) ) };前端与集合： 使用ES6的Set使用Set对象：new、add、delete、has、size迭代Set: 多种迭代方法、Set与Array互转、求交集、差集let mySet = new Set(); // 添加元素 mySet.add(1); mySet.add(5); mySet.add(5); // set中不能添加重复的基本数据类型 mySet.add('some text'); let o = {a: 1, b:2} mySet.add(o) // set中可以添加内存地址不同的引用类型 mySet.add({a: 1, b:2}) const has = mySet.has(o); mySet.delete(5); // 跌代方法 for(let [key,value] of mySet.entries()) console.log(key,value) // set 转 arr 两种方法 const myArr1 = [...mySet] const myArr2 =Array.from(mySet) const mySet2 = new Set([1,2,3,4]) // 交集 const intersection = new Set([...mySet].filter(x=>mySet2.has(x))) // 差集 const difference = new Set([...mySet].filter(x=> !mySet2.has(x)))集合-章节总结集合是一种无序且唯一的数据结构ES6中有集合，名为Set集合常用操作：去重、判断某元素是否在集合中、求交集，差集
链表是什么？多个元素组成的列表元素存储不连续，用next指针连在一起数组 VS 链表数组：增删非首尾元素时往往需要移动元素链表：增删非首尾元素，不需要移动元素，只需要更改next指向即可JS中的链表JavaScript中没有链表可以用Object模拟链表Coding PartLeetCode #237 删除链表中的节点请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。现有一个链表 -- head = [4,5,1,9]，它可以表示为: 示例 1：输入：head = [4,5,1,9], node = 5输出：[4,1,9]解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.示例 2：输入：head = [4,5,1,9], node = 1输出：[4,5,9]解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9. 提示：链表至少包含两个节点。链表中所有节点的值都是唯一的。给定的节点为非末尾节点并且一定是链表中的一个有效节点。不要从你的函数中返回任何结果。解题思路：无法直接获取被删除节点的上个节点将被删除节点转移到下个节点即：如果要删除1节点 则需要先把9节点的值赋值给1节点，即4-5-9-9，然后删除最后一个节点 即 4-5-9解题步骤：将被删除的节点的值改为下个节点的值删除下个节点复杂度：时间复杂度O（1）空间复杂度O（1）/* * @param {ListNode} node * @return {void} Do not return anything, modify node in-place instead. */ var deleteNode = function(node) { node.val = node.next.val; node.next = node.next.next; // 删除一个节点即 将本来要删除的节点的指针 指向下个节点的下个节点。 };LeetCode #206 反转链表反转一个单链表。示例:输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL解题思路假如：反转两个节点：将n+1的next指向n假如：反转多个节点：双指针遍历链表，重复上述操作解题步骤：双指针一前一后遍历链表遍历过程中不断反转双指针复杂度：时间复杂度 O（n）空间复杂度 O（1）/** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { let p1 = head; let p2 = null; while(p1){ const temp = p1.next; p1.next = p2; p2 = p1; p1 = temp; } return p2; };LeetCode #83 删除排序链表中的重复元素给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。示例 :输入: 1->1->2输出: 1->2输入: 1->1->2->3->3输出: 1->2->3解题思路：因为 链表是有序的，所以重复元素一定相邻遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值解题步骤：遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值遍历结束以后，返回原链表的头部复杂度：时间复杂度：O（n）空间复杂度：O（1）/** * @param {ListNode} head * @return {ListNode} */ var deleteDuplicates = function(head) { let p = head; while(p && p.next){ if(p.val === p.next.val){ p.next = p.next.next; }else{ p = p.next; } } return head; };LeetCode # 141 环形链表给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。 否则，返回 false 示例一：输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点示例二：输入：head = [1,2], pos = 0输出：true解释：链表中有一个环，其尾部连接到第一个节点。示例三：输入：head = [1], pos = -1输出：false解释：链表中没有环。提示：链表中节点的数目范围是 [0, 104]-105 <= Node.val <= 105pos 为 -1 或者链表中的一个 有效索引 。解题思路:两个人在圆形操场上的起点同时起跑，速度快的人一定会超过速度慢的人一圈。用一快一慢两个指针遍历链表，如果指针能够相逢，那么链表就有圈解题步骤:用一快一慢两个指针遍历链表，如果指针能够相逢，就返回true遍历结束后，还没有相逢就返回false复杂度:时间复杂度 O（n）空间复杂度 O（1）/** * @param {ListNode} head * @return {boolean} */ var hasCycle = function(head) { let p1 = head; // 慢指针 let p2 = head; // 快指针 while(p1 && p2 && p2.next){ p1 = p1.next; p2 = p2.next.next; if(p1 === p2){ //两个指针相逢 return true; } } return false; };前端与链表：JS中的原型链原型链介绍原型链的本质是链表原型链上的节点是各种原型对象，比如Function.prototype、Object.prototype原型链通过_proto_属性连接各种原型对象原型链长啥样？obj -> Object.prototype -> nullfunc -> Function.prototype -> Object.prototype -> nullarr -> Array.prototype -> Object.prototype -> nullCoding Part原型链知识点如果A沿着原型链能找到B.prototype，那么A instanceof B 为true如果在A对象上没有找到x属性，那么会沿着原型链找x属性面试题一简述instanceof的原理，并实现知识点： 如果A沿着原型链能找到B.prototype，那么A instanceof B 为true解法：遍历A的原型链，如果找到B.prototype，返回true，否则返回false// 和遍历链表思路一样 const instanceOf = (A, B) => { let p = A; while(p){ if(p === B.prototype){ return true; } p = p.__proto__; } return false; }面试题二var foo = {}, F = function(){}; Object.prototype.a = 'value a'; Function.prototype.b = 'value b'; console.log(foo.a); console.log(foo.b); console.log(F.a); console.log(F.b);分析：知识点：如果在A对象上没有找到x属性，那么会沿着原型链找x属性解法：明确foo和F变量的原型链，沿着原型链找a属性和b属性。console.log(foo.a); // 'value a' console.log(foo.b); // 'undefined' console.log(F.a); // 'value a' console.log(F.b); // 'value b'前端与链表： 使用链表指针获取JSON的节点值const json = { a: { b: {c: 1} }, d: { e: 2 } } const path = ['d', 'e']; // 路径 // 和遍历链表异曲同工之妙 let p = json; path.forEach(k =>{ p = p[k]; }) // 路径：2链表--总结链表里的元素存储不是连续的，之间通过next链接JavaScript中没有链表，但可以用Object模拟链接链表常用操作：修改next，遍历链表JS中的原型链也是一个链表。沿着proto属性使用链表指针可以获取JSON的节点值阶段思考题：编写一个 instanceOf 方法，可以判断一个变量是否是另一个变量的实例。判断一个链表是否为回文链表。题目链接：https://leetcode-cn.com/problems/palindrome-linked-list/
队列是什么？一个先进先出的数据结构Javascript中没有队列，但可以用Array实现队列的所有功能 Coding Part什么场景用队列？需要先进先出的场景比如：电影院排队进场，JS异步中的任务队列，计算最近请求次数场景一、电影院排队进场先进先出，保证有序场景二、JS异步中的任务队列JS是单线程，无法同时处理异步中的并发任务使用任务队列先后处理异步任务 场景三、 计算最近请求次数输入一个数组，代表请求发起的时刻inputS = [[],[1],[100],[3001],[3002]] [null,1,2,3,3]有新请求就入队。3000ms前发出的请求出队队列的长度就是最近请求的次数LeetCode #933题最近的请求次数写一个 RecentCounter 类来计算特定时间范围内最近的请求。请你实现 RecentCounter 类：RecentCounter() 初始化计数器，请求数为 0 。int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。保证每次对 ping 的调用都使用比之前更大的 t 值。输入： ["RecentCounter", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]] 输出： [null, 1, 2, 3, 3] 解释： RecentCounter recentCounter = new RecentCounter(); recentCounter.ping(1); // requests = [1]，范围是 [-2999,1]，返回 1 recentCounter.ping(100); // requests = [1, 100]，范围是 [-2900,100]，返回 2 recentCounter.ping(3001); // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3 recentCounter.ping(3002); // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3 提示： 1 <= t <= 104 保证每次对 ping 的调用都使用比之前更大的 t 值 至多调用 ping 方法 104 次解题思路：越早发出的请求越早不在最近3000ms内的请求里满足先进先出，考虑用队列解题步骤：有新请求就入队，3000ms前发出的请求出队队列的长度就是最新请求的次数时间复杂度 O（n）空间复杂度 O（n）var RecentCounter = function() { this.queue = []; }; /** * @param {number} t * @return {number} */ RecentCounter.prototype.ping = function(t) { this.queue.push(t); while(this.queue[0] < t-3000){ this.queue.shift(); } return this.queue.length; };队列-总结队列是一个先进先出的数据结构JavaScript中没有队列，但是可以用Array实现队列的所有功能队列常用操作push、 shift、 queue[0]
栈是什么？一个后进先出的数据结构JavaScript中没有栈，但可以用Array实现栈的所有功能栈的应用场景需要后进先出的场景比如： 十进制转二进制，判断字符串的括号是否有效、函数的调用栈场景一、 十进制转二进制后出来的余数要先出来把余数依次入栈，然后再出栈，就可以实现余数倒序输出场景二、 有效的括号越靠后的左括号，对应的右括号越靠前左括号入栈，右括号出栈，最后栈空了就是合法的。场景三、 函数调用堆栈最后调用的函数，最先执行完成JS解释器使用栈来控制函数的调用顺序LeetCode #20题20 有效的括号给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。解题思路：对于没有闭合的左括号而言，越靠后的左括号，对应的右括号越靠前。满足后进先出，考虑用栈的思路步骤：新建一个栈扫描字符串。遇到左括号入栈，遇到和栈顶括号类型匹配的右括号出栈，类型不匹配直接判定为不合法最后栈控了合法，不空就不合法时间复杂度 O(n)空间复杂度 O(n)/** * @param {string} s * @return {boolean} */ var isValid = function(s) { if(s.length %2 === 1) { return false } const stack = []; for(let i = 0; i<s.length; i+=1){ const c = s[i]; if(c === '(' || c === '{' || c === '['){ stack.push(c); }else{ const top = stack[stack.length-1]; if( (top === '(' && c === ')') || (top === '{' && c === '}') || (top === '[' && c === ']') ){ stack.pop(); }else{ return false; } } } return stack.length === 0; };总结栈是一个后进先出的数据结构JavaScript中没有栈，但是可以用array实现栈的所有功能栈的常用操作： push、pop、stack[length-1]用ES6的class，封装一个stack类，包括push、pop、peek方法// 使用es6的class来封装一个stack类 class farkStack{ // 定义一个名字为Stack的类 constructor(){ this.dataStore = [] } push(item){ this.dataStore.push(item); } pop(){ return this.dataStore.pop(); } peek(){ // 探出 return this.dataStore[this.dataStore.length - 1]; } size(){ return this.dataStore.length; } clear(){ this.dataStroe = [] } }用栈这个数据结构，将100这个十进制数字转为2进制function switchBinary(decNum){ let stack = new farkStack(); while(decNum > 0){ stack.push(decNum % 2); decNum = Math.floor(decNum/2) } let binaryStr = '' while(stack.size() !== 0) { binaryStr += stack.pop() } return binaryStr; } switchBinary(125)