[数据结构与算法]算法套路汇总

链表

链表千万别递归，递归栈会导致你的空间复杂度无法做到O(1)

快慢指针

1. 判断是否有环
2. 一次遍历找到链中的倒数第几个点
3. 找到中间节点

空置头节点

????new一个空节点指向头节点可以有效的防止空指针报错

数组

前缀和数组

????new一个新数组preSum来存放之前数组nums（该数组不能被修改）的和preSum[i]=nums[i]+nums[i-1]。就可以通过preSum数组的加减快速求出原数组某个区间内元素的和。

进阶

1. 可以扩展到二维数组
2. 可以用哈希表来代替数组计算前缀和

差分数组

????类似于前缀和数组，new一个新数组diff来存放之前数组nums的差diff[i]=nums[i]-nums[i-1]。当需要频繁的改动nums中某个区间的值时只需要在对应的差分数组位置加减即可。diff[i]+1表示nums[i:]都加1。diff[i]+1&&diff[j]-1表示nums[i:j-1]都加1。

坑

????题目可能会花里胡哨导致你看不出这道题应该用差分数组来做。比如力扣1109. 航班预订统计。一般来说需要频繁的对数组的某个区间进行修改的都可以用差分数组来做。

二叉树

递归淦他！只要是个树，那基本上递归都比迭代写起来简单。

未完待续