基础思想

文章目录

1. 1. 剪枝
2. 2. 枚举/遍历
3. 3. 递归
4. 4. 回溯
5. 5. 分治
6. 6. 贪心
7. 7. 动态规划
8. 8. 双指针

剪枝

通过if之类的判断去除算法中一些不必要的计算

枚举/遍历

递归

回溯

比如深度遍历走迷宫，先试探走，不行再往回走，“往回走”的过程叫做回溯

分治

将问题分解为2~3个子问题，再用递归解决，比如归并排序的递归实现（先拆分数组元素为有序数组，再组装有序数组）

贪心

每一步最优，则全局最优；贪心例题里面即使知道要用贪心算法，还是需要一些特别的技巧

动态规划

状态，转移方程／递推公式；空间换时间；开一个内存空间，将结果记录下来，以便后续复用；

双指针

• 二分法
• 夹：快排
• 滑动窗口：字符串>子串
• 快慢指针：验证环形链表