Algorithm

算法小抄笔记

Posted by QingJun's Blog on January 20, 2021

套路框架

数据结构

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

散列表、栈、队列、堆、树、图等等各种数据结构都是在数组和链表的基础上建立的

  • 队列、栈，数组和链表都可以实现，各有优缺点。

  • 图：邻接表，链表；邻接矩阵，二维数组。

  • 散列表

  • 树：完全二叉树/堆，数组；平常的树，链表。

数组和链表的优缺点：

  • 数组由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须⼀次性分配够，所以说数组如果要扩容，需要重新分配⼀块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插⼊和删除，每次必须搬移后⾯的所有数据以保持连续，时间复杂度 O(N)。
  • 链表因为元素不连续，⽽是靠指针指向下⼀个元素的位置，所以不存在数组的扩容问题；如果知道某⼀元素的前驱和后驱，操作指针即可删除该元素或者插⼊新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据⼀个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

对于任何数据结构，其基本操作⽆非遍历 + 访问，再具体⼀点就是：增删查改。

各种数据结构的遍历 + 访问无非两种形式：线性的和非线性的。

线性就是以 for/while 迭代为代表，非性就是以递归为代表。

数组遍历，线性遍历

1
2
3

for(int i = 0; i < nums.size(); i++){
    //...
}

链表遍历，线性遍历和递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13

class ListNode{
    int val;
    ListNode *next;
};
//线性遍历
for(ListNode *i = head; i != NULL; i = i->next){
    //...
}
//递归遍历
void traverse(ListNode *i){
    //...
    traverse(i->next);
}

二叉树遍历，递归遍历

1
2
3
4
5
6
7
8

class TreeNode{
    int val;
    TreeNode *left, *right;
};
void traverse(TreeNode *root){
    traverse(root->left);
    traverse(root->right);
}

二叉树

数据结构是⼯具，算法是通过合适的⼯具解决特定问题的方法。

⼆叉树是最容易培养框架思维的，⽽且⼤部分算法技巧，本质上都是树的遍历问题。

1
2
3
4
5
6
7

void traverse(TreeNode *root){
    //前序遍历
	traverse(root->left);
    //中序遍历
    treverse(root->right);
    //后序遍历
}

只要涉及递归的问题，都是树的问题。

动态规划

动态规划问题的⼀般形式就是求最值。求解动态规划的核⼼问题是穷举。

动态规划三要素：

  • 重叠子问题

    动态规划的穷举有点特别，因为这类问题存在「重叠⼦问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

  • 最优子结构

    动态规划问题⼀定会具备「最优⼦结构」，才能通过⼦问题的最值得到原问题的最值。

    要符合 「最优⼦结构」，⼦问题间必须互相独立。

  • 状态转移方程

    虽然动态规划的核⼼思想就是穷举求最值，但是问题可以千变万化， 穷举所有可⾏解其实并不是⼀件容易的事，只有列出正确的「状态转移⽅程」才能正确地穷举。

思考状态转移方程的思维框架：

明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。

斐波那契数列例子：

  • 如果用暴力递归写的话，实际上是一棵递归树，时间复杂度为 O(2^N)
  • 如果用「备忘录」来优化，实质上是将存在巨量冗余的递归树通过剪枝，变幻成了一幅不存在冗余的递归图。这样时间复杂度为 O(N)
  • 带备忘录的递归解法是自顶向下，也就是从递归树的根节点不断向上分解；迭代的动态规划解法是自底向上，从最小的问题不断向上推进
  • 很容易发现，其实状态转移⽅程直接代表着暴⼒解法。优化⽅法无非是⽤备忘录或者 DP table，再⽆奥妙可⾔。
  • 有时求解并不需要存储所有状态，只需要存储几个状态，可以进行优化从而降低空间复杂度

时间复杂度分析：子问题总数 * 每个子问题的时间

回溯/DFS

解决⼀个回溯问题，实际上就是⼀个决策树的遍历过程。只需要思考三个问题：

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

代码框架

1
2
3
4
5
6
7
8
9

result = []
def backtrack(路径，选择列表):
    if 满足结束条件
    	result.add(路径)
        return
   	for 选择 in 选择列表：
    	做选择
        backtrack(路径，选择列表)
        撤销选择

核⼼是 for 循环⾥的递归，在递归调⽤之前「做选择」，在递归调⽤ 之后「撤销选择」。

前序遍历部分的代码是在进入节点前执行；后序遍历部分的代码是在离开节点后执行

在回溯算法中，做选择是前序遍历部分代码，撤销选择是后序遍历部分的代码。我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径。

符合回溯框架，不管怎么优化，时间复杂度都不可能低于 O(N!)，因为穷举整棵决策树是⽆法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠⼦问题可以优化，回溯算法就是纯暴力穷举，所以复杂度⼀般都很⾼。

回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做⼀些操作。

动态规划的「状态」「选择」和 「base case」对应着回溯算法的「路径」「选择列表」和 「结束条件」。某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠⼦问题性质，可以用 dp table 或者备忘录优化，将递归树⼤幅剪枝，这就变成了动态规划。

BFS

问题的本质就是让你在⼀幅「图」中找到从起点 start 到终点 target 的最近距离。但这个⼴义的描述可以有各种变体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int BFS(Node start, Node target){
    queue<Node> q;//核心数据结构
    set<Node> visited;//避免走回头路
    q.push(start);//将起点加入队列
    visited.insert(start);
    int step = 0;//记录扩散的步数
    while(!q.empty()){
        int sz = q.size();
        //将当前队列中的所有节点向四周扩散
        for(int i = 0; i < sz; i++){
            Node cur = q.top();
            q.pop();
            //判断是否到达终点
            if(cur == target)
                return step;
            //将 cur 的相邻节点加入队列
            for(Node x : cur.adj())
                if(x not in visited){
                    q.push(x);
                    visited.insert(x);
                }
        }
        step++;//更新步数
    }
}

双向 BFS 优化

二分查找

滑动窗口

CATALOG
    FEATURED TAGS
    Leetcode C++
    FRIENDS