为什么需要缓存 # 减少不必要的网络请求，提升页面访问速度 减少服务器负载 节省网络开销(流量) 缓存工作机制 # 通过 http 请求头及 http 响应头来控制 缓存类型 # Private cache # 私有缓存：特定端的缓存，例如用户的浏览器 Shared cache # 源站和客户端之间的缓存，proxy cdn 等 Heuristic cache # 启发式缓存 http 的设计是能缓存尽量缓存，http 客户端根据 http 响应头自行决定缓存行为 缓存相关 header # Cache-Control # 缓存控制响应头, HTTP/1.1 引入 max-age 能存活多久(单位秒), 例： max-age=3153000 s-maxage 跟 max-age 类似，作用于共享缓存，当这个存在时会忽略 max-age private 仅允许端(浏览器)缓存，私有缓存 ...
Least recently used cache # 最近 最少 使用的缓存 解法： 双链表 + hash 表 /** * Least Recently Used cache * Get: O(1), hash 表 * Put: O(1)，需要维持顺序，最近最少使用的节点要删掉 * * 双向链表 */ class LRUCache { constructor(capacity) { // 当前元素数量 // 容量上限 this.capacity = capacity; /** @type {{[index: number]: LinkedListNode}} */ this.cache = {}; // 当前容量 this.size = 0; // 伪头结点 this. ...
组合 # 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 1 <= n <= 20 1 <= k <= n 题解 # /** * n 选 k 共有多少个组合情况 * @param {number} n * @param {number} k */ const combine = (n, k) => { const ans = []; /** * @param {number} k 子集的元素数 * @param {number} start 从第几个开始选 * @param {number} list 子集数组 */ const getCombine = (k, start, list) => { if (k === 0) { // 选满了 ans. ...
SOLID 原则 # S # Single Responsibility Principle， 单一职责原则 O # Open-Closed Principle，对拓展开放，对修改关闭 L # Liskov Substitution，里氏替换原则 I # Interface Segregation，接口隔离 D # Dependency Inversion Principle，依赖倒置原则 依赖抽象的接口，而不是具体的实现 DRY 原则 #
Babel # @babel/core #
配置1 # 配置结构 工作过程 # 根据入口文件构建依赖图 处理依赖图里的所有资源 生成 js bundle，清单文件 Loader # 将任意类型文件转译为 JavaScript 代码 常见资源处理 # Typescript babel-loader 加上 @babel/preset-typescript 规则集 缺点： 无类型校验 module.exports = { /* ... */ module: { rules: [ { test: /\.ts$/, use: [ { loader: 'babel-loader', options: { presets: ['@babel/preset-typescript'], }, }, ], }, ], }, }; CSS ...
Collision # 冲突： H(k1) = H(k2) 冲突解决方案 # Chaining # Open Addressing #
定义 # G = (V, E)， V 为非空顶点集，E 为边的集合 Directed Graph # 有向图 边 （u, v), u -> v ， v 跟 u 相邻 没有自循环的有向图是 简单有向图 Undirected Graph # 无向图 无向图不允许自循环 Degree # 度 In Degree # 入度 Out Degree # 出度: Path # <v0, v1, … , vk> v0 -> vk 的顶点的一个序列 长度： 路径中边的数量 Simple Path # 路径中所有的顶点都是不同的 Cycle # Edge # (u, v), 有向图中 (u, v) , (v, u) 是不一致的 ...
Singly linked list # 单链表 时间复杂度 # Access Search Insertion Deletion O(n) O(n) O(1) O(n) 注： 插入操作仅为在给定节点 Node 的指针 P 的前提下，在其后面插入一个节点，此时复杂度为 O(1)，若在 P 前面插入一个节点，则复杂度为 O(n), 因为需要遍历 Doubly linked list # 双链表 优点： # 可以双向遍历 删除操作更高效(O(1))，在已知给定节点的指针的前提下 插入操作 (O(1)) 缺点： # 额外的空间开销，用来存指针 所有操作需要维持两个指针的指向 时间复杂度 # Access Search Insertion Deletion O(n) O(n) O(1) O(n) / O(1) 注：如果需要遍历节点，则删除的时间复杂度为 O(n)
算法正确性证明 # 算法正确：对每一个正确输入，都能得到正确的解 证明步骤 # 证明程序终止时，能获得正确的解，(部分正确） 证明程序始终会终止 初始断言： 程序输入值具有的属性；结果断言： 程序输出值具有的属性 Hoare triple: p{S}q if p true and S terminates, q true, then S is partially correct