算法问题的本质大多是解决穷举问题,主要可归纳为两点:
- 如何穷举
- 如何有技巧的穷举
困难的也是这两点,如何找到穷举解法,以及如何优化穷举解法,即有技巧的穷举
各种技巧的限制和运用
一、链表和数组
二分搜索
二分搜索只能运用在有序数组上
滑动窗口
滑动窗口的适用场景是必须要能明确什么时候应该扩大窗口,什么时候应该收缩窗口
回文串
如果要判断是否为回文串,则使用双指针从两端向中心检查;如果要查询回文子串,从中心向两端扩散。
注:Manacher算法更为精妙
前缀和
差分数组
二、二叉树
二叉树题目的递归解法可以分两类思路:第一类是遍历一遍二叉树得出答案,第二类是通过分解问题计算出答案,这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。
评论区