Data Structures & Algorithms

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. 优化 - 如果某一趟中没有一

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

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

下一个排列 的 LeetCode 解题笔记。

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

全排列 的 LeetCode 解题笔记。

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