常规算法思想整理
滑动窗口法
滑动窗口法，也叫尺取法，可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。
由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。往往类似于“请找到满足 xx 的最 x 的区间(子串、子数组)的 xx”这类问题都可以使用该方法进行解决
一般使用双指针来维护滑块窗口，通常会设置一个左指针p1和一个右指针p2都指向0，[p1,p2],则为滑块维护的大小，滑块的移动规则可以根据题目自己定义，但每次移动都需要更新一次结果然后与旧的结果进行比较来决定是否更新记录
经典问题
- 无重复字符最长字串
- 得到 K 个黑块的最少涂色次数
双指针法
双指针法与滑动窗口法有异曲同工之处，都是维护两个指针。可以通过移动指针来不断减小问题规模。
经典问题
- 盛最多水的容器
中心扩散法
中心扩散法的思路是：遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远
当然回文串问题中存在奇偶串的问题，可能还需要从两个索引的中心位置开始扩散
时间复杂度一般为O(n^2)
经典问题
- 最长回文子串
哈希表
当存在多个未知变量的值需要被记录时，我们会使用哈希表，哈希表是一个十分方便的字典，可以帮助我们快速查找某个已经计算过的值
我们还可以用哈希表制作记忆化容器，当遇到某个需要复杂计算量的问题时（比如动态规划），我们可以使用参数命名问题的方式为当前问题命名，将第一次计算过的结果存入表中，当下次遇到重复问题时，先判断是否计算过，如果计算过直接取结果即可，这样便避免了重复计算的时间浪费
如果遇到多重循环结果有边界问题，哈希表还可以将几次的计算结果存储，通过初步计算结果再与后面的条件进行计算，这样便减少了因为问题规模扩大而造成的时间复杂度的扩大
经典问题
- 青蛙过河
- 保证文件名唯一
栈
具有记忆性，先进后出的特点。解决因符合特定条件而引发的递归问题，通常由一个指针维护列表即可。
经典问题
- 有效的括号
整型变量
整型变量的作用比布尔变量更有优势，当我们需要处理的问题存在三个或多个状态时，可以用整型变量来标识不同状态。
如以下三种状态可以用0，1，-1来记录。正状态(1)，负状态(0)，未处理状态(-1)。
当问题存在的状态是可枚举的时候，适当的引入整型变量记录状态是十分有效的。
经典问题
- 字符串转换整数 (atoi)
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 1300452403@qq.com
