算法初步

排序

稳定是指关键字相同的记录在排序后保持原有相对次序不变, 只有在原有相对次序有意义时需要考虑.

排序算法	平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
快速排序	$O(n\log(n))$	$O(n\log(n))$	$O(n\log(n))$	$O(\log(n))$	不稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
堆排序	$O(n\log(n))$	$O(n\log(n))$	$O(n\log(n))$	$O(1)$	不稳定
插入排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(1)$	稳定
希尔排序	$O(n\log(n))$	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定
归并排序	$O(n\log(n))$	$O(n\log(n))$	$O(n\log(n))$	$O(n)$	稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(k)$	稳定
桶排序	$O(n+k)$	$O(n+k)$	$O(n^2)$	$O(n+k)$	稳定
基数排序	$O(nm)$	$O(nm)$	$O(nm)$	$O(n+m)$	稳定

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


#include <vector>
using namespace std;

// 数列最大值
template<typename Type>
static Type maximal(vector<Type>& arr) {
    Type max = arr[0];
    for (int i = 1; i <= arr.size() - 1; ++i) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

// 数列最小值
template<typename Type>
static Type minimal(vector<Type>& arr) {
    Type min = arr[0];
    for (int i = 1; i <= arr.size() - 1; ++i) {
        if (arr[i] < min) min = arr[i];
    }
    return min;
}

冒泡排序

每轮遍历时两两比较并交换.

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


template<typename Type>
static void bubble(vector<Type>& arr) {
    for (int i = 0; i < arr.size() - 1; ++i) {
        bool isSwapped = false; // 记录交换情况
        for (int j = 0; j < arr.size() - 1 - i; ++j){
            if (arr[j] > arr[j + 1]){ // 若条件改为">="则不再稳定
                swap(arr[j], arr[j + 1]);
                isSwapped = true; 
            }
        }
        if(!isSwapped) break; // 本轮没有交换说明已经有序
    }
}

快速排序(双路)

快速排序本质为比较交换排序.
分区中随机选择一个基准, 所有小于基准值的放在基准一侧, 大于基准值的放在另一侧, 退出时, 基准位于中间位置, 递归操作.

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


#include <random>
template<typename Type>
static void quickRecur(vector<Type>& arr, int left, int right){
    if (left >= right) return;
    random_device seed; ranlux48 engine(seed());
    uniform_int_distribution<> distrib(left,right);
    Type flag = arr[distrib(engine)];
    int head = left - 1, tail = right + 1;
    while (head < tail) {
        do head++; while(arr[head] < flag);
        do tail--; while(arr[tail] > flag);
        if (head < tail) swap(arr[head], arr[tail]);
    }
    quickRecur(arr, left, tail);
    quickRecur(arr, tail+1, right);
}
template<typename Type>
static void quick(vector<Type>& arr){
    quickRecur(arr, 0, arr.size()-1);
}

在重复值较多的场景下, 可以额外划分出一个区域将与基准值相等的元素聚集在基准值前后实现三路.
sort()方法以快速排序为主, 辅以插入排序和堆排序.

选择排序

遍历过程中依次选出末尾序列中的最值元素放到序列起始位置.

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


template<typename Type>
static void selection(vector<Type>& arr) {
    for (int i = 0; i < arr.size() - 1; ++i) {
        int min = i;
        for (int j = i + 1; j < arr.size(); ++j) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        } // 选出末尾序列中最小值
        swap(arr[i], arr[min]); // 交换到序列起始位置
    }
}

堆排序

堆排序本质为选择最值排序.
堆是一个完全二叉树, 大根堆指父节点值总大于(等于)子节点值, 小根堆指父节点值总小于(等于)子节点值.
以升序为例, 创建大根堆, 交换根(当前最大值)到叶末尾, 固定叶末尾, 其余部分变为大根堆(找出下一个最大值), 重复操作直至所有元素固定.

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


template<typename Type>
static void push(vector<Type>& arr, int start, int end) {
    int dad = start, son = dad * 2 + 1; // 父节点和左子节点, 右子节点为"dad * 2 + 2"
    while (son <= end) {
        if ((son + 1 <= end) && arr[son] < arr[son + 1]) ++son; // 选出子结点中较大的
        if (arr[dad] > arr[son]) return; // 父节点大于子节点, 已为大根堆
        else {
            swap(arr[dad], arr[son]); // 父节点小于等于子节点时, 互换
            dad = son;
            son = dad * 2 + 1; // 再依次将子堆调整为大根堆
        }
    }
}
template<typename Type>
static void heap(vector<Type>& arr){
    int size = arr.size();
    for (int i = size / 2 - 1; i >= 0; --i) {
        push(arr, i, size-1);
    } // 构造大根堆
    for (int i = size - 1; i > 0; --i) {
        swap(arr[0], arr[i]); // 交换当前末尾和根
        push(arr, 0, i-1); // 固定好的末尾以外部分调整为大根堆
    }
}

插入排序

遍历时将当前元素插入到前面队列的相应位置, 该位置及其后的元素依次后移.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


static void insertion(vector<Type>& arr) {
    for (int i = 1; i < arr.size(); ++i) {
        Type flag = arr[i]; // 记录当前元素
        int j = i - 1;
        while ((j >= 0) && (flag < arr[j])){
            arr[j + 1] = arr[j];
            --j;
        } // 找到位置时, 元素依次后移
        arr[j + 1] = flag;
    }
}

希尔排序

分割为若干子序列进行插入排序, 子序列有序后, 再合并进行插入排序, 循环操作.

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


template<typename Type>
static void shell(vector<Type>& arr) {
    int gap = 1;
    while (gap < arr.size() / 3){
        gap = 3 * gap + 1;
    } // 子序列分割数
    while (gap) {
        // 以gap为间隔的子序列分别进行插入排序
        for (int i = gap; i < arr.size(); ++i) {
            for (int j = i; (j >= gap) && (arr[j] < arr[j - gap]); j -= gap) {
                swap(arr[j], arr[j - gap]);
            }
        }
        gap /= 3;
    }
}

归并排序

临时空间存储两个有序序列之和用来存放合并排序后的序列, 依次比较两个有序序列元素并存入临时空间, 重复上述操作.

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


template<typename Type>
static void mergeRecur(vector<Type>& arr, int start, int end) {
    if (start >= end) return;
    int mid = ((end - start) >> 1) + start;
    mergeRecur(arr, start, mid); // 左有序序列
    mergeRecur(arr, mid + 1, end); // 右有序序列
    static vector<Type> tmp;
    tmp.clear();
    int left = start, right = mid + 1; // 两指针指向各自起始位置
    while ((left <= mid) && (right <= end)){
        if (arr[left] <= arr[right]) tmp.push_back(arr[left++]);
        else tmp.push_back(arr[right++]); // 较小的元素存入临时数组, 较小元素序列指针右移
    }
    while (left <= mid) tmp.push_back(arr[left++]);
    while (right <= end) tmp.push_back(arr[right++]); // 将剩余元素序列的元素依次存入临时数组
    for (Type i : tmp) arr[start++] = i;
}
template<typename Type>
static void merge(vector<Type>& arr){
    mergeRecur(arr, 0, arr.size()-1);
}

计数排序

非比较方式排序, 而是直接记录元素位置和个数并反向填充原数组, 只适用于整数排序.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


static void counting(vector<int>& arr) {
    int max = maximal(arr), min = minimal(arr), range = max - min + 1;
    static vector<int> cnt(range,0); // 用于记录的数组
    for (int i : arr) ++cnt[i - min]; // 记录元素相对位置及个数
    for (int i = 0, j = 0; i <= range - 1; ++i) {
        while (cnt[i]) {
            arr[j++] = i + min; // 反向填充原数组
            --cnt[i];
        }
    }
}

桶排序

减少计数排序浪费的空间, 使用映射函数(类似于Hash函数), 映射后分布均匀时效率最高, 桶内部使用插入排序.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


static void bucket(vector<int>& arr) {
    int max = maximal(arr), min = minimal(arr);
    int size = (max - min) / int(arr.size()) + 1, num = (max - min) / size + 1; // 确定桶容量和桶个数
    vector<int> buckets[num];
    for (int i = 0; i <= arr.size() - 1; ++i) {
        int idx = (arr[i] - min) / size; // 映射函数
        buckets[idx].push_back(arr[i]); // 元素入桶
        // 桶内使用插入排序
        for (int j = int(buckets[idx].size()) - 1; j > 0; --j) {
            if (buckets[idx][j] < buckets[idx][j - 1])
                swap(buckets[idx][j],buckets[idx][j - 1]);
        }
    }
    for (int i = 0, j = 0; i <= num - 1; ++i) {
        for (int k = 0; k <= int(buckets[i].size()) - 1; ++k)
            arr[j++] = buckets[i][k]; // 反向填充原数组
    }
}

基数排序

非比较方式排序, 将元素本身切分并逐部分比较, 除整数外, 还适用于特定格式的字符串和浮点数.

 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


static void radix(vector<int>& arr) {
    int max = maximal(arr), digit = 0, shift = 1, size = int(arr.size());
    while (max) {
        max /= 10;
        ++digit;
    } // 获取位数
    vector<int> tmp(size, 0);
    // 从低位开始排序
    for (int i = 0; i < digit; ++i) {
        vector<int> cnt(10,0);
        // 内部使用计数排序
        for (int j = 0; j < size; ++j) {
            int k = (arr[j] / shift) % 10;
            ++cnt[k];
        }
        for (int j = 1; j < 10; ++j) {
            cnt[j] = cnt[j - 1] + cnt[j];
        }
        for (int j = size - 1; j >= 0; --j) {
            int k = (arr[j] / shift) % 10;
            tmp[cnt[k] - 1] = arr[j];
            --cnt[k];
        }
        for (int j = 0; j < size; ++j) {
            arr[j] = tmp[j];
        }
        shift *= 10;
    }
}

衍生问题

逆序对数量: 在数组 $a[n]$ 中, 若 $0\leq i<j\leq n-1$ 且 $a[i] > a[j]$, 则有序对 $(a[i],a[j])$ 被称为逆序对, 现求数组中全部逆序对数量.
在归并过程中累加: “cnt += mid - left + 1;”

第 $k$ 大的数: 在不排列数组 $a[n]$ 情况下, 求数组中第 $1\leq k\leq n$ 大的数.
快排过程中, 若基准右侧元素个数超过 $k$ 则所求一定在右侧, 忽略左侧递归 - 时间复杂度为 $O(n)$.

线性表

指针实现链表(C)

以带哨兵节点(头节点)的单向链表为例, 目标为实现如下方法(部分参考C++ STL <list>容器和经典算法题):

 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


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

typedef int ValType;

typedef struct node {
    ValType val;
    struct node *next;
} Node, List;

List* init(void); // 初始化链表
bool empty(List* head); // 判断链表为空
void clear(List* head); // 清空链表
void destroy(List* head); // 销毁链表
int size(List* head); // 链表大小
bool traverse(List* head); // 遍历链表
 
void pushFront(List* head, ValType val); // 头插法
void pushBack(List* head, ValType val); // 尾插法
ValType popFront(List* head); // 头出法
ValType popBack(List* head); // 尾出法
ValType front(List* head); // 头部元素
ValType back(List* head); // 尾部元素
 
bool insert(List* head, int n, ValType val); // 指定位置插入元素
ValType get(List* head, int n); // 获取指定位置元素
int match(List* head, ValType val); // 寻找匹配的元素
ValType delete(List* head, int n); // 删除指定位置元素
ValType deleteReverse(List *head, int n); // 反序删除指定位置元素
 
bool resize(List* head, int n); // 重新设置链表大小
bool reverse(List* head); // 翻转链表
bool sort(List* head); // 链表排序
bool unique(List* head); // 删除有序链表中的重复元素
List* splice(List* dest, List* src); // 拼接两个链表
List* merge(List* src1, List* src2); // 合并两个有序链表

各方法的实现如下:

  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
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280


Node* newNode(ValType val);
void quickSort(ValType arr[], int left, int right);
 
Node* newNode(ValType val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->next = NULL;
    return node;
}
 
List* init(void) {
    List* head = newNode(-1);
    return head;
}

bool empty(List* head) {
    if (head->next == NULL) return true;
    return false;
}

// 保留头节点
void clear(List* head) {
    while (head->next) {
        List* curr = head->next;
        head->next = curr->next;
        free(curr);
    }
}

// 指针置空
void destroy(List* head) {
    List* curr = head;
    while (curr) {
        head = head->next;
        free(curr);
        curr = head;
    }
}
 
int size(List* head) {
    int cnt = 0;
    for (Node* curr = head->next; curr; curr = curr->next) ++cnt;
    return cnt;
}
 
bool traverse(List* head) {
    if (empty(head)) return false;
    for (Node* curr = head->next; curr; curr = curr->next) {
        printf("%d ", curr->val);
    }
    printf("\n");
    return true;
}

void pushFront(List* head, ValType val) {
    Node* curr = newNode(val);
    curr->next = head->next;
    head->next = curr;
}
 
// O(n)
void pushBack(List* head, ValType val) {
    Node* tail = head;
    while (tail->next) tail = tail->next;
    tail->next = newNode(val);
}
 
ValType popFront(List* head) {
    if (empty(head)) return -1;
    Node* curr = head->next;
    head->next = curr->next;
    ValType val = curr->val;
    free(curr);
    return val;
}

// O(n)
ValType popBack(List* head) {
    if (empty(head)) return -1;
    Node* prev = head;
    while (prev->next->next) prev = prev->next;
    ValType val = prev->next->val;
    free(prev->next);
    prev->next = NULL;
    return val;
}
 
ValType front(List* head) {
    if (empty(head)) return -1;
    return head->next->val;
}

// O(n)
ValType back(List* head) {
    if (empty(head)) return -1;
    Node* tail = head;
    while (tail->next) tail = tail->next;
    return tail->val;
}

// 遍历到满足条件的前一个节点
bool insert(List* head, int n, ValType val) {
    if (empty(head) || n < 1) return false;
    for (Node* prev = head; prev->next; prev = prev->next) {
        --n;
        if (n == 0) {
            Node* new = newNode(val);
            new->next = prev->next;
            prev->next = new;
            return true;
        }
    } return false;
}

ValType get(List* head, int n) {
    if (empty(head) || n < 1) return -1;
    for (Node* curr = head->next; curr->next; curr = curr->next) {
        --n;
        if (n == 0) {
            return curr->val;
        }
    } return -1;
}

int match(List* head, ValType val) {
    if (empty(head)) return -1;
    int cnt = 0;
    for (Node* curr = head->next; curr->next; curr = curr->next) {
        ++cnt;
        if (curr->val == val) return cnt;
    } return -1;
}

// 遍历到满足条件的前一个节点
ValType delete(List* head, int n) {
    if (empty(head) || n < 1) return -1;
    for (Node* prev = head; prev->next; prev = prev->next) {
        --n;
        if (n == 0) {
            Node* del = prev->next;
            prev->next = del->next;
            ValType val = del->val;
            free(del);
            return val;
        }
    } return -1;
}

// 双指针法
ValType deleteReverse(List *head, int n) {
    if (empty(head) || n < 1) return -1;
    Node* fast = head->next;
    for (int i = n - 1; i > 0; --i) {
        if (fast->next == NULL) return -1;
        fast = fast->next;
    }
    Node* slow = head;
    while (fast->next) {
        fast = fast->next;
        slow = slow->next;
    }
    Node* curr = slow->next;
    slow->next = curr->next;
    ValType val = curr->val;
    free(curr);
    return val;
}

// 遍历到满足条件的前一个节点
bool resize(List* head, int n) {
    if (empty(head) || n < 1) return false;
    for (Node* prev = head; prev->next; prev = prev->next) {
        --n;
        if (n == 0) {
            clear(prev->next);
            return true;
        }
    } return false;
}

// 三指针迭代法
bool reverse(List* head) {
    if (empty(head) || empty(head->next)) return false;
    Node *prev = NULL, *curr = head->next;
    while (curr) {
        Node* next = curr->next;
        curr->next = prev;
        prev = curr, curr = next;
    }
    head->next = prev;
    return true;
}

// 传入数组使用快排
bool sort(List* head) {
    if (empty(head) || empty(head->next)) return false;
    int arrSize = size(head);
    ValType* arr = (ValType*)malloc(sizeof(ValType) * arrSize);
    Node* curr = head->next;
    for (int i = 0; i < arrSize; ++i) {
        arr[i] = curr->val;
        curr = curr->next;
    }
    quickSort(arr, 0, arrSize - 1);
    curr = head->next;
    for (int i = 0; i < arrSize; ++i) {
        curr->val = arr[i];
        curr = curr->next;
    }
    free(arr);
    return true;
}

// 遍历到重复值出现的前一个节点
bool unique(List* head) {
    if (empty(head) || empty(head->next)) return false;
    Node* prev = head->next;
    while (prev->next->next) {
        if (prev->val > prev->next->val) {
            return false;
        } else if (prev->val == prev->next->val) {
            Node* curr = prev->next;
            prev->next = curr->next;
            free(curr);
        } else {
            prev = prev->next;
        }
    } return true;
}

List* splice(List* dest, List* src) {
    if (empty(dest)) return src;
    if (empty(src)) return dest;
    Node* tail = dest;
    while (tail->next) tail = tail->next;
    tail->next = src->next;
    return dest;
}

List* merge(List* src1, List* src2) {
    if (empty(src1)) return src2;
    if (empty(src2)) return src1;
    sort(src1), sort(src2);
    List* dest = init();
    Node *curr1 = src1->next, *curr2 = src2->next, *tail = dest;
    while (curr1 && curr2) {
        if (curr1->val < curr2->val) {
            tail->next = curr1;
            curr1 = curr1->next;
            tail = tail->next;
        } else {
            tail->next = curr2;
            curr2 = curr2->next;
            tail = tail->next;
        }
    }
    // 将剩余部分直接连接
    if (curr1) tail->next = curr1;
    if (curr2) tail->next = curr2;
    src1->next = NULL, src2->next = NULL;
    return dest;
}

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;
    srand(time(NULL));
    int idx = rand() % (left - right) + left;
    int flag = arr[idx], head = left - 1, tail = right + 1;
    while (head < tail) {
        do head++; while(arr[head] < flag);
        do tail--; while(arr[tail] > flag);
        if (head < tail) {
            int tmp = arr[head];
            arr[head] = arr[tail];
            arr[tail] = tmp;
        }
    }
    quickSort(arr, left, tail);
    quickSort(arr, tail + 1, right);
}

此外, 链表也可以双向, 循环, 无哨兵节点, 有尾指针等.

作为ADT的线性表

ADT(abstract data structure) 抽象数据结构.

线性表存储上一般使用STL容器(C++)/数组/链表.

线性表	头插/头出	尾插/尾出	插入/删除	访问
链表(无尾指针)	$O(1)$	$O(m)$	$O(n)$	$O(n)$
vector/数组	$O(m)$	$O(1)$	$O(m)$	$O(1)$

受限线性表: 栈(stack), 后进先出(LIFO); 队列(queue), 先进先出(FIFO).
栈的进栈(push)和出栈(pop)在同侧, 另一侧封住; 一个指针指向栈顶(top); 栈空时指针指向栈底(bot).
队列的入队(push)和出队(pop)在不异侧, 一个指针指向队首(front), 一个指针指向队尾(back); 队列空时, 队首和队尾指向相同.

对顶栈: 将两栈的栈顶相对, 一侧进栈时另一侧出栈.
单调栈: 栈内元素始终保持递增(递减); 出栈/入栈时遍历栈, 时间复杂度为 $O(m)$.

双端队列(double-ended queue): 队首队尾均可入队或出队.
优先队列(priority queue): 队列内元素始终保持递增(递减), 通常使用小根堆(大根堆)实现; 入队/出队时时调整堆, 时间复杂度为 $O(\log m)$.
循环队列: 并非ADT, 数组模拟队列的技巧, 通过循环移动队首队尾指针, 以 $O(1)$ 的时间复杂度实现入队和出队操作; 队尾(队首)指针或指向最后一个元素(第一个元素)或其后一位(后一位), 但不同实现判断为空和为满的条件有所不同.

STL中的线性表

容器	属性	实现	头插/头出	尾插/尾出	插入/删除	访问	遍历
array	顺序	连续内存	不支持	不支持	不支持	$O(1)$	正向/反向
vector	顺序	连续内存 capacity > size	$O(m)$	$O(1)$	$O(m)$	$O(1)$	正向/反向
list	顺序	双向循环链表	$O(1)$	$O(1)$	$O(n)$	$O(n)$	正向/反向
forward_list	顺序	单向链表	$O(1)$	$O(m)$	$O(n)$	$O(n)$	正向
deque	顺序	分段连续内存	$O(1)$	$O(1)$	不支持	$O(1)$	不支持
stack	适配器	默认底层为deque	出入栈 $O(1)$	不支持	不支持	不支持	不支持
queue	适配器	默认底层为deque	出队 $O(1)$	入队 $O(1)$	不支持	不支持	不支持
priority_queue	适配器	默认底层为vector大根堆	出队 $O(\log m)$	入队 $O(\log m)$	不支持	不支持	不支持

迭代器: iterator, reverse_iterator.
赋值方法: assign(), swap().
容量方法: size(), empty(), resize(), capacity(), reserve().
读取方法: at(), operator(), front(), back(), top().
增删方法: push_front(), pop_front(), push_back(), pop_back(), push(), pop(), insert(), erase(), remove(), clear().

衍生问题

双指针法

使用双指针同时遍历 (并剪枝), 以便将时间复杂度 $O(n^2)$ 降至 $O(n)$.
反转字符串, 翻转数组, 快速排序, 三数之和, 四数之和 - 头尾指针.
合并有序链表 - 两个头指针.
翻转单向链表 - 三指针迭代.
单向链表倒数第 $n$ 个节点, 链表相交, 环形链表, 删除数组中特定元素 - 快慢指针.

四数之和: 返回数组中和为 $s$ 的所有四个整数 (四元组不能重复) - 时间复杂度 $O(n^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


vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); ++i) {
        // 1级剪枝处理
        if (nums[i] > target && nums[i] >= 0) break;
        // 1级去重
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        for (int j = i + 1; j < nums.size(); ++j) {
            // 2级剪枝处理
            if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) break;
            // 2级去重
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            int left = j + 1, right = nums.size() - 1;
            while (right > left) {
                // 考虑溢出
                if ((long) nums[i] + nums[j] + nums[left] + nums[right] > target) --right;
                // 考虑溢出
                else if ((long) nums[i] + nums[j] + nums[left] + nums[right]  < target) ++left;
                else {
                    result.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});
                    // 三级去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    // 找到答案, 同时内收
                    right--; left++;
                }
            }
        }
    }
    return result;
}

环形链表: 返回链表中单环的入点 - 时间复杂度 $O(n)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


ListNode *detectCycle(ListNode *head) {
    ListNode* fast = head, slow = head;
    while(fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        // 快慢指针相遇处
        if (slow == fast) {
            ListNode* begin = head;
            ListNode* end = fast;
            while (begin != end) {
                // 环入口处
                begin = begin->next;
                end = end->next;
            }
            return begin;
        }
    }
    return NULL;
}

滑动窗口

满足条件的最小连续子串/子数组: 扩大窗口找到可行解, 缩小窗口优化可行解.
满足条件的最小连续子串/子数组: 扩大窗口直至不满足条件, 再进行移动.

最小连续子数组: 返回数组中和为 $s$ 的最小连续长度子数组 - 时间复杂度 $O(n)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


int minSubArrayLen(int target, vector<int>& nums) {
    int n = nums.size();
    if (n == 0) {
        return 0;
    }
    int ans = INT_MAX, left = 0, right = 0, sum = 0;
    while (right < n) {
        sum += nums[right];
        while (sum >= target) {
            ans = min(ans, right - left + 1);
            sum -= nums[left];
            ++left;
        }
        ++right;
    }
    return ans == INT_MAX ? 0 : ans;
}

最大连续 $1$ 数列: 0-1数列中最多可将 $k$ 个 $0$ 变为 $1$, 返回最长的连续 $1$ 子数列长度 - 时间复杂度 $O(n)$.

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


int findMaxConsecutiveOnes(int k, vector<int>& nums) {
    int ans = 0, left = 0, zeroNum = 0;
    for (int right = 0; right <= nums.size(); ++right) {
        if (nums[right] == 0) zeroNum++;
        while (zeroNum > k) {
            if (nums[left] == 0) zeroNum--;
            left++;
        }
        ans = max(ans, right - left + 1);
    }
    return ans;
}

四则运算

使用栈将中缀表达式变为后缀表达式: 优先级高于或等于栈顶符号(左括号)入栈, 优先级低于栈顶符号(右括号)时弹出栈顶元素, 直至高于或等于(弹出左括号)再入栈(右括号不入栈).

使用栈直接计算后缀表达式: 数字入栈, 遇到符号时弹出两个数字, 将运算结果入栈; 栈中最后只剩一个元素, 即为所求.

搜索

BFS(Breadth First Search): 广度优先搜索, 使用队列记录搜索结果; 当前节点出队, 当前节点的子节点入队.
DFS(Depth First Search): 深度优先搜索, 使用栈记录搜索结果; 节点入栈, 通过出栈实现回溯.

查找

顺序表

二分查找, 线性插值, Fibonacci

平衡树

指针实现AVL树(C)

最理想的平衡二叉树(左右子树深度差始终 $<1$), 但插入和删除时需要大量"旋转"(常数次), 平均时间复杂度为 $O(\log{n})$; 应用于windows内核.

目标为实现如下方法：

 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


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int ValType;

typedef struct node {
	ValType val;
	int height;
	struct node *left, *right;
} Node, Tree;

// 递归法实现: 前序, 中序, 后序遍历
void preorderTraverse(Tree *root);
void inorderTraverse(Tree *root);
void postorderTraverse(Tree *root);

// 迭代法 (栈) 实现: 前序, 中序, 后序遍历
void levelTraverse(Tree *root);
void preorderIteration(Tree *root);
void inorderIteration(Tree *root);
// 迭代法 (队列) 实现: 层次遍历
void postorderIteration(Tree *root);

Tree *insert(Tree *root, ValType val);
Tree *delete(Tree *root, ValType val);
Tree *destroy(Tree* root);

各方法具体实现如下：

  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
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274


// 定义循环双端序列及方法, 可兼顾栈与队列
#define MAXSIZE 1000

typedef struct {
	Node *arr[MAXSIZE];
	int front, back;
} Deque;

bool isDequeEmpty(Deque *deque) {
	return deque->front == deque->back;
}

Deque *initDeque(void) {
	Deque *deque = (Deque*) malloc(sizeof(Deque));
	deque->back = deque->front = 0;
	return deque;
}

void pushBack(Deque *deque, Node *node) {
	deque->arr[++deque->back] = node;
	if (deque->back == MAXSIZE - 1) deque->back = 0;
	if (deque->back == deque->front) exit(-1);
}

Node *popBack(Deque *deque) {
	if (isDequeEmpty(deque)) return NULL;
	Node *node = deque->arr[deque->back--];
	if (deque->back == -1) deque->back = MAXSIZE - 1;
	return node;
}

Node *popFront(Deque *deque) {
	if (isDequeEmpty(deque)) return NULL;
	Node *node = deque->arr[++deque->front];
	if (deque->front == MAXSIZE - 1) deque->front = 0;
	return node;
}

void preorderTraverse(Tree *root) {
	if (!root) return;
	printf("%d ", root->val);
	preorderTraverse(root->left);
	preorderTraverse(root->right);
}

void inorderTraverse(Tree* root) {
	if (!root) return;
	inorderTraverse(root->left);
	printf("%d ", root->val);
	inorderTraverse(root->right);
}

void postorderTraverse(Tree *root) {
	if (!root) return;
	postorderTraverse(root->left);
	postorderTraverse(root->right);
	printf("%d ", root->val);
}

// 后序遍历
Tree *destroy(Tree *root) {
	if (root) {
		destroy(root->left);
		destroy(root->right);
		free(root);
	}
	return NULL;
}

// 迭代法实现dfs, 本质为用栈模拟递归函数栈帧结构
void preorderIteration(Tree *root) {
	Deque *stack = initDeque();
	if (root) pushBack(stack, root);
	while (!isDequeEmpty(stack)) {
		Node *node = popBack(stack);
		if (node) {
			// 按照右, 左, 根, 空顺序入栈
			if (node->right) pushBack(stack, node->right);
			if (node->left) pushBack(stack, node->left);
			pushBack(stack, node);
			pushBack(stack, NULL);
		} else {
			node = popBack(stack);
			printf("%d ", node->val);
		}
	}
}

void inorderIteration(Tree *root) {
	Deque *stack = initDeque();
	if (root) pushBack(stack, root);
	while (!isDequeEmpty(stack)) {
		Node *node = popBack(stack);
		if (node) {
			// 按照右, 根, 空, 左顺序入栈
			if (node->right) pushBack(stack, node->right);
			pushBack(stack, node);
			pushBack(stack, NULL);
			if (node->left) pushBack(stack, node->left);
		} else {
			node = popBack(stack);
			printf("%d ", node->val);
		}
	}
}

void postorderIteration(Tree *root) {
	Deque *st = initDeque();
	if (root) pushBack(st, root);
	while (!isDequeEmpty(st)) {
		Node *node = popBack(st);
		if (node) {
			// 按照根, 空, 右, 左顺序入栈
			pushBack(st, node);
			pushBack(st, NULL);
			if (node->right) pushBack(st, node->right);
			if (node->left) pushBack(st, node->left);
		} else {
			node = popBack(st);
			printf("%d ", node->val);
		}
	}
}

void levelTraverse(Tree *root) {
	Deque *que = initDeque();
	if (root) pushBack(que, root);
	while (!isDequeEmpty(que)) {
		// 记录当前层节点数
		int size = (que->back + MAXSIZE - que->front) % MAXSIZE;
		for (int i = 0; i < size; ++i) {
			Node *node = popFront(que);
			printf("%d %d  ", node->val, node->height);
			if (node->left) pushBack(que, node->left);
			if (node->right) pushBack(que, node->right);
		}
		printf("\n");
	}
}

int maxi(int a, int b) {
	return a > b ? a : b;
}

int getHeight(Tree *root) {
	if (!root) return 0;
	return root->height;
}

// 平衡因子: 左子树高度 - 右子树高度
int getFactor(Tree *root) {
	return getHeight(root->left) - getHeight(root->right);
}

// 根据左右孩高度更新根高度
void updateHeight(Tree *root) {
	int hl = getHeight(root->left);
	int hr = getHeight(root->right);
	root->height = maxi(hl, hr) + 1;
}

// LL型, 即右旋
Tree *LLRotate(Tree *root) {
	Node *node = root->left;
	root->left = node->right; node->right = root;
	updateHeight(root); updateHeight(node);
	return node;
}

// RR型, 即左旋
Tree *RRRotate(Tree *root) {
	Node *node = root->right;
	root->right = node->left; node->left = root;
	updateHeight(root); updateHeight(node);
	return node;
}

// LR型, 即左孩左旋后根右旋
Tree *LRRotate(Tree *root) {
	root->left = RRRotate(root->left);
	return LLRotate(root);
}

// RL型, 即右孩右旋后根左旋
Tree *RLRotate(Tree *root) {
	root->right = LLRotate(root->right);
	return RRRotate(root);
}

// 插入时维护平衡
Tree *balanceInsert(Tree *root, ValType val) {
	if (root) {
		int factor = getFactor(root);
		if (factor > 1) {
			if (val < root->left->val) root = LLRotate(root);
			else if (val > root->left->val) root = LRRotate(root);
		}
		else if (factor < -1) {
			if (val < root->right->val) root = RLRotate(root);
			else if (val > root->right->val) root = RRRotate(root);
		}
	}
	return root;
}

Tree *insert(Tree *root, ValType val) {
	if (!root) {
		Node* node = (Node*) malloc(sizeof(Node));
		node->val = val, node->height = 1; // 叶子节点高度为1
		node->left = node->right = NULL; return node;
	}
	if (val < root->val) {
		root->left = insert(root->left, val);
		updateHeight(root); // 递归返回时更新根节点高度
		return balanceInsert(root, val); // 维护当前子树平衡
	}
	if (val > root->val) {
		root->right = insert(root->right, val);
		updateHeight(root);
		return balanceInsert(root, val);
	}
	return root;
}

// 删除时维护平衡
Tree *balanceDelete(Tree *root) {
	if (root) {
		int factor = getFactor(root);
		if (factor > 1) {
			int subFact = getFactor(root->left);
			 // 将中间情况并入操作较少的情况中
			if (subFact >= 0) root = LLRotate(root);
			else root = LRRotate(root);
		} else if (factor < -1) {
			int subFact = getFactor(root->right);
			if (subFact > 0) root = RLRotate(root);
			// 将中间情况并入操作较少的情况中
			else root = RRRotate(root);
		}
	}
	return root;
}

Tree *delete(Tree *root, ValType val) {
	if (!root) return NULL;
	if (val < root->val) {
		root->left = delete(root->left, val);
		updateHeight(root); // 递归返回时更新根节点高度
		return balanceDelete(root); // 维护当前子树平衡
	} else if (val > root->val) {
		root->right = delete(root->right, val);
		updateHeight(root);
		return balanceDelete(root);
	} else {
		Node *lc = root->left, *rc = root->right;
		if (!lc && !rc) { // 叶子节点
			free(root); return NULL;
		} else if (!lc) { // 只有右子树
			free(root); return rc;
		} else if (!rc) { // 只有左子树
			free(root); return lc;
		} else {
			Node *prcMin = root;
			if (prcMin->right->left) {
				prcMin = prcMin->right;
				while (prcMin->left->left) prcMin = prcMin->left;
			} // 找到后驱节点的父节点, 即右子树最小节点的父节点
			root->val = prcMin->left->val;
			free(prcMin->left);
			// 避免出现野指针
			prcMin->left = NULL; return root;
		}
	}
}

STL中的RB树 (未完)

弱平衡二叉树, 牺牲一定的查询性能减少插入和删除时的"旋转"次数; STL中的关联式容器均使用此结构; 应用于 Linux 内核.

2-3树: 存在2-节点(1值2孩)和3-节点(2值3孩); 向上生长.
平衡规则: 左右子树高度相等.
插入: 插入2-节点时变为3-节点; 插入3-节点时先变为4-节点, 4-节点向上分解为3个2-节点, 并将根2-节点向上插入, 直到树中无4-节点; 插入路径均为3-节点时, 树高度加 $1$.
删除: 3-节点可直接删除; 删除2-节点时将后驱节点逐个前移, 3-节点向下分解; 只剩2-节点时, 向上合并为3-节点, 树高度减 $1$.
问题: 需要维护3种不同节点, 维持平衡的转换较复杂.

LLRB树: 将2-3树中3-节点拆分为两个2-节点, 规定左侧节点为红色, 右侧节点及原本2-节点均为黑色, 红色节点不计入高度.
平衡规则: 红节点只会出现在左孩, 不会出现连续的红节点相连; 左右子树黑色高度相等.
插入(红色调整): 新节点总为红色; 红节点在右孩时, 左旋并调整颜色; 连续红节点相连时, 右旋并调整颜色; 左右孩均为红节点时, 颜色反转; 根节点设置为黑色.
删除(黑色调整): 红节点可直接删除; 删除黑节点时调整递归路径为红黑相间使得待删除黑节点变为红色, 递归返回时调整为平衡.

RB树: 将2-3-4树中3-节点拆分为红节点和黑节点, 4-节点拆分为2个红节点和黑节点, 红色结点不计入高度.
平衡规则: 根节点黑色; 红色节点左右两孩均为黑色; 左右子树黑色高度相等.

区间树:

关联式容器: 基于RB树; 存储key(键)或key-value(键值)对; 所有元素自动排序; key不能修改.
方法: iterator, insert(), erase(), find(), clear().
set: 不允许出现重复key.
multiset: 允许key冗余, find()返回找到的第一个.
map: 不允许出现重复key; 元素为pair类型; [] 可根据key读取value; value可修改.
multimap: 允许key冗余, find()返回找到的第一个.

索引与B+树 (未完)

持久化介质中, 同时需要大量查询和插入, 采用弱平衡 $n$ 叉树, 减少“旋转”和数据迁移次数; 在数据库索引和文件索引中广泛使用.

B树

B+树

LSM树

maple树

Hash表

回溯及衍生问题 (未完)

回溯是树形结构的遍历式查找.

二叉树属性/修改/构造 - 树的递归遍历方式.
叶子数/左下角值/路径总和 - 均可.
所有路径/翻转/构造/最大二叉树/合并二叉树 - 前序.
是否对称/最大深度/最小深度/节点数/是否平衡/公共祖先 - 后序.
二叉搜索树插入/删除/修剪/构造 - 前序.
二叉搜索树判断/最小绝对差/众数/转换为累加树 - 中序.

串

模式匹配

KMP算法

模式匹配: 在文本串中匹配第一次出现模式串的位置.
BF算法: 暴力匹配 - 时间复杂度 $O(nm)$.
KMP算法: 避免重复匹配; 前缀(next/prefix)数组记录模式串前后缀相等长度 - 即匹配不相等时应当回溯的位置 - 时间复杂度 $O(n+m)$, 空间复杂度 $O(m)$.

模式串"abcabdfabc"

“a”, next[0]=0; “ab”, next[1]=0; “abc”, next[2]=0;
“abca”, next[3]=1, 前后缀相等内容 - “a”;
“abcab”, next[4]=2, 前后缀相等内容 - “ab”;
“abcabd”, next[5]=0; “abcabdf”, next[6]=0;
“abcabdfa”, next[7]=1, 前后缀相等内容 - “a”;
“abcabdfab”, next[8]=2, 前后缀相等内容 - “ab”;
“abcabdfabc”, next[9]=3, 前后缀相等内容 - “abc”.

next数组: 0 0 0 1 2 0 1 2 3.
$-1$: -1 -1 -1 0 1 -1 0 1 2
右移: -1 0 0 0 1 2 0 1 2.
右移后 $+1$: 0 1 1 2 3 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


#include <string.h>

void getNext(const char str[], int next[], int len) {
	int j = 0;
	next[0] = 0;
	for (int i = 1; i < len; ++i) {
		while (j > 0 && str[i] != str[j]) j = next[j - 1];
		if (str[i] == str[j]) ++j;
		next[i] = j;
	}
}

int strStr(const char haystack[], const char needle[]) {
	int nLen = (int) strlen(needle), hLen = (int) strlen(haystack);
	if (nLen == 0) return 0;
	int next[nLen];
	getNext(needle, next, nLen);
	int j = 0;
	for (int i = 0; i < hLen; ++i) {
		while (j > 0 && haystack[i] != needle[j]) j = next[j - 1];
		if (haystack[i] == needle[j]) ++j;
		if (j == nLen) return (i - nLen + 1);
	}
	return -1;
}

FA (未完)

FA(Finite Automata) 有穷状态自动机

DFA, NFA

DFA(Deterministic): 相同的输入总是转移到相同的状态.
机制: 先看字符串再看正则表达式, 不会发生回溯, 即已经匹配过的字符不会匹配多次.
语言: MySQL, awk, egrep, flex, lex.

NFA(Nondeterministic): 相同输入可以转移到不同状态, 无输入时也可以转移状态.
机制: 先看正则表达式再看字符串, 会发生回溯, 速度较慢.
传统: 分支懒惰; Go, PCRE, Perl, PHP, Java, Python, Ruby, grep, less, more, .Net, vi.
POSIX: 分支贪婪; mawk.

贪婪与懒惰: 限定符默认为贪婪模式; 传统NFA默认为懒惰模式.

回溯陷阱: NFA实现的语言应当尽量避免回溯的发生以提高性能.

正则表达式

/pattern/flags: 匹配模式/修饰符

修饰符
: 默认只匹配第一个
g: 全局匹配
i: 不区分大小写
m: 多行匹配
s: 使 . 中包含\r\n
u: 能够正确处理UTF-16
y: 从剩余第一个位置开始匹配

转义符
\特殊字符: 转义字符, 匹配特殊字符自身

字符
普通字符: 匹配字符字面意义
\cx: 匹配x指向的控制符
\xn: 匹配16进制下ASCII编码中n指向的字符
\un: 匹配16进制下Unicode编码中n指向的字符
\f: 匹配换页符, 相当于\x0c和\cL
\n: 匹配换行符, 相当于\x0a和\cJ
\r: 匹配回车符, 相当于\x0d和\cM
\t: 匹配制表符, 相当于\x09和\cl
\v: 匹配垂直制表符, 相当于\x0b和\cK
\0: 匹配NULL, 相当于\u0000
[\b]: 匹配退格符, 相当于\u0008

字符类
[ ]: 匹配方括号内任意字符
[ - ]: 匹配方括号内字符范围
[^ ]: 匹配方括号内字符以外的字符
\d: 匹配任意数字, 等价于[0-9]
\D: 匹配任意非数字, 等价于[^0-9]
\s: 匹配任意控制符, 等价于[\f\n\r\t\v]
\S: 匹配任意非控制符, 等价于[^\f\n\r\t\v]
\w: 匹配任意数字字母下划线, 等价于[A-Za-z0-9_]
\W: 匹配任意非数字字母下划线, 等价于[^A-Za-z0-9_]
.: 通配, 等价于[^\r\n\u2028\u2029]

定位符
^: 匹配字符串开始位置
$: 匹配字符串结束位置
\b: 匹配单词边界
\B: 匹配非单词边界

量词：默认贪婪, 匹配尽可能多的字符
*: 匹配前面模式0次或多次
+: 匹配前面模式至少1次
?: 匹配前面模式至多1次
{n}: 匹配前面模式恰好n次
{n,}: 匹配前面模式至少n次
{n,m}: 匹配前面模式至少n次, 至多m次
?: 加在限定符后, 惰性, 匹配最少的字符

分组符
(exp): 分组并捕获子表达式exp
(?:exp): 分组但不捕获子表达式exp
(exp)\n: 分组并引用第n个捕获子表达式exp

断言符
exp1(?=exp2): 先行断言, 匹配在exp2前的exp1
exp1(?!exp2): 先行否定断言, 匹配不在exp2前的exp2
(?<=exp2)exp2: 后行断言, 匹配在exp2后的exp1
(?<!exp2)exp2: 后行否定断言, 匹配不在exp2后的exp2

分支符
|: 匹配前面模式或后面模式

优先级
转义符
字符类, 分组符, 断言符
量词
定位符, 字符
分支符

无损压缩 (未完)

游程编码 haffman 树 LZW 算法

作为String类的串

String类中方法时间复杂度基本均为 $O(n)$ 或 $O(m)$.
迭代器: iterator, reverse_iterator.
赋值方法: =, assign().
读取方法: [], at().
拼接方法: +, +=, append().
分割方法: split().
查找方法: find(), rfind().
替换方法: replace().
比较方法: compare(), <, <=, ==, >, >=, !=.
子串方法: substr().
增删方法: insert(), erase().
转换方法: c_str(), to_string(), stoi(), stol(), stoll(), stoul(), stoull(), stof(), stod(), stold().

衍生问题

串替换: 从后向前填充, 避免逐位移动 - 时间复杂度 $O(n)$.
串反转: 头尾双指针 - 时间复杂度 $O(n)$.
串循环移动: 先整体反转, 再部分反转 - 时间复杂度 $O(n)$.
向左循环移动 $m$ 位: 整体反转后, 前 $n-m$ 位和后 $m$ 位分别反转.
向右循环移动 $m$ 位: 整体反转后, 前 $m$ 位和后 $n-m$ 位分别反转.

重复子串: 非空字符串是否由一子串重复多次构成 - KMP算法, 时间复杂度 $O(n)$, 空间复杂度 $O(n)$.

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


void getNext (int* next, const string& s){
    next[0] = 0;
    int j = 0;
    for(int i = 1;i < s.size(); ++i){
        while(j > 0 && s[i] != s[j]) j = next[j - 1];
        if(s[i] == s[j]) ++j;
        next[i] = j;
    }
}

// 不妨设子串长度为m, 则有n=xm
// next数组即为0 0 ... 1  2 ... n-m
bool repeatedSubstringPattern (string s) {
    if (s.size() == 0) return false;
    int next[s.size()];
    getNext(next, s);
    int len = s.size();
    if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0)
        return true;
    return false;
}

反转串中单词: 反转串中由空格隔开的单词顺序 - 时间复杂度 $O(n)$, 空间复杂度 $O(1)$.

 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


// 整体反转
void reverse(string& s, int start, int end){
    for (int i = start, j = end; i < j; i++, j--)
        swap(s[i], s[j]);
}

// 快慢指针法去除多余空格
void removeExtraSpaces(string& s) {
    int slow = 0;
    for (int i = 0; i < s.size(); ++i) { //
        if (s[i] != ' ') {
            if (slow != 0) s[slow++] = ' ';
            while (i < s.size() && s[i] != ' ')
                s[slow++] = s[i++];
        }
    }
    s.resize(slow);
}

// 单词逐个反转
string reverseWords(string s) {
    removeExtraSpaces(s);
    reverse(s, 0, s.size() - 1);
    int start = 0;
    for (int i = 0; i <= s.size(); ++i) {
        if (i == s.size() || s[i] == ' ') {
            reverse(s, start, i - 1);
            start = i + 1;
        }
    }
    return s;
}

图

搜索: bfs, dfs, A*, 并查集

最小生成树: Prim, Kruskal

最短路径: Dijkstra, Floyd

拓扑排序, 关键路径

排序

冒泡排序

快速排序(双路)

选择排序

堆排序

插入排序

希尔排序

归并排序

计数排序

桶排序

基数排序

衍生问题

线性表

指针实现链表(C)

作为ADT的线性表

STL中的线性表

衍生问题

双指针法

滑动窗口

四则运算

搜索

查找

顺序表

平衡树

指针实现AVL树(C)

STL中的RB树 (未完)

索引与B+树 (未完)

Hash表

回溯及衍生问题 (未完)

串

模式匹配

KMP算法

FA (未完)

正则表达式

无损压缩 (未完)

作为String类的串

衍生问题

图

动态规划

复杂度陷阱