Data Structures & Algorithms

最长无重复子串 的 LeetCode 解题笔记。

1. 什么是稀疏索引 - 首先他是个索引 - 索引.md - 其次他是稀疏的 - 稀疏索引和密集索引的区别在于是否为每个key都建立索引 2. 为什么需要稀疏索引 稀疏索引占用空间小 2.1. 稀疏索引 vs 密集索引 稀疏索引 密集索引 ------------------ -----------

1. 索引是什么 - 索引是一种把查找关键字和对应的数据记录关联起来（可以看作key-value对）的数据结构 - 索引查找是通过索引来查找数据 2. 为什么需要索引 - 用来加速数据的查找 3. 稀疏索引 vs 稠密索引 - 稀疏索引.md 4. 正排索引 vs 倒排索引 - 倒排索引.md 5.

1. 正排索引 文档Id- 文档 ，比如MySQL 1.1. 如何查找包含关键词的文档 1. 需要遍历所有文档 【O(N)】 2. 逐字逐字匹配 【O(m+n)】 2. 倒排索引 关键词- 文档Id + 文档Id- 文档 ，比如ES 先把文档分词，然后记录分词以及对应文档Id的映射，同时记录文档ID

1. 是什么 缓存能提高查找效率，但是缓存空间是有限的，需要把用不到的数据淘汰出缓存 2. 分类 2.1. FIFO 2.1.1. 是什么 First In First Out：优先淘汰最早进入被缓存的数据 2.1.2. 实现 队列即可 2.2. LRU 2.2.1. 是什么 Least Recen

1. 动态规划步骤 1. 递归+记忆化- 递推 2. 状态的定义： opt[n],dp[n],fib[n] 3. 状态转移方程： opt[n]=best of(opt[n-1], opt[n-2], ...) 4. 最优子结构 2. 例子 2.1. 路径数目计算 - 递归 - - 递推 - -

1. 是什么 - 每一步都采取当前状态下的最优选择（局部最优解），从而希望推导出全局最优解 2. 举例 2.1. 最优装载 2.1.1. 思路 - 每次都选择重量最小的装上船 2.1.2. 实现 2.1.2.1. 测试 2.2. 零钱兑换 - 假设有 25 分、10 分、5 分、1 分的硬币，现要找

1. 是什么 - 将原问题分解成若干个规模较小的子问题（子问题和原问题的结构一样，只是规模不一样） - 子问题又不断分解成规模更小的子问题，直到不能再分解（直到可以轻易计算出子问题的解） - 利用子问题的解推导出原问题的解 1.1. 递归 - 分治适合用递归实现，复杂度分析使用主定理 - - 递归.

1. 递归是什么 - 函数自己调用自己 2. 递归的调用过程 - 以求和函数为例 - 测试 - 过程分析 3. 递归基本思想 1. 拆解问题 1. 把规模大的问题拆成规模较小的问题 2. 规模较小的问题拆成规模更小的问题 3. 规模小到一定程度可以直接得出答案 2. 求解 1. 由最小规模问题的解得

编辑距离 的 LeetCode 解题笔记。