主要面向做题的复健
语法和STL
std
1
2
3
| ##include <bits/stdc++.h>
reverse(nums.begin(), nums.end());
string s = to_string(num);
|
struct
1
2
3
4
5
6
| struct Student {
string name;
int age;
float score;
}a,b;
Student c;
|
string操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include <string>
string s;
getline(cin, s);
s = "hello";
s += str;
s.length();
s.substr(start, length);
s.find(str,[pos]);
s.c_str();
isalnum(c);
isupper(c);
islower(c);
toupper(c);
|
动态数组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
26
27
| vector<int> v;
vector<int> nums(n, 2);
vector<int> v2(10);
vector<int> v3(10, 1);
vector<int> v4(v2);
vector<int> v5(v2.begin(), v2.begin() + 3);
vector<int> v6(a,a+3);
vector<vector<int>> dp;
vector<vector<bool>> dp(m, vector<bool>(n, true));
push_back(value)
pop_back()
insert(pos, value)
erase(pos)
for (int i = 0; i < v.size(); i++)
cout << v[i] << endl;
|
环形数组 O(1) 增删头部元素
当 start, end 移动超出数组边界（< 0 或 >= arr.length）时，我们可以通过求模运算 % 让它们转一圈到数组头部或尾部继续工作，这样就实现了环形数组的效果。
栈队列stack,queue
实际上可以用vector代替stack
1
2
3
| push(1),pop();
stk.top();
queue.front();
|
双向链表list
O(1)插入删除，不支持随机访问，只能获取头尾元素
增删查改指定索引的元素O(n)，需要从头开始遍历到索引处拿到那个节点（优化：1. 哈希链表 2.跳表）
跳表：跳表相当于在原链表的基础上，增加了多层索引，每向上一层，索引节点的数量减少一半，索引的间隔变为 2 倍，索引的高度是 logN，所以跳表的查询时间复杂度是O(logN)
1
2
3
4
5
6
7
8
9
10
11
12
13
| list<int> l;
front(),back()
push_back(1),pop_back();
push_front(2),pop_front();
auto it = l.begin();
lst.erase(it);
for (auto it = l.begin(); it != l.end(); it++)
cout << *it << endl;
|
哈希表 unordered_map<K,V>
Map键值对是Java的接口。
根据底层实现不同：
- HashMap的实现是基于哈希表，O(1)增删改查
- 而TreeMap的实现是基于红黑树, O(logn)
- 哈希表O(1)增删改查，因为底层实现就是table数组，只是通过哈希函数把key映射到table数组的索引位置，然后在这个位置上存储value。使用拉链法、开放寻址法解决哈希冲突（冲突时同位置存多个、向下个位置存）。
- 哈希表底层就是操作一个数组，其主要的时间复杂度来自于哈希函数计算索引和哈希冲突。只要保证哈希函数的复杂度在 O(1)，且合理解决哈希冲突的问题，那么增删查改的复杂度就都是 O(1)。
- 哈希表中键的遍历顺序是不确定的，不能依赖哈希表的遍历顺序来编写程序。
- key 在底层 table 数组中的分布是随机的，不像数组/链表结构那样有明确的元素顺序。
- 哈希表会自动扩缩容，扩容时会重新计算哈希值，导致键值对的顺序发生变化。
- C++哈希表中，访问一个不存在的键会自动创建，值为默认。这一点和其他语言不同，需要格外注意。记住访问值之前要先判断键是否存在
1
2
3
4
5
6
7
8
9
10
11
12
|
unordered_map<int, string> hashmap;
hashmap[4] = "four";
hashmap.erase(4);
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
|
private final HashMap<K, Integer> map = new HashMap<>();
private final ArrayList<Node<K, V>> arr = new ArrayList<>();
|
二叉树
链式直接表示 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 (!q.empty()) {
TreeNode* cur = q.front();
q.pop();
std::cout << cur->val << std::endl;
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);
int depth = 1;
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode* cur = q.front();
q.pop();
cout << "depth = " << depth << ", val = " << cur->val << endl;
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);
}
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;
};
template<typename V>
struct TrieNode {
V val = NULL;
TrieNode<V>* children[256] = { NULL };
};
|
堆 ——一种能动态排序的数据结构
能动态排序的常用数据结构其实只有两个：
一个是优先级队列（底层用二叉堆实现），另一个是二叉搜索树。二叉搜索树的用途更广泛，优先级队列能做的事情，二叉搜索树其实都能做。但优先级队列的 API 和代码实现相较于二叉搜索树更简单，所以一般能用优先级队列解决的问题，我们没必要用二叉搜索树。
BST：左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。
二叉堆：堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。一般用于优先队列和堆排序。
主要操作就两个，sink（下沉）和 swim（上浮），用以维护二叉堆的性质。
二叉堆(优先队列)的插入和删除操作的时间复杂度都是 O(logn) 的，其中 n 是二叉堆中元素的个数。
堆排序相当于把一个乱序的数组都 push 到一个二叉堆（优先级队列）里面，然后再一个个 pop 出来，就得到了一个有序的数组。不过，正常的堆排序算法的代码并不依赖优先级队列，且空间复杂度是 O(1)，因为它把 push 和 pop 的代码逻辑展开了，再加上直接在数组上原地建堆，这样就不需要额外的空间了。
C++ STL的优先队列默认是最大堆（堆顶为最大元素），可以通过自定义比较函数来实现最小堆。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| std::priority_queue<TypeName> q;
std::priority_queue<TypeName, Container> q;
std::priority_queue<TypeName, Container, Compare> q;
auto cmp = [](const std::pair<int, int> &l, const std::pair<int, int> &r) {
return l.second < r.second;
};
std::priority_queue<std::pair<int, int>,
std::vector<std::pair<int, int>>,
decltype(cmp)>
pq(cmp);
|
线段树
线段树是 二叉树结构 的衍生，用于高效解决区间查询和动态修改的问题，其中区间查询的时间复杂度为 O(logN)，动态修改单个元素的时间复杂度为 O(logN)。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class SegmentTree {
public SegmentTree(int[] nums, Function<Integer, Integer> merge) {}
public int query(int i, int j) {}
public void update(int i, int val) {}
}
|
因为不断把线段二分，所以线段树的高度是 O(logN)
查询 query 方法（找两个点）遍历的节点总数是 logN 的常数倍，时间复杂度是 O(logN)
更新 update （找叶子节点，并更新这条路径的值）的时间复杂度是 O(logN)
图
节点Vertex和边Edge的集合，可以用邻接矩阵或邻接表表示。
图的存储
1
2
3
4
5
6
7
|
vector<vector<int>> graph;
vector<vector<bool>> matrix;
|
图的遍历
图的遍历就是 多叉树遍历 的延伸，仍是DFS和BFS。区别是，图结构中可能存在环，所以需要标记避免遍历函数在环中死循环。
遍历图的「节点」和「路径」略有不同:
- 遍历「节点」时，需要 visited 数组在前序位置标记节点
- 遍历图的所有「路径」时，需要 onPath 数组在前序位置标记节点，在后序位置撤销标记。
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
37
38
39
40
41
42
43
44
45
46
47
48
|
class Node {
public:
int val;
std::vector<Node*> children;
};
void traverse(Node* root) {
if (root == nullptr) {
return;
}
std::cout << "visit " << root->val << std::endl;
for (auto child : root->children) {
traverse(child);
}
}
class Vertex {
public:
int id;
std::vector<Vertex*> neighbors;
};
void traverse(Vertex* s, std::vector<bool>& visited) {
if (s == nullptr) {
return;
}
if (visited[s->id]) {
return;
}
visited[s->id] = true;
std::cout << "visit " << s->id << std::endl;
for (auto neighbor : s->neighbors) {
traverse(neighbor, visited);
}
}
|
对于树结构，遍历所有「路径」和遍历所有「节点」是没什么区别的。而对于图结构，遍历所有「路径」和遍历所有「节点」稍有不同。
因为对于树结构来说，只能由父节点指向子节点，所以从根节点 root 出发，到任意一个节点 targetNode 的路径都是唯一的。换句话说，遍历一遍树结构的所有节点之后，必然可以找到 root 到 targetNode 的唯一路径：
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
|
std::list<Node*> path;
void traverse(Node* root, Node* targetNode) {
if (root == nullptr) {
return;
}
if (root->val == targetNode->val) {
std::cout << "find path: ";
for (auto node : path) {
std::cout << node->val << "->";
}
std::cout << targetNode->val << std::endl;
return;
}
path.push_back(root);
for (Node* child : root->children) {
traverse(child, targetNode);
}
path.pop_back();
}
|
而对于图结构来说，由起点 src 到目标节点 dest 的路径可能不止一条。我们需要一个 onPath 数组，在进入节点时（前序位置）标记为正在访问，退出节点时（后序位置）撤销标记，这样才能遍历图中的所有路径，从而找到 src 到 dest 的所有路径：
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
|
vector<bool> onPath(graph.size());
list<int> path;
void traverse(Graph& graph, int src, int dest) {
if (src < 0 || src >= graph.size()) {
return;
}
if (onPath[src]) {
return;
}
if (src == dest) {
cout << "find path: ";
for (auto it = path.begin(); it != path.end(); it++) {
cout << *it << "->";
}
cout << dest << endl;
return;
}
onPath[src] = true;
path.push_back(src);
for (const Edge& e : graph.neighbors(src)) {
traverse(graph, e.to, dest);
}
path.pop_back();
onPath[src] = false;
}
|
遍历所有路径的算法复杂度较高。
快速排序、快速选择、sort
1
2
3
4
5
| bool cmp(int a, int b) {
return a > b;
}
sort(nums.begin(), nums.end(), cmp);
|
算法框架
链表双指针
- 双指针：合并两个/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三个指针。
注意技巧：
- 一旦出现类似 nxt.next 这种操作，就要条件反射地想到，先判断 nxt 是否为 null，否则容易出现空指针异常。
- 注意循环的终止条件。你要知道循环终止时，各个指针的位置，这样才能保返回正确的答案。如果你觉得有点复杂想不清楚，那就动手画一个最简单的场景跑一下算法，比如这道题就可以画一个只有两个节点的单链表 1->2，然后就能确定循环终止后各个指针的位置了。
递归法：递归函数的定义是：输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。
随后，当前指针后续为后面链表反转后的尾节点。所以，将这个尾节点的next指向当前节点，当前节点的next指向空，返回头节点。
数组双指针
- 快慢指针：原地修改元素，fast指针在前面探查元素
- 左右指针：二分。只要数组有序，就应该想到双指针技巧。
滑动窗口
初始化 left = right = 0,把索引左闭右开区间 [left, right) 称为一个「窗口」
通过扩大和缩小「窗口」来解决某些问题。
滑动窗口算法技巧主要用来解决子数组问题，比如寻找符合某个条件的最长/最短子数组。
滑动窗口并不能穷举出所有子串。
判断哈希表中元素是否存在应使用if(map.count(c))而不是if(map[c])，因为map[c]可能会创建新的键值对!
遇到子数组/子串相关的问题，你只要能回答出来以下几个问题，就能运用滑动窗口算法：
- 什么时候应该扩大窗口？
- 什么时候应该缩小窗口？
- 什么时候应该更新答案？
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) {
auto window = ...
int left = 0, right = 0;
while (right < s.size()) {
char c = s[right];
window.add(c);
right++;
...
printf("window: [%d, %d)\n", left, right);
while (window needs shrink) {
char d = s[left];
window.remove(d);
left++;
...
}
}
}
|
二叉树与递归
递归算法：
- 首先，这个问题是否可以抽象成一棵树结构？如果可以，那么就要用递归算法了。
- 如果要用递归算法，那么就思考「遍历」和「分解问题」这两种思维模式，看看哪种更适合这个问题。
- 如果用「分解问题」的思维模式，那么一定要写清楚这个递归函数的定义是什么，然后利用这个定义来分解问题，利用子问题的答案推导原问题的答案；
- 如果用「遍历」的思维模式，那么要用一个无返回值的递归函数，单纯起到遍历递归树，收集目标结果的作用。
其实，「分解问题」的思维模式就对应着后面要讲解的 动态规划算法 和 分治算法，「遍历」的思维模式就对应着后面要讲解的
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;
}
|
next_permutation
1
2
| next_permutation(start, end);
next_permutation(a, a + n);
|
