ThinkerQAQ

3.Algorithms

Data Structures & Algorithms · 16 篇笔记

  1. 3.1 缓存替换策略historical

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

  2. 3.2 动态规划historical

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

  3. 3.3 贪心historical

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

  4. 3.4 分治historical

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

  5. 3.5 递归historical

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

  6. 3.6 回溯historical

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

  7. 3.7 DFShistorical

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

  8. 3.8 二分查找historical

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

  9. 3.9 冒泡排序historical

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

  10. 3.10 线性查找historical

    1. 线性查找 2. 实现 2.1. 测试

  11. 3.11 堆排序historical

    1. 堆排序 heap.md 建堆+删除 2. 特点 - 稳定性：不稳定 - 时间：O（nlogn） - 空间：O（1） 3. 实现 3.1. 测试 4. 参考 - 排序算法稳定性\ 百度百科 - 堆排序 \- 维基百科，自由的百科全书

  12. 3.12 归并排序historical

    1. 归并排序 采用了分而治之的思想，就是说把一个大的问题分成小的问题，然后递归求解 不停地把数组拆成两半，直到有序（只有一个节点），最后进行合并 如果说快速排序的关键在于分，那么归并排序的关键在于合 2. 特点 - 稳定性：稳定 - 原地排序：不是 - 复杂度 - 时间：O（nlogn） - -

  13. 3.13 插入排序historical

    1. 插入排序 把数组分成有序和无序的部分，从无序部分取出每一个元素插入到已排好序的数组中 在数组相对有序的情况下效率比选择排序高，时间复杂度O（N） 2. 特点 - 稳定性：稳定 - 原地排序 - 空间复杂度：O（1） - 时间复杂度：O（n²） 3. 过程 4. 实现 4.1. 测试 5. 参考

  14. 3.14 快速排序historical

    1. 快速排序 采用了分而治之的思想，就是说把一个大的问题分成小的问题，然后递归求解 快速排序想选取一个pivot，比他小的移动到左边，比他大的移动到右边， 对左边的小数组和右边的小数组做同样的处理 如果说归并排序的关键在于合并，那么快速排序的关键在于拆分 2. 效率 - 稳定性：不稳定 - 原地排

  15. 3.15 选择排序historical

    1. 选择排序 遍历的时候寻找最大的值，完成遍历后把他放在合适的位置。 相对于冒泡排序来说减少了交换的次数 2. 特点 - 稳定性：不稳定 - 原地排序 - 时间复杂度：O（n²） - 空间复杂度：O（1） 3. 过程 4. 实现 4.1. 测试 5. 参考 - 排序算法稳定性\ 百度百科

  16. 3.16 排序historical

    1. 常见排序算法 1.1. 冒泡排序 - 冒泡排序.md 1.2. 选择排序 - 选择排序.md 1.3. 插入排序 - 插入排序.md 1.4. 归并排序 - 归并排序.md 1.5. 快速排序 - 快速排序.md 1.6. 堆排序 - 堆排序.md 2. 排序对比 时间复杂度 空间复杂度 是否