算法

为了获取生产环境报错对应的源码位置，之前将打包之后的 map 文件上传到 node 服务，日积月累之下，已经占用了好几个 g 的磁盘空间 就想到用 LRU 算法 的思想去对这些文件进行管理 LRU LRU 英文全称是 Least Recently Used，最不经常使用，是一种内存管理算法。可以参考 leetcode 的描述 LRU缓存机制 核心思想是 “如果数据最近被访问过,那么将来被访问的几率也更高”。所以在容量有限的情况下，淘汰最近最少使用的缓存。即近期内最不会被访问的数据进行淘汰 可以使用一个队列来缓存数据 如果有新数据插入，就移出队列中最后一个缓存 如果有数据访问，要将访问到的数据移到尾部，重新进行排序 实现 在 javascript 中，可以使用 Map 或者 Set 来模拟一个队列 import path from "path"; import fse from "fs-extra"; /** 上传 sourcemap 存放地址 */ export const sourcemapFilePath = path.join(__dirname, "../../../../uploads"); // 使用 LRU 算法去控制 sourcemap 文件 export class SourcemapCache { private path = path.join(__dirname, "cache.json"); private length: number; // 最大缓存数量 private cache: Set<string>; constructor(length = 10) { this....

题目 地址：https://leetcode.cn/problems/two-sum/ 思路 通过 Map 把数组的每一项进行缓存 （key 为数组中的项，value 为索引），然后再对数组进行遍历，并计算是否存在 key 相加等于目标值 遍历数组，判断差值是否存在 Map 中 如果存在，返回对应的索引 如果不存在，将这一项添加到 Map 中 数组遍历结束，返回一个兜底的数组 [-1, -1] /** * @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 item = nums[i]; const different = target - item; if (map.get(different) !== undefined) { return [map....

题目 地址：https://leetcode.cn/problems/fibonacci-number/ 解题 斐波那契数列的特点是由后两个数字相加得出下一个数字， 首先能想到的就是用递归来解决。 递归的出口是 F(0) = 0，F(1) = 1 找到出口之后就很简单了，三下五除二就写出来： var fib = function (n) { if (n <= 1) { return n; } function add(num) { if (num === 1 || num === 0) { return num; } else { return add(num - 1) + add(num - 2); } } return add(n); }; 愉快的提交之后， 嚯，击败了 14% 的提交。 优化 由于盲目的使用递归，造成了大量的重复操作，时间复杂度是 O(2^n)，指数级爆炸。 自顶而下 为了解决这些重复的操作，使用 memoization 的思想来对已计算的数据进行缓存。 下面来用 数组 实现一下：...