Data Structures & Algorithms

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. 由最小规模问题的解得

1. 回溯是什么 - 每一步都选择一条路出发，能进则进，不能进则退回上一步（回溯），换一条路再试 2. 八皇后问题 - 2.1. 思路 - 暴力法 - 从 64 个格子中选出任意 8 个格子摆放皇后，检查每一种摆法的可行性 - 一共有 种摆法 - 每一行只能放一个皇后，那么只有 种摆法 - 回溯+剪

1. DFS是什么 - 深度优先搜索，适用于字符串、数组、树，经常配合回溯.md使用 2. 字符串 2.1. 全排列 - 输入一个字符串，输出它的全排列 - 分析：使用树 - 2.1.1. 经典做法 2.1.2. 升级版 2.2. 组合 - 子集.md 3. 数组 3.1. 组合总和 - 组合总和.

1. 二分查找 在已排序的数组中，取中间值【middle】跟查找值【target】比较 - target = middle，那么就返回middle的位置 - target < middle的话，那么在数组左半部分继续查找 - target middle的话，那么在数组右半部分继续查找 2. 实现 2

1. 冒泡排序 有序的数组是不存在逆序对的，非有序的则存在逆序对，只需要把逆序对交换一下即可 - 多趟扫描 - 每趟相邻项比较，如果是逆序对那么交换位置 2. 特点 - 稳定性：稳定 - 时间复杂度：O（n²） - 空间复杂度：O（1） 3. 实现 3.1. 测试 4. 优化 - 如果某一趟中没有一