Xuhao's Blog - 算法
type: channel
link: https://www.xuhao.club/algo/
items: 揭秘B站智能防挡弹幕的原理与实现
items: 进阶算法之排序和搜索
items: 数据结构（九）堆
items: 数据结构（八）图
items: 数据结构（七）树
items: 数据结构（六）字典
items: 数据结构（五）集合
items: 数据结构（四）链表
items: 数据结构（三）队列
items: 数据结构（二）栈

揭秘B站智能防挡弹幕的原理与实现
type: item
date: 2022-06-12T14:30:00+08:00
description: 相信大家一定都经常看视频，尤其是年轻人最爱的B站或者爱奇艺，腾讯等等长短视频。是当下民众快消文化的一种体现。近期有时间，给大家分享下智能防挡弹幕的实现及原理。希望大家能喜欢。

进阶算法之排序和搜索
type: item
date: 2022-01-29T16:34:00+08:00
description: 最近年底了，有点忙，拖更了一个月进阶算法之排序和搜索排序和搜索是什么？排序：把某个乱序的数组变成升序或者降序的数组搜索：找出数组中某个元素的下标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); // …

数据结构（九）堆
type: item
date: 2021-11-30T16:48:19+08:00
description: 堆是什么？堆是一种特殊的完全二叉树所有的节点都大于等于(最大堆)或小于等于（最小堆）它的子节点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个最大…

数据结构（八）图
type: item
date: 2021-09-24T19:54:00+08:00
description: 图是什么？图是网络结构的抽象模型，是一组由边连接的节点图可以表示任何二元关系，比如道路、航班。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+…

数据结构（七）树
type: item
date: 2021-08-27T15:36:00+08:00
description: 树是什么？一种分层数据的抽象模型前端工作中常见的树包括：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二叉树的先中后序遍历(非递归版)// 先序遍历（非递归版）核心思…

数据结构（六）字典
type: item
date: 2021-07-15T18:44:00+08:00
description: 字典是什么？与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储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[]} num…

数据结构（五）集合
type: item
date: 2021-03-31T15:30:00+08:00
description: 集合是什么？一种无序且唯一的数据结构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集合常用操作：去重、判断某元素是否在集合中、求交集，差集

数据结构（四）链表
type: item
date: 2021-01-31T23:32:00+08:00
description: 链表是什么？多个元素组成的列表元素存储不连续，用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],…

数据结构（三）队列
type: item
date: 2021-01-31T23:23:00+08:00
description: 队列是什么？一个先进先出的数据结构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]

数据结构（二）栈
type: item
date: 2020-12-30T20:03:00+08:00
description: 栈是什么？一个后进先出的数据结构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)