2020.04.03

1.存储方式

数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）

数组由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)

链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间

2.基本操作

  • 线性就是 for/while 迭代为代表
  • 非线性就是递归为代表

3.刷题路线

先刷二叉树

动态规划解题套路

递归算法的时间复杂度怎么计算？子问题个数乘以解决一个子问题需要的时间

  • 重叠子问题
  • 备忘录优化
  • 解法
    • 自上而下：递归
    • 自下而上：带dp数组的迭代
  • 状态转移方程 -（暴力解公式）

二维数组的遍历方式：

  • 正序
  • 倒叙
  • 斜序

回溯算法套路

解决一个回溯问题，实际上就是一个决策树的遍历过程 回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作

1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件

案例：

  • 全排列
  • N皇后

keyword:

  • 画决策树

二分法套路

  • 整体简单，但边界条件，细节很重要
  • 左边界和右边界搜索
  • 定义区间

滑动窗口套路

1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。