主要面向做题的总结和复习，因此不涉及初级内容

时空复杂度

数据结构复习

动态数组vector

尾部O1插入删除，中间On插入删除
支持随机访问（核心是连续的内存空间！）
扩缩容、搬移数据难

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
vector<int> v;
// 初始化一个大小为 n 的数组 nums，其值全都为 2
vector<int> nums(n, 2);

vector<int> v2(10);//初始化大小为10的vector
vector<int> v3(10, 1);//初始化大小为10，值为1的vector
vector<int> v4(v2);//拷贝v2
vector<int> v5(v2.begin(), v2.begin() + 3);//拷贝v2的前三个元素
vector<int> v6(a,a+3);//拷贝数组a的前三个元素

// 初始化一个二维 int 数组 dp
vector<vector<int>> dp;

// 初始化一个大小为 m * n 的布尔数组 dp，
// 其中的值都初始化为 true
vector<vector<bool>> dp(m, vector<bool>(n, true));

push_back(value)
pop_back()
insert(pos, value)    // pos为迭代器，如ans.begin() + 2
erase(pos)

// 遍历
for (int i = 0; i < v.size(); i++)
    cout << v[i] << endl;

环形数组 O(1) 增删头部元素
维护两个指针 start 和 end，start 指向第一个有效元素的索引，end 指向最后一个有效元素的下一个位置索引。即[start, end) 区间包含数组元素
当 start, end 移动超出数组边界（< 0 或 >= arr.length）时，我们可以通过求模运算 % 让它们转一圈到数组头部或尾部继续工作，这样就实现了环形数组的效果。

双链表list

O(1)插入删除，不支持随机访问，只能获取头尾元素
增删查改指定索引的元素O(n)，需要从头开始遍历到索引处拿到那个节点（优化：1. 哈希链表 2.跳表）
跳表：跳表相当于在原链表的基础上，增加了多层索引，每向上一层，索引节点的数量减少一半，索引的间隔变为 2 倍，索引的高度是 logN，所以跳表的查询时间复杂度是O(logN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
list<int> l;
front(),back()
push_back(1),pop_back();
push_front(2),pop_front();

auto it = l.begin();
// 移动到第二个位置
advance(it, 1);
// 删除第二个位置的元素
lst.erase(it);

// 遍历
for (auto it = l.begin(); it != l.end(); it++)
    cout << *it << endl;

栈队列stack,queue

1
2
3
push(1),pop();
stk.top();
q.front();

哈希表 unordered_map<K,V>

Map键值对是Java的接口。
根据底层实现不同：

  • HashMap的实现是基于哈希表，O(1)增删改查
  • 而TreeMap的实现是基于红黑树, O(logn)
  1. 哈希表O(1)增删改查，因为底层实现就是table数组，只是通过哈希函数把key映射到table数组的索引位置，然后在这个位置上存储value。使用拉链法、开放寻址法解决哈希冲突（冲突时同位置存多个、向下个位置存）。
  2. 哈希表底层就是操作一个数组，其主要的时间复杂度来自于哈希函数计算索引和哈希冲突。只要保证哈希函数的复杂度在 O(1)，且合理解决哈希冲突的问题，那么增删查改的复杂度就都是 O(1)。
  3. 哈希表中键的遍历顺序是不确定的，不能依赖哈希表的遍历顺序来编写程序。
    • key 在底层 table 数组中的分布是随机的，不像数组/链表结构那样有明确的元素顺序。
    • 哈希表会自动扩缩容，扩容时会重新计算哈希值，导致键值对的顺序发生变化。
  4. C++哈希表中，访问一个不存在的键会自动创建，值为默认。这一点和其他语言不同，需要格外注意。记住访问值之前要先判断键是否存在
1
2
3
4
5
6
7
8
9
10
11
12
// 初始化一个空的哈希表 map
unordered_map<int, string> hashmap;

// 直接用Key操作
hashmap[4] = "four";
hashmap.erase(4);

// c++20 判断键是否存在
if (hashmap.contains(4)) {
    cout << hashmap[4] << endl;
}

哈希集合 unordered_set

就是哈希表，只存key，不关心value，主要用于元素去重和O(1)增删查判断是否存在

用链表加强哈希表LinkedHashMap

有序哈希表，底层是哈希表+双向链表，有哈希表 O(1) 的增删查改效率，同时又可以像链表一样保持键的插入顺序。
抽象来看，哈希表本质上就是一个键值映射，链表本质上就是一个顺序存储元素的容器。现在我就是想让这个键值映射中的键按照插入顺序排列，怎么把哈希表和链表结合起来？
哈希表存<key,Node>，链表存Node，Node再存key和value。这样就可以从keyO(1)找到Node，因为拿到Node，所以在链表中增删也是O(1).

1
private final HashMap<K, Node<K, V>> map = new HashMap<>();

用数组加强哈希表

基于标准哈希表添加一个新的 randomKey() API，在 O(1) 的时间复杂度返回一个随机键：
用数组存储哈希表的键，用哈希表存储键值对。
但是remove()操作的时间复杂度是 O(n) 的，因为我们需要遍历数组找到要删除的键，然后将其与数组末尾的键交换位置，最后再删除它。
解决办法：哈希表记录每个Key在数组中的位置即<Key,数组下标索引>，数组存pair<Key,Value>这样就可以在 O(1) 的时间复杂度内找到要删除的键在数组中的位置，然后进行交换和删除操作。

1
2
3
4
5
// 存储 key 和 key 在 arr 中的索引
private final HashMap<K, Integer> map = new HashMap<>();

// 真正存储 key-value 的数组
private final ArrayList<Node<K, V>> arr = new ArrayList<>();

string

1
2
3
4
5
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址

二叉树

实现方式：

链式直接表示 val left right

1
2
3
4
5
6
7
8
9
10
// 基本的二叉树节点
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

邻接表实现

1
2
3
4
5
6
7
8
9
10
    1
   / \
  2   3
 /   / \
4   5   6

unordered_map<int, vector<int>> tree;
tree[1] = {2, 3};
tree[2] = {4};
tree[3] = {5, 6};

递归遍历DFS

1
2
3
4
5
6
7
8
9
10
11
12
// 二叉树的遍历框架
// 在前序、中序、后序遍历的位置加代码
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    traverse(root->left);
    // 中序位置
    traverse(root->right);
    // 后序位置
}

注：二叉搜索树（BST） 的中序遍历结果是有序的

层序遍历BFS

每次把队头元素拿出来，然后把它的左右子节点加入队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::queue<TreeNode*> q;
    q.push(root);
    // 每轮while循环对应处理一层节点
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        // 访问 cur 节点
        std::cout << cur->val << std::endl;
        
        // 把 cur 的左右子节点加入队列
        if (cur->left != nullptr) {
            q.push(cur->left);
        }
        if (cur->right != nullptr) {
            q.push(cur->right);
        }
    }
}

同时维护节点在第几层的写法：

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
26
27
28
29
30
void levelOrderTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    // 记录当前遍历到的层数（根节点视为第 1 层）
    int depth = 1;
    // 每轮while循环对应处理一层节点
    while (!q.empty()) {
       
        // 通过 sz = q.size() 固定当前层的节点数量，确保只处理当前层的所有节点。
        int sz = q.size();       
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            q.pop();
            // 访问 cur 节点，同时知道它所在的层数
            cout << "depth = " << depth << ", val = " << cur->val << endl;

            // 把 cur 的左右子节点加入队列
            if (cur->left != nullptr) {
                q.push(cur->left);
            }
            if (cur->right != nullptr) {
                q.push(cur->right);
            }
        }
        depth++;
    }
}

多叉树

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
26
27
28
29
class Node {
public:
    int val;
    vector<Node*> children;
};

// 二叉树的遍历框架
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    traverse(root->left);
    // 中序位置
    traverse(root->right);
    // 后序位置
}

// N 叉树的遍历框架
void traverse(Node* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    for (Node* child : root->children) {
        traverse(child);
    }
    // 后序位置
}

二叉搜索树BST ——TreeMap TreeSet

左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。

HashMap 底层把键值对存储在一个 table 数组里面
而 TreeMap 底层把键值对存储在一棵二叉搜索树的节点里面。
方法：

  • 增删改查：O(logn) 因为找到一个节点的时间复杂度是 O(logn)
  • 最大最小元素：O(logn)
  • 返回全部元素：利用BST中序遍历有序
  • rank：O(logn) 返回排名第 k 的元素 需要额外维护每个节点为根的子树的节点个数

注意，BST的增删改查操作都是 O(logn) 的时间复杂度，但是在极端情况下，BST 会退化成链表，此时时间复杂度会退化成 O(n)。因此引出平衡二叉树AVL树和红黑树。

Trie树

解决字符串相关问题。相同前缀的字符串不会重复存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 基本的多叉树节点
class TreeNode {
public:
    int val;
    vector<TreeNode*> children;
};

// Trie 树节点实现
template<typename V>
struct TrieNode {
    V val = NULL;
    TrieNode<V>* children[256] = { NULL };  
    // 这个 val 字段存储键对应的值，children 数组存储指向子节点的指针。
    //TrieNode 中 children 数组的索引是有意义的，代表键中的一个字符。
    // 比如说 children[97] 如果非空，说明这里存储了一个字符 'a'，因为 'a' 的 ASCII 码为 97。
};

二叉堆 ——一种能动态排序的数据结构

能动态排序的常用数据结构其实只有两个：
一个是优先级队列（底层用二叉堆实现），另一个是二叉搜索树。二叉搜索树的用途更广泛，优先级队列能做的事情，二叉搜索树其实都能做。但优先级队列的 API 和代码实现相较于二叉搜索树更简单，所以一般能用优先级队列解决的问题，我们没必要用二叉搜索树。

BST：左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。
二叉堆：堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。一般用于优先队列和堆排序。

主要操作就两个，sink（下沉）和 swim（上浮），用以维护二叉堆的性质。
二叉堆(优先队列)的插入和删除操作的时间复杂度都是 O(logn) 的，其中 n 是二叉堆中元素的个数。
堆排序相当于把一个乱序的数组都 push 到一个二叉堆（优先级队列）里面，然后再一个个 pop 出来，就得到了一个有序的数组。不过，正常的堆排序算法的代码并不依赖优先级队列，且空间复杂度是 O(1)，因为它把 push 和 pop 的代码逻辑展开了，再加上直接在数组上原地建堆，这样就不需要额外的空间了。

C++ STL的优先队列默认是最大堆（堆顶为最大元素），可以通过自定义比较函数来实现最小堆。

1

线段树

线段树是 二叉树结构 的衍生，用于高效解决区间查询和动态修改的问题，其中区间查询的时间复杂度为 O(logN)，动态修改单个元素的时间复杂度为 O(logN)。

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

class SegmentTree {
    // 构造函数，给定一个数组，初始化线段树，时间复杂度 O(N)
    // merge 是一个函数，用于定义 query 方法的行为
    // 通过修改这个函数，可以让 query 函数返回区间的元素和、最大值、最小值等
    public SegmentTree(int[] nums, Function<Integer, Integer> merge) {}
    
    // 查询闭区间 [i, j] 的元素和（也可能是最大最小值，取决于 merge 函数），时间复杂度 O(logN)
    public int query(int i, int j) {}
    
    // 更新 nums[i] = val，时间复杂度 O(logN)
    public void update(int i, int val) {}
}

因为不断把线段二分，所以线段树的高度是 O(logN)
查询 query 方法（找两个点）遍历的节点总数是 logN 的常数倍，时间复杂度是 O(logN)
更新 update （找叶子节点，并更新这条路径的值）的时间复杂度是 O(logN)

图

节点Vertex和边Edge的集合，可以用邻接矩阵或邻接表表示。

图的存储

alt text
alt text

邻接表：把每个节点 x 的邻居都存到一个列表里，然后把 x 和这个列表映射起来，这样就可以通过一个节点 x 找到它的所有相邻节点。

邻接矩阵则是一个二维布尔数组，我们权且称为 matrix，如果节点 x 和 y 是相连的，那么就把 matrix[x][y] 设为 true（上图中绿色的方格代表 true）。如果想找节点 x 的邻居，去扫一圈 matrix[x][..] 就行了。

注：有向加权图的实现：

如果是邻接表，我们不仅仅存储某个节点 x 的所有邻居节点，还存储 x 到每个邻居的权重，就实现加权有向图了。

如果是邻接矩阵，matrix[x][y] 不再是布尔值，而是一个 int 值，0 表示没有连接，其他值表示权重，就变成加权有向图了

对于无向图中的边ab，存储两条有向边a->b, b->a。因此只考虑有向图。

图的遍历

图的遍历就是 多叉树遍历 的延伸，主要遍历方式还是深度优先搜索（DFS）和广度优先搜索（BFS）。

唯一的区别是，树结构中不存在环，而图结构中可能存在环，所以我们需要标记遍历过的节点，避免遍历函数在环中死循环。

遍历图的「节点」和「路径」略有不同，遍历「节点」时，需要 visited 数组在前序位置标记节点；遍历图的所有「路径」时，需要 onPath 数组在前序位置标记节点，在后序位置撤销标记。

算法框架

链表双指针

  • 双指针：合并两个/k个有序链表
  • 快慢指针：slow走一步，fast走两步，判断链表是否有环，找到链表的中点，找到链表的倒数第 k 个元素
1
2
3
4
5
6
7
ListNode* fast = head;
ListNode* slow = head;
while (fast != nullptr && fast->next != nullptr) {
    fast = fast->next->next;
    slow = slow->next;
    if (fast == slow) break;
}

技巧：

  • 当需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。
1
ListNode dummy(0), *p = &dummy;
  • 创建新链表时，要正确终结链表，如果用原链表节点创建，要把最后一个结点的next设置为空指针。

反转链表

反转单链表

迭代法：每个节点修改 需要维护pre，cur，next三个指针。
注意技巧：

  1. 一旦出现类似 nxt.next 这种操作，就要条件反射地想到，先判断 nxt 是否为 null，否则容易出现空指针异常。
  2. 注意循环的终止条件。你要知道循环终止时，各个指针的位置，这样才能保返回正确的答案。如果你觉得有点复杂想不清楚，那就动手画一个最简单的场景跑一下算法，比如这道题就可以画一个只有两个节点的单链表 1->2，然后就能确定循环终止后各个指针的位置了。

递归法：递归函数的定义是：输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。
随后，当前指针后续为后面链表反转后的尾节点。所以，将这个尾节点的next指向当前节点，当前节点的next指向空，返回头节点。

数组双指针

  • 快慢指针：原地修改元素，fast指针在前面探查元素
  • 左右指针：二分。只要数组有序，就应该想到双指针技巧。

滑动窗口

初始化 left = right = 0,把索引左闭右开区间 [left, right) 称为一个「窗口」
通过扩大和缩小「窗口」来解决某些问题。
滑动窗口算法技巧主要用来解决子数组问题，比如寻找符合某个条件的最长/最短子数组。
滑动窗口并不能穷举出所有子串。
判断哈希表中元素是否存在应使用if(map.count(c))而不是if(map[c])，因为map[c]可能会创建新的键值对!

遇到子数组/子串相关的问题，你只要能回答出来以下几个问题，就能运用滑动窗口算法：

  1. 什么时候应该扩大窗口？
  2. 什么时候应该缩小窗口？
  3. 什么时候应该更新答案？
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
26
27
28
29
30
31
32
33
34
35
36
// 滑动窗口算法伪码框架
void slidingWindow(string s) {
    // 用合适的数据结构记录窗口中的数据，根据具体场景变通
    // 比如说，我想记录窗口中元素出现的次数，就用 map
    // 如果我想记录窗口中的元素和，就可以只用一个 int
    auto window = ...

    int left = 0, right = 0;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        window.add(c);
        // 增大窗口
        right++;

        // 进行窗口内数据的一系列更新
        ...

        // *** debug 输出的位置 ***
        printf("window: [%d, %d)\n", left, right);
        // 注意在最终的解法代码中不要 print
        // 因为 IO 操作很耗时，可能导致超时

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            window.remove(d);
            // 缩小窗口
            left++;

            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

二叉树与递归

递归算法：

  1. 首先，这个问题是否可以抽象成一棵树结构？如果可以，那么就要用递归算法了。
  2. 如果要用递归算法，那么就思考「遍历」和「分解问题」这两种思维模式，看看哪种更适合这个问题。
  3. 如果用「分解问题」的思维模式，那么一定要写清楚这个递归函数的定义是什么，然后利用这个定义来分解问题，利用子问题的答案推导原问题的答案；
  4. 如果用「遍历」的思维模式，那么要用一个无返回值的递归函数，单纯起到遍历递归树，收集目标结果的作用。

其实，「分解问题」的思维模式就对应着后面要讲解的 动态规划算法 和 分治算法，「遍历」的思维模式就对应着后面要讲解的
DFS/回溯算法。

algorithm

sort

用于数组，vector等具有随机存取特性的容器
默认以less作为比较函数，即从小到大排序
cmp比较函数的编写：return true时a排在b前面
可以重载<运算符，也可以重载()运算符

1
2
3
4
bool cmp(node a, node b)
{
    return a.length > b.length;//a比b长度大时a排在b前面
}

next_permutation

1
2
next_permutation(start, end);//在[start, end)区间内求下一个排列
next_permutation(a, a + n);//求a数组的下一个排列，长度为n