算法笔记学习记录
ZOU
 2021-05-05 11:33:17      10k 字  48 分钟  

排序

插入排序

插入排序的思想是从第一个数开始逐渐扩大已排序序列，具体实现是将某个数与已排序序列中的数比较，决定其在排好序的序列中位置。

1
2
3
4
5
6
for (int i = 1; i < n; i++) {
    for (int j = i - 1; j >= 0 && a[j] > a[j+1]; j—-) {
        swap(a[j], a[j+1]);
    }
    // ...
}

冒泡排序

冒泡排序的思想是相邻两个之间比较然后交换，一轮下来可以确定最后一个数的位置（注意不论是递增还是递减，都是先确定最后一个数），然后依次向前敲定。

1
2
3
4
5
6
7
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - i; j++) {
        if (a[j] > a[j+1]) {
            swap(a[j], a[j+1]);
        }
    }
}

递归

要理解递归，首先你要理解递归，直到你能理解递归（笑）。

全排列

输入一个整数n，给出1～n这n个整数的全排列，要求按照字典序从小到大排列。

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
#include <iostream>
using namespace std;

const int maxn = 11;
int n, p[maxn];
bool hashTable[maxn] = {false};

void generateP(int index) {
    if(index > n) {
        for(int i = 1; i <= n; i++) {
            printf("%d", p[i]);
        }
        printf("\n");
        return;
    }
    for(int i = 1; i <= n; i++) {
        if(hashTable[i] == false) {
            hashTable[i] = true;
            p[index] = i;
            generateP(index + 1);
            hashTable[i] = false;
        }
    }
}

int main() {
    n = 3;
    generateP(1);
    
    return 0;
}

不可以将代码中的generateP(index + 1)改成index++ + generateP(index)，因为index表示下标，当没有深入到下一层递归时，index不应该改变。

N皇后（回溯法)

N皇后基础算法在全排列的基础上进行改进，可看作不在对角线上的全排列。回溯法更优的地方在于：在放置了一部分皇后之后，可判断剩下的皇后是否有必要放下去，当无论怎么放都会冲突时则没必要递归，直接返回上层即可。

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
#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 1010;
int p[MAXN], n, count = 0; //p为暂时储存序列的数组，n为最大值
bool hashTable[MAXN] = {false};
void nQueen(int index) {
    if (index == n + 1) {
        count++;    //当能够进入这里，说明一定是合法序列
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (hashTable[i] == false) {
            bool flag = true;
            for (int pre = 1; pre < index; pre++) {
                if (abs(index - pre) == abs(i - p[pre])) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                hashTable[i] = true;
                p[index] = i;
                nQueen(index + 1);
                hashTable[i] = false;
            }
        }
    }
}
int main() {
    scanf("%d", &n);
    nQueen(1);
    printf("%d", count);
    return 0;
}

贪心

简单贪心没有固定的写法，视题目而定，下面给出区间贪心的做法

区间贪心

给出n个区间(x, y)，从中选择尽可能多的开区间，使得这些开区间两两没有交集，求出最大的开区间数。

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
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 10;  //表示最大区间数
struct Interval {
    int x, y;
} I[MAXN];
bool cmp(Interval a, Interval b) {
    if (a.x != b.x) return a.x > b.x;
    else return a.y < b.y;
}
int main() {
    int n;  //区间数
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &I[i].x, &I[i].y);
    }
    sort(I, I + n, cmp);
    int ans = 1, lastx = I[0].x;    //表示最多能选ans个区间
    for (int i = 1; i < n; i++) {
        if (I[i].y <= lastx) {
            lastx = I[i].x;
            ans++;
        }
    }
    printf("%d", ans);
    return 0;
}

当题目改为区间选点问题时，即给出n个闭区间[x, y]，求最少需要多少个点，才能使每个闭区间中都至少存在一个点。只需要将I[i].y <= lastx改成I[i].y < lastx即可。

二分

二分模板

寻找有序序列中第一个满足某条件的元素的位置的代码模板。

1
2
3
4
5
6
7
8
9
10
11
12
// 二分区间左闭右闭，初值必须能覆盖解的所有可能取值
int solve(int left, int right, int x) {
    int mid = (left + right) / 2;
    while(left < right) {
        if(条件成立) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

当左开右闭时，代码修改如下：

1
2
3
4
5
6
7
8
9
10
11
12
// 二分区间左开右闭，初值必须能覆盖解的所有可能取值
int solve(int left, int right, int x) {
    int mid = (left + right) / 2;
    while(left + 1 < right) {
        if(条件成立) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return right;
}

二分法求√2的近似值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const double eps = 1e-5;    // 表示精度

double f(double x) {
    return x * x;
}

double calSqrt() {
    double left = 1, right = 2, mid;
    while(left < right) {
        mid = (left + right) / 2;
        if(right - left < eps) return mid;
        if(f(mid) > 2) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return mid;
}

双指针

归并排序（递归实现）

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
const int maxn = 100;
// 此处l2为r1 + 1
void merge(int a[], int l1, int r1, int l2, int r2) {
    int i = l1, j = l2;     // 双指针指向待合并数组最左端
    int temp[maxn], index = 0;
    while (i <= r1 && j <= r2) {
        if (a[i] <= a[j] {
            temp[index++] = a[i++];
        } else {
            temp[index++] = a[j++];
        }
    }
    while (i <= r1) temp[index++] = a[i++]; // 将剩余元素加入序列
    while (j <= r2) temp[index++] = a[j++];
    for (int x = 0; x < index; x++) {
        a[l1+x] = temp[x];  // 将合并后的序列赋值回数组a
    }
}
// 将array数组当前[left, right]进行归并排序
void mergeSort(int a[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;   // 取中点
        mergeSort(a[], left, mid);
        mergeSort(a[], mid + 1, right);
        merge(a[], left, mid, mid + 1, right);  // 将左子区间和右子区间合并
    }
}

快速排序（递归实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Partition(int a[], int left, int right) {
    int temp = a[left];
    while (left < right) {      // 只要left和right不相遇
        while (left < right && a[right] > temp) right—-;
        a[left] = a[right];
        while (left < right && a[left] <= temp) left++;
        a[right] = a[left];
    }
    a[left] = temp;
    return left;    // 返回相遇时的下标
}
void quickSort(int a[], int left, int right) {
    if (left < right) {
        int pos = Partition(a[], left, right);  // 此时已确定一个数位置
        quickSort(a[], left, pos - 1);  // 对左子区间进行快排
        quickSort(a[], pos + 1, 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
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
#include <iostream>
#include <string>
#include <map>
#include <stack>
#include <queue>
using namespace std;

struct node {
    int num;
    char op;
    bool flag;
};

string str;
stack<node> s;
queue<node> q;
map<char, int> op;

void Change() {
    node temp;
    for (int i = 0; i < str.length();) {
        if (str[i] >= '0' && str[i] <= '9') {
            temp.flag = true;
            temp.num = str[i++] - '0';
            while (i < str.length() && str[i] >= '0' && str[i] <= '9') {
                temp.num = temp.num * 10 + (str[i++] - '0');
            }
            q.push(temp);
        } else {
            temp.flag = false;
            while (!s.empty() && op[str[i]] <= op[s.top().op]) {
                q.push(s.top());
                s.pop();
            }
            temp.op = str[i++];
            q.push(temp);
        }
    }
    while (!s.empty()) {
        q.push(s.top());
        s.pop();
    }
}

double Cal() {
    double first, second;
    node cur, temp;
    stack<int> st;
    while (!q.empty()) {
        cur = q.front();
        q.pop();
        if (cur.flag == true) st.push(cur.num);
        else {
            second = st.top();
            st.pop();
            first = st.top();
            st.pop();
            temp.flag = true;
            if (cur.op == '+') temp.num = first + second;
            else if (cur.op == '-') temp.num = first - second;
            else if (cur.op == '*') temp.num = first * second;
            else temp.num = first / second;
            s.push(temp);
        }
    }
    return s.top().num;
}

int main() {
    op['+'] = op['-'] = 1;
    op['*'] = op['/'] = 2;
    getline(cin, str);
    for (string::iterator it = str.end(); it != str.begin(); it++) {
        if (*it == ' ') str.erase(it);
    }
    Change();
    printf("%.2f", Cal());
    
    return 0;
}

DFS

背包问题

有n件物品，每件物品重量为w[i]，价值为c[i]。如果需要选出若干物品放入一个容量为v的背包中，问如何放才能在重量不超过v的基础上使得总价值最大。

  • 常规递归解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

const int maxn = 30;
int n, v, maxValue = 0, w[maxn], c[maxn];

void DFS(int index, int sumW, int sumC) {
    if (index == n) {
        if (sumW <= v && sumC > maxValue) maxValue = sumC;
        return;
    }
    DFS(index + 1, sumW, sumC);     // 不选该物品的分支
    DFS(index + 1, sumW + w[index], sumC + c[index]);   // 选的分支
}

int main() {
    scanf(“%d %d”, &n, &v);
    for (int i = 0; i < n; i++) scanf(“%d”, &w[i]);
    for (int i = 0; i < n; i++) scanf(“%d”, &c[i]);
    DFS(0, 0, 0);   // 初始index，sumW和sumC都是0
    printf(“%d”, maxValue);
}
  • 剪枝改进
1
2
3
4
5
6
7
8
void DFS(int index, int sumW, int sumC) {
    if (index == n) return;
    DFS(index + 1, sumW, sumC);
    if (sumW + w[index] <= v) {
        if (sumC + c[index] > maxValue) maxValue = sumC + c[index];
        DFS(index + 1, sumW + w[index], sumC + v[index]);
    }
}

求子序列

该一类问题描述给定一个序列，枚举这个序列的所有子序列（可以不连续），以下给出一个具体案例：

给定n个整数（可能为负），从中选择k个数，使得这k个数之和恰好等一给定的一个整数x，如果有多种方案，则从其中选择平方和最大的一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// maxSumSqu为最大平方和
int n, k, x, maxSumSqu = -1, a[maxn];
// temp存放临时方案，ans存放平方和最大的方案
vector<int> temp, ans;

void DFS(int index, int tempK, int sum, int sumSqu) {
    if (tempK = k && sum == x) {
        if (sumSqu > maxSumSqu) {
            maxSumSqu = sumSqu;
            ans = temp;
        }
        return;
    }
    if (tempK > k || index == n || sum > x) return;
    temp.push_back(a[index]);
    DFS(index + 1, tempK + 1, sum + a[index], sumSqu + a[index] * a[index]);
    temp.pop_back();
    DFS(index + 1, tempK, sum, sumSqu);
}

BFS

BFS模版

一般使用队列实现

1
2
3
4
5
6
7
8
9
10
void BFS(int s) {
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        取出队首元素top;
        访问队首元素top（例如print）;
        将队首元素出队;
        将top的下一层结点中未曾入队的结点全部入队，并设置为已入队;
    }
}

迷宫找出口

给定一个n * m大小的迷宫，其中*代表不可通过的墙壁，而“.”代表平地，s表示起点，t表示终点。移动过程中，如果当前位置时（x, y）（下标从0开始），且每次只能往上下左右移动，求从起点s到终点t的最少步数。

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
#include <iostream>
#include <queue>
using namespace std;

const int maxn = 100;

struct Node {
    int x, y;
    int step;   // 表示步长
} s, t, node;

int n, m;
char maze[maxn][maxn];
bool inq[maxn][maxn] = {false};
int x[4] = {0, 0, 1, -1};
int y[4] = {1, -1, 0, 0};

// 检测位置是否有效
bool test(int x, int y) {
    if (x >= n || x < 0 || y >= m || y < 0) return false;
    if (maze[x][y] == ‘*’) return false;
    if (inq[x][y] == true) return false;
    return true;
}

int BFS() {
    queue<Node> q;
    q.push(s);
    while (!q.empty()) {
        Node top = q.front();
        q.pop();
        if (top.x = t.x && top.y == t.y) return top.step;
        for (int i = 0; i < 4; i++) {
            int newx = top.x + x[i];
            int newy = top.y + y[i];
            if (test(newx, newy)) {
                node.x = newx;
                node.y = newy;
                node.step = top.step + 1;
                q.push(node);
                inq[newx][newy] = true;
            }
        }
        return -1;
    }
}

int main() {
    scanf(“%d%d”, &n, &m);
    for (int i = 0; i < n; i++) {
        getchar();
        for (int j = 0; j < m; j++) {
            maze[x][y] = getchar();
        }
        maze[x][m+1] = ‘\0’;
    }
    scanf(“%d%d%d%d”, &s.x, &s.y, &t.x, &t.y);
    s.step = 0;
    printf(“%d”, BFS());
    
    return 0;
}

树与二叉树

二叉树的储存和操作

二叉树的储存结构

通常采用二叉链表来储存二叉树，二叉链表有以下好处：

  1. 结构体中存放指针，占用空间小
  2. 删除方便，只需要将指针置空就行
  3. 可以实时控制新生成结点的个数
1
2
3
4
5
6
7
8
9
10
11
struct node {
    typename data;
    node* left;
    node* right;
};
node* newNode(int v) {
    node* node = new node;
    node->data = v;
    node->left = node->right = NULL;
    return node;
}

二叉树结点的查找、修改

1
2
3
4
5
6
void search(node* root, int x, int newdata) {
    if (root == NULL) return;
    if (root->data == x) root->data = newdata;
    search(root->left, x, newdata);
    search(root->right, x, newdata); 
}

二叉树结点的插入

1
2
3
4
5
6
7
8
9
10
// insert函数将在二叉树中插入一个数据域为x的新结点（参数root要加引用）
void insert(node* &root, int x) {
    if (root == NULL) {     // 空树，说明查找失败，也即插入位置
        root = newNode(x);  //根root也已修改，因为传了引用
        return;
    }
    if (root->data == x) return;    // 说明已经存在
    else if (x < root->data) insert(root->left, x);
    else insert(root->right, x);
}

二叉树的建立

1
2
3
4
5
6
7
node* create(int data[], int n) {
    node* root = NULL;
    for (int i = 0; i < n; i++) {
        insert(root, data[i]);
    }
    return root;
}

二叉树的遍历

二叉树先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 定义二叉树节点的结构体
struct Node {
    Node left;
    int data;
    Node right;
};
// 先序遍历函数
void PreOrder(Node a) {
    if(a) {
        printf(“%d”, a.data);
        PreOrder(a.left);
        PreOrder(a.right);
    }
}

中序和后序遍历只需要调换printf语句和递归的顺序即可

二叉树先序&中序遍历（栈）

中序实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InOrder(Node a) {
    Node b = a;
    stack<Node> s;
    while (b || !empty(s)) {
        while (b) {
            s.push(b);
            b = b.left;
        }
        if (!empty(s)) {
            b = s.top();
            printf(“%d”, b.data);
            s.pop();
            b = b.right;
        }
    }
}

前序实现

将printf语句放在s.push(b)这一句之前即可，表示第一次遇见这个结点就打印

二叉树层序遍历（队）

1
2
3
4
5
6
7
8
9
10
11
void LayerOrder(Node a) {
    queue<Node> q;
    Node b = a;
    if (!b) return;  // 如果结点空了则返回
    q.push(b);
    if (!empty(q)) {
        printf(“%d”, b.data);
        if (b.left) q.push(b.left);
        if (b.right) q.push(b.right);
    }
}

重建二叉树

给出先序序列和中序序列，要求重建这棵二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
node* create(int preL, int preR, int inL, int inR) {
    if (preL > preR) return NULL;
    int k;
    node* root = new node;
    root->data = pre[preL];
    for (k = 0; k < inR; k++) {
        if (pre[preL] == in[k]) break;
    }
    int numLeft = k - inL;  // 注意是减中序的左结点
    root->left = create(preL + 1, pre + numLeft, inL, k - 1);
    root->right = create(pre + numLeft + 1, preR, k + 1, inR);
    return root;
}

树的遍历

树的静态写法

1
2
3
4
struct node {
    int data;
    vector<int> child;  // 动态数组防止子结点过多空间超限
} Node[maxn];

树的先根遍历

1
2
3
4
5
6
void PreOrder(int root) {
    printf(“%d”, &Node[root].data);
    for (int i = 0; i < Node[root].child.size(); i++) {
        PreOrder(Node[root].child[i]);
    }
}

后根遍历只需要将printf语句下放即可。

树的层序遍历（记录层号）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct node {
    int data;
    int layer;  // 记录层号
    vector<int> child;
} Node[maxn];
void LayerOrder(int root) {
    queue<node> q;
    Node[root].layer = 0;
    q.push(Node[root]);
    while (!q.empty()) {
        int front = q.front();
        q.pop();
        printf(“%d”, Node[front].data);
        for (int i = 0; i < Node[front].child.size(); i++) {
            int child = Node[front].child[i];
            child.layer = Node[front].layer + 1;
            q.push(child);
        }
    }
}

二叉查找树（BST）

  1. 要么二叉查找树是一棵空树。
  2. 要么二叉查找树由根结点、左子树、右子树组成，其中左子树和右子树都是二叉查找树，且左子树上所有结点的数据域均小于或等于根结点的数据域，右子树上所有的结点数据域均大于根结点的数据域（其中可以得到一个规律：二叉查找树的中序遍历必然是非递减序列）。

查找操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// search函数查找二叉查找树中数据域为x的结点
void search(node* root, int x) {
    if (root == NULL) {
        printf(“search failed”);
        return;
    }
    if (x == root->data) {
        printf(“%d”, root->data);
    } else if (x < root->data) {
        search(root->left, x);
    } else {
        search(root->right, x);
    }
}

插入操作

1
2
3
4
5
6
7
8
9
10
// insert函数将在二叉树中插入一个数据域为x的新结点（参数root要加引用）
void insert(node* &root, int x) {
    if (root == NULL) {     // 空树，说明查找失败，也即插入位置
        root = newNode(x);
        return;
    }
    if (root->data == x) return;    // 说明已经存在
    else if (x < root->data) insert(root->left, x);
    else insert(root->right, x);
}

二叉查找树的建立

1
2
3
4
5
6
7
node* create(int data[], int n) {
    node* root = NULL;
    for (int i = 0; i < n; i++) {
        insert(root, data[i]);
    }
    return 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
// 寻找以root为根结点的树中的最大权值结点
node* findMax(node* root) {
    while (root->right != NULL) {
        root = root->right;
    }
    return root;
}
// 寻找以root为根结点的树中的最小权值结点
node* findMin(node* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}
// 删除以root为根结点的树中权值为x的结点
void delete(node* &root, int x) {
    if (root == NULL) return;
    if (root->data == x) {
        if (root->right == NULL && root->left == NULL) {
            root = NULL;    // 如果是叶子结点直接置空
        } else if (root->left != NULL) {
            node* pre = findMax(root->left);
            root->data = pre->data;
            delete(root->left, pre->data);
        } else if (root->right != NULL) {
            node* next = findMin(root->right);
            root->data = next->data;
            delete(root->right, next->data);
        }
    } else if (root->data > x) {
        delete(root->left, x);
    } else {
        delete(root->right, x);
    }
}

并查集

并查集模版

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
int father[N];
//初始化并查集
void init() {
    for (int i = 1; i <= N; i++) {
        father[i] = i;
    }
}
//查找根结点操作
int findFather(int x) {
    int a = x;  //a会被根结点替换掉，先储存
    while (x != father[x]) {
        x = father[x];
    }
    while (a != father[a]) {
        int z = a;  //a会被father[a]替换掉，先储存
        a = father[a];
        father[z] = x;
    }
    return x;
}
//合并两个集合
void union(int a, int b) {
    int fa = findFather(a);
    int fb = findFather(b);
    if (fa != fb) {
        father[fa] = fb;
    }
}

好朋友（练习题）

有一个数码宝贝的世界，不同的数码宝贝可能是好朋友，数码宝贝的好朋友关系存在交换律和传递律，现在输入一组数码宝贝的编号和它们之间的关系，问能将这些数码宝贝最多分为多少组。

解题思路：将题目中的组视为集合，可以对在输入时对这些数码宝贝进行合并操作，最后得到的组数就是答案。关于如何获取组数，可以建立一个bool数组flag[n]来判断每个元素是否时某个集合的根结点。最后遍历该数组为true时累加即可。

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
#include <iostream>
using namespace std;
const int N = 110;
int father[N];
bool flag[N];
int findFather(int x) {
    int a = x;
    while (x != father[x]) x = father[x];
    // 缩短路径
    while (a != father[a]) {
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}
void Union(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if (faA != faB) father[faA] = faB;
}
void init(int n) {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
        flag[i] = false;
    }
}
int main() {
    int n, m, a, b, cnt = 0;
    scanf("%d%d", &n, &m);
    init(n);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        Union(a, b);
    }
    for (int i = 1; i <= n; i++) {
        flag[findFather(i)] = true;
    }
    for (int i = 1; i <= n; i++) {
        if (flag[i] == true) cnt++;
    }
    printf("%d", cnt);
}

堆

大顶堆向下调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 对heap数组在[low, high]范围进行向下调整
// 其中low为欲调整结点的数组下标，而high为堆的最后一个元素
void downAdjust(int low, int high) {
    int i = low, j = low * 2;
    while (j <= high) {
        if (j + 1 <= high && heap[j+1] >= heap[j]) j = j + 1;
        if (heap[j] > heap[i]) {
            swap(heap[i], heap[j]);
            i = j;
            j = i * 2;
        } else break;
    } 
}
// 有了上面的函数，就可以很简便的建堆了
void createHeap() {
    for (int i = n / 2; i >= 1; i—-) {
        downHeap(i, n);
    }
}
// 还有删除堆顶
void deleteTop() {
    heap[1] = heap[n—-];
    downHeap(1, n);
}

大顶堆向上调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 对heap数组在[low, high]范围进行向上调整
// 其中low一般设置为1，而high为欲调整的结点树组下标
void upAdjust() {
    int i = high, j = i / 2;
    while (j >= low) {
        if (heap[j] < heap[i]) {
            swap(heap[i], heap[j]);
            i = j;
            j = i / 2;
        } else break;
    }
}
// 再此基础上就很容易实现添加元素的代码了
void insert(int x) {
    heap[++n] = x;
    upAdjust(1, n);
}

图

图的储存方法

通常采用邻接矩阵和邻接表储存，邻接矩阵采用二维数组，下标表示端点，值表示权值；邻接表一般使用链表储存，也可以用动态数组vector，更易理解。

邻接表

1
2
3
4
5
6
7
8
9
10
11
struct Node {   // v是端点编号，w是权值
    int v, w;
    Node (int _v, _w) {     // 添加构造函数方便添加结点
        v = _v;
        w = _w;
    }
};
vector<Node> adj[100];
// 添加一条从1号到3号顶点的无向边，权值为4
adj[1].push_back(Node(3,4));
adj[3].push_back(Node(1,4));

图的遍历序列

DFS

以下解法都是针对图的通解（不针对联通分量），如果确定图是联通分量或强联通分量，则只需依次DFS即可。

邻接矩阵的DFS解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int maxn = 1000;
const int inf = 1000000000;
int n, g[maxn][maxn];
bool vis[maxn] = {false};
void DFS(int v, int depth) {
    vis[v] = true;
    // 如果要对v进行一些操作，可以在这里进行
    // 下面对所有从u出发能达到的分支顶点进行枚举
    for (int i = 0; i < n; i++) {
        if (vis[i] == false && g[v][i] != inf) {
            DFS(i, depth+1);
        }
    }
}
void DFSTrave() {
    for (int i = 0; i < n; i++) {
        if (vis[i] == false) {
            DFS(i, 1);
        }
    }
}

邻接表写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int maxn = 1000;
int n;  // 表示端点数
vector<int> adj[maxn];
bool vis[maxn] = {false};
void DFS(int v, int depth) {
    vis[v] = true;
    // 如果要对v进行一些操作，可以在这里进行
    // 下面对所有从u出发能达到的分支顶点进行枚举
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (vis[u] == false) {
            DFS(u, depth+1);
        }
    }
}
void DFSTrave() {
    for (int i = 0; i < n; i++) {
        if (vis[i] == false) {
            DFS(i, 1);
        }
    }
}

BFS

邻接矩阵写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n, g[maxn][maxn];   // n为顶点数，maxn为最大顶点数
bool inq[maxn] = {false};
void BFS(int u) {
    queue<int> q;
    q.push(u);
    inq[u] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v = 0; v < n; v++) {
            if (inq[v] == false && g[u][v] != inf) {
                
            }
        }
    }
}
void BFSTravel() {
    for (int i = 0; i < n; i++) {
        if (inq[i] == false) {
            BFS(i);
        }
    }
}

邻接表写法

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
vector<int> adj[maxn];
int n;
bool inq[maxn];
void BFS(int u) {
    inq[u] = true;
    queue<int> q;
    q.push(u);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v = 0; v < adj[u].size(); v++) {
            int v = adj[u][v];
            if (inq[v] == false) {
                q.push(v);
                inq[v] = true;
            }
        }
    }
}
void BFSTravel() {
    for (int i = 0; i < n; i++) {
        if (inq[i] == false) {
            BFS(i);
        }
    }
}

给定初始点输出层号

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
struct node {
    int v;
    int layer;
};
vector<node> adj[maxn];
void BFS(int s) {
    queue<node> q;
    node start;
    start.v = s;
    start.layer = 0;
    q.push(start);
    while (!q.empty()) {
        node front = q.front();
        q.pop();
        int u = front.v;
        for (int i = 0; i < adj[u].size(); i++) {
            node next = adj[u][i];
            next.layer = front.layer + 1;
            if (vis[next.v] == false) {
                q.push(next);
                vis[next.v] = true;
            }
        }
    }
}

最短路径

Dijkstra算法

解决单源最短路径的一种算法。

邻接矩阵写法

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
const int inf = 1000000000;
const int maxn = 1000;
int g[maxn][maxn], n;   // g是图，n是顶点数
bool vis[maxn] = {false};     // vis表示是否访问过
int d[maxn];    // 表示起点到各点的最短路径长度
void Dijkstra(int s) {
    fill(d, d + maxn, inf);
    d[s] = 0;   // 初始化
    for (int i = 0; i < n; i++) {   // 循环n次
        int u = -1, min = inf;
        for (int j = 0; j < n; j++) {
            if (d[j] < min && vis[j] == false) {
                u = j;  // u是起点到当前未访问顶点中距离最小的点
                min = d[j];
            }
        }
        if (u == -1) return;    // 说明剩下的顶点和s不连通
        vis[u] = true;
        for (int v = 0; v < n; v++) {
            if (vis[v] == false && g[u][v] + d[u] < d[v] && 
                g[u][v] != inf) {
                d[v] = d[u] + g[u][v];
            }
        }
    }
}

邻接表写法

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
struct Node {
    int v, dis; // v为边的目标顶点，dis为边权
};
vector<Node> g[maxn]; // 存放图
int d[maxn];    // 存放最短路径
bool vis[maxn] = {false}; // 判定是否访问过
void Dijkstra(int s) {
    fill(d, d + maxn, 0);
    d[s] = 0;   // 初始化
    for (int i = 0; i < n; i++) {
        int u = -1, min = inf;  
        for (int j = 0; j < n; j++) {
            // 这个循环是拿到当前未访问点中距离最小的那个
            if (vis[j] == false && d[j] < min) {
                u = j;
                min = d[j];
            }
        }
        if (u == -1) return;
        vis[u] = true;
        for (int j = 0; j < g[u].size(); j++) {
            int v = g[u][j].v;
            if (vis[v] == false && g[u][j].dis + d[u] < d[v]) {
                d[v] = d[u] + g[u][j].dis;
            }
        }
    }
}

Dijkstra+DFS

用于处理逻辑更为复杂的边权或者点权的计算（非和），比起Dijkstra更为通用而模版化

  • Dijkstra部分
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
vector<int> pre[maxn];  // pre[v]表示v顶点的所有前驱
void Dijkstra(int s) {
    fill(d, d + maxn, inf);
    d[s] = 0;   // 初始化
    for (int i = 0; i < n; i++) {   // 循环n次
        int u = -1, min = inf;
        for (int j = 0; j < n; j++) {
            if (d[j] < min && vis[j] == false) {
                u = j;  // u是起点到当前未访问顶点中距离最小的点
                min = d[j];
            }
        }
        if (u == -1) return;    // 说明剩下的顶点和s不连通
        vis[u] = true;
        for (int v = 0; v < n; v++) {
            if (vis[v] == false && g[u][v] != inf) {
                if (g[u][v] + d[u] < d[v]) {
                    d[v] = d[u] + g[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);    // 令v的前驱为u
                }
                else if (g[u][v] + d[u] == d[v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
}
  • DFS部分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int optValue;   //表示第二标尺最优值
vector<int> pre[maxn];
vector<int> path, tempPath; //最优路径和临时最优路径
void DFS(int s) {
    //递归边界
    if (v == st) {  //到达了叶子结点st
        tempPath.push_back(v);
        int value;
        value = tempPath上的value值
        if (value 优于 optValue) {
            optValue = value;
            path = tempPath;
        }
        tempPath.pop();
        return;
    }
    //递归式
    tempPath.push_back(v);
    for (int i = 0; i < pre[v].size(); i++) {
        DFS(pre[v][i]);
    }
    tempPath.pop_back();
}
  • 访问部分（因为递归的原因，所以一般要逆向访问）
1
2
3
4
5
6
7
8
9
10
11
12
//边权部分
int value = 0;
for (int i = tempPath.size() - 1; i > 0; i--) {
    int id = tempPath[i], nextId = tempPath[i-1];
    value += v[i][i-1]; //value增加id->idNext的边权
}
//点权部分
int value = 0;
for (int i = tempPath.size() - 1; i > 0; i--) {
    int id = tempPath[i];
    value += w[i]; //value增加id的点权
}

Bellman-Ford

  • 用于处理负环的情况，当存在负环而且负环从源点可达时Dijkstra算法会出错，因为负环会导致在第一次遍历结束后最短路径的某部分可以通过负环得到优化。Bellman算法不是进行1次，而是进行v-1（v为顶点个数）次，每一次都至少优化一层（可以证明最短路径一定不会超过v-1层）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Node {
    int v, dis; // v为邻接边的目标顶点，dis为邻接边的边权
};
const int MAXN = 0x3fffffff;
vector<Node> g[MAXN];
int n;  //顶点数
int d[MAXN];    //起点到达各点的最短路径长度
void Bellman(int s) {
    fill(d, d + MAXN, INF);
    //以下为求解数组d的部分
    for (int i = 0; i < n - 1; i++) {
        for (int u = 0; u < n; u++) {
            for (int j = 0; j < g[u].size(); j++) {
                int v = g[u][j].v;
                int dis = g[u][j].dis;
                if (d[u] + dis < d[v]) {
                    d[v] = d[u] + dis;
                }
            }
        }
    }
}

SPFA

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
vector<Node> adj[maxn]; //图g的邻接表
int n, d[maxn], num[maxn];  //num数组记录顶点的入队次数
bool inq[maxn]; //判断顶点是否在队列中

bool SPFA(int s) {
    //初始化部分
    memset(inq, false, sizeof(inq));
    memset(num, 0, sizeof(num));
    fill(d, d + maxn, inf);
    //核心部分
    queue<int> q;
    q.push(s);
    d[s] = 0;
    inq[s] = true;
    num[s]++;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        //遍历u的所有邻接边v
        for (int j = 0; j < adj[u].size(); j++) {
            int dis = adj[u][j].dis;
            int v = adj[u][j].v;
            if (d[u] + dis < d[v]) {
                d[v] = d[u] + dis;
                if (!inq[v])  {
                    q.push(v);
                    inq[v] = true;
                    num[v]++;
                    if (num[v] >= n)
                        return false;   //有可达负环
                }
            }
        }
    }
    return true;    //无可达负环
}

Floyd（全源最短路径）

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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 1000000000; //初始的所有边权
const int MAXV = 1000;  //最大顶点数
int n, m;   //n为顶点数，m为边数
int dis[MAXV][MAXV];    //dis[i][j]表示顶点i和顶点j的最短距离
void Floyd() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dis[i][k] + dis[k][j] < dis[i][j] &&
                    dis[i][k] != INF && dis[k][j] != INF) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }
}
int main() {
    fill(dis[0], dis[0] + MAXV * MAXV, INF);  //初始化边权
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) 
        dis[i][i] = 0;  //别忘了顶点到自身的距离是0
    int u, v;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        scanf("%d", &dis[u][v]);
    }
    Floyd();    //执行完Floyd之后dis[i][j]储存i到j的最短路径
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", dis[i][j]);
        }
        printf("\n");
    }
    return 0;
}

最小生成树

prim算法

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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 1000000000; //初始的所有边权
const int MAXV = 1000;  //最大顶点数
int n, m;   //n为顶点数，m为边数
int d[MAXV];    //顶点到集合s的最短距离
int g[MAXV][MAXV];  //图
bool vis[MAXV] = {false};   //vis表示顶点是否访问过
int Prim() {    //默认0号为初始点，返回最小生成树的边权之和
    fill(d, d + MAXV, INF);   //将整个d数组初始化为INF
    d[0] = 0;
    int ans = 0;    //ans值为最小生成树的边权之和
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;  //min一般初始赋值很大值，max一般赋很小值
        for (int j = 0; j < n; j++) {
            if (vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        //找不到小于INF的d[u]，说明剩下的顶点和集合s不联通
        if (u == -1) return -1;
        vis[u] = true;
        ans += d[u];    //将与集合s距离最小的边加入最小生成树
        for (int v = 0; v < n; v++) {
            if (vis[v] == false && g[u][v] != INF &&
                d[v] > g[u][v]) {
                d[v] = g[u][v]; //将g[u][v]赋值给d[v]，说明是距离集合的最小值
            }
        }
    }
    return ans;
}
int main() {
    fill(g[0], g[0] + MAXV * MAXV, INF);  //初始化边权
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) 
        g[i][i] = 0;  //别忘了顶点到自身的距离是0
    int u, v;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        scanf("%d", &g[u][v]);
        g[v][u] = g[u][v];
    }
    int ans = Prim();
    printf("%d", ans);
    return 0;
}

Kruskal算法

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
#include <iostream>
#include <algorithm>
using namespace std;
const int maxv = 110;  //最大顶点数
const int maxe = 11000; //最大边数
int n, m;   //n为顶点数，m为边数
int father[maxv];   //并查集来判断是否为连通图
struct Edge {
    int u, v;   //表示边的两个顶点
    int value;  //边权值
} edge[maxe];
bool cmp(Edge a, Edge b) {
    return a.value < b.value;
}
int findFather(int x) {
    int a = x;
    while (a != father[a]) {
        a = father[a];  //寻找父亲，循环结束时a储存该连通图的根结点
    }
    while (x != father[x]) {    //路径压缩
        int z = x;  //先储存，x会被father[x]替换掉
        x = father[x];
        father[z] = a;
    }
    return a;
}
int Kruskal() {
    int ans = 0, numEdge = 0;   //ans表示最小生成树边权值和，numEdge表示边数
    for (int i = 0; i < m; i++) {
        if (numEdge == n - 1) break;
        int fau = findFather(edge[i].u);
        int fav = findFather(edge[i].v);
        if (fau != fav) {   //说明两个联通分量独立
            father[fau] = fav;
            ans += edge[i].value;
            numEdge++;
        }
    }
    if (numEdge != n - 1) return -1;    //说明整个图不联通
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {   //初始化并查集
        father[i] = i;
    }
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].value);
    }
    sort(edge, edge + m, cmp);
    int ans = Kruskal();
    printf("%d", ans);
    return 0;
}

拓扑排序

拓扑排序可以用来判断一个有向图是否是有向无环图。

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
vector<int> g[maxn];    //邻接表
int n, m, inDegree[maxn];   //表示顶点数，边数和入度
//拓扑排序
bool topuSort() {   //当为有向无环图时返回true
    int num = 0;
    queue<int> q;
    for (int i = 0; i < n; i++) {   //如果入度为0，则入队
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];    //后继结点
            inDegree[v]—-;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
        num++;
    }
    if (num == n) return true;
    else return false;
}

动态规划

什么是动态规划

动态规划（Dynamic Programming）是一种用来解决一类最优化问题的算法思想。简单来说，动态规划将一个复杂的问题分解成若干个问题，通过综合子问题的最优解来得到原问题最优解的过程。十分灵活，无固定写法。有以下几个特性：

  1. 一个问题必须要有重叠子问题和最优子结构才能用动态规划求解
  2. 与分治的区别：分治不拥有重叠子问题
  3. 与贪心的区别：贪心“自顶向下”，只考虑子问题中最优的一个解。动态规划会考虑所有子问题，并选择继承能得到最优结果的那一个
  4. 设计状态转移方程是动态规划的核心，也是动态规划最难的地方。动态转移方程必须满足状态的无后效性

递归写法（斐波那契数列）

思路：每次访问到一个数时将其储存起来，来大量减少重复计算。类似打表的思想，以空间换取时间代价

1
2
3
4
5
6
7
8
int F(int n) {
    if (n == 0 || n == 1) return 1;
    if (dp[n] != -1) return dp[n];
    else {
        dp[n] = F(n-1) + F(n-2);
        return dp[n];
    }
}

递推写法（数塔问题）

状态转移方程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1000;
int f[maxn][maxn], dp[maxn][maxn];
int main() {
    int n;
    scanf(“%d”, &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            scanf(“%d”, &f[i][j]);
        }
    }
    for (int j = 1; j <= n; j++) {
        dp[n][j] = f[n][j];
    }
    for (int i = n - 1; i >= 1; i—-) {
        for (int j = 1; j <= i; j++) {
            max(dp[i+1][j], dp[i+1][j+1]) + f[i][j];
        }
    }
    printf(“%d”, dp[1][1]);
    return 0;
}

最大连续子序列和

给定一个数字序列，就其中最大的连续子序列的和。

思路：设立一个数组dp，存放的是以a[i]作为末尾的连续序列的最大和，可以发现dp[i]可以由dp[i-1]和a[i]得到。状态转移方程为：。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main() {
    int n, k;
    scanf(“%d”, &n);
    for (int i = 0; i < n; i++) {
        scanf(“%d”, &a[i]);
    }
    dp[0] = a[0];
    for (int i = 1; i < n; i++) {
        dp[i] = max{a[i], dp[i-1] + a[i]};
    }
    for (int i = 1; i < n; i++) {
        if (dp[i] > dp[k]) k = i;
    }
    printf(“%d”, dp[k]);
}

最长不下降子序列（LIS）

在一个数字序列中，找到一个最长的子序列（可以不连续），使得这个子序列是不下降（非递减）的。

状态转移方程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100;
int A[N], dp[N];
int main() {
    int n;
    scanf(“%d”, &n);
    for (int i = 1; i <= n; i++) scanf(“%d”, &A[i]);
    int ans = -1;   // 记录最大长度
    for (int i = 1; i <=; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++) {
            dp[i] = dp[j] + 1;  // 状态转移方程，用以更新dp[i]
        }
    }
    ans = max(ans, dp[i]);
}
printf(“%d”, ans);
return 0;

最长公共子序列（LCS）

给定两个字符串a和b（下标从1开始），求一个字符串，使得这个字符串是a和b的最长公共部分（子序列可以不连续)。

状态转移方程为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
int dp[100][100];
int main() {
    string a, b;
    scanf(“%s%s”, a, b);
    a = “(” + a;    // 让a和b下标从1开始，找两个不同的字符
    b = “)” + b;
    int lena = a.length(), b = b.length();
    memset(dp, 0, sizeof(dp)); // 初始化为0
    // 状态转移方程
    for (int i = 1; i <= lena; i++) {
        for (int j = 1; j <= lenb; j++) {
            if (a[i] == b[j]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    printf(“%d”, dp[lena][lenb]);
    return 0;
}

最长回文子串

给出一个字符串s，求s的最长回文子串的长度。

状态转移方程：

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
#include <iostream>
using namespace std;
int dp[1001][1001];
int main() {
    string s;
    can >> s;
    int len = s.length(), ans = 1;
    memset(dp, 0, sizeof(dp));  // dp数组初始化为0
    for (int i = 0; i < len; i++) {
        dp[i][i] = 1;
        if (i < len - 1) {
            if (s[i] == s[i+1]) {
                dp[i][i+1] = 1;
                ans = 2;
            }
        }
    }
    // 状态转移方程
    for (int l = 3; l <= len; l++) {
        for (int i = 0; l + i - 1 < len; i++) {
            int j = l + i - 1;
            if (s[i] == s[j] && dp[i+1][j-1] == 1) {
                dp[i][j] = 1;
                ans = l;
            }
        }
    }
    printf(“%d”, ans);
    return 0;
}

背包问题

01背包问题

有n件物品，每件物品重量为w[i]，价值为w[i]。现在有一个容量为v的背包，问如何选取物品放入背包中，使得背包中的总价值最大。其中每件物品都只有1件。

二维数组做法（便于理解）的状态转移方程：

空间优化解法的状态转移方程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
using namespace std;
int w[100], c[100], dp[1000];
int main() {
    int n, V;
    scanf(“%d%d”, &n, &V);
    for (int i = 1; i <= n; i++) scanf(“%d”, &w[i]);
    for (int i = 1; i <= V; i++) scanf(“%d”, &c[i]);
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int v = V; v >= w[i]; v--) {
            dp[v] = max(dp[v], dp[v-w[i]] + c[i]);
        }
    }
    int maxn = 0;
    for (int v = 0; v <= V; v++) {
        if (dp[v] > maxn) maxn = dp[v];
    }
    printf(“%d”, maxn);
    return 0;
}

完全背包问题

有n件物品，每件物品重量为w[i]，价值为w[i]。现在有一个容量为v的背包，问如何选取物品放入背包中，使得背包中的总价值最大。其中每件物品有无穷件。

状态转移方程：

边界为：

一维状态转移方程：

边界为：

此处和01背包问题的不同点在于是正向枚举的

1
2
3
4
5
for (int i = 1; i <= n; i++) {
    for (int v = w[i]; v <= V; v++) {
        dp[v] = max(dp[v], dp[v - w[i]] + c[i]);
    }
}

字符串匹配

KMP

时间复杂度为：（）

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
//getNext求解长度为n的字符串s的next数组
void getNext(string s, int n) {
    int j = -1;
    next[0] = -1;   //初始化j = next[0] = -1表示
    for (int i = 1; i < n; i++) {   //求解1～n-1的next数组
        while（j != -1 && s[i] != s[j+1]) {
            j = next[j];    //反复让j = next[j]
        }   //当j = -1或s[i] == s[j+1]
        if (s[i] == s[j+1]) {
            j++;    //next[i] = j + 1
        }
        next[i] = j;
    }
}
//KMP算法，判断pattern是否是text的子串
bool KMP(string text, string pattern) {
    int lent = text.length(), lenp = pattern.length();
    getNext(pattern, lenp);
    int j = -1;
    for (int i = 0; i < n; i++) {
        while (j != -1 && text[i] != pattern[j+1]) {
            j = next[j];
        }
        if (text[i] == pattern[j+1]) {
            j++;
        }
        if (j == m - 1) {
            return true;
        }
    }
    return false;
}

数学问题

最大公约数 & 最小公倍数

最大公约数通常采用辗转相除法解决

1
2
3
4
int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

得到最大公约数d后，最小公倍数即为

素数判断

一般方法

1
2
3
4
5
6
7
bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

该方法判断1～n之间的素数时时间复杂度为o（n√n)

埃氏筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
const int maxn = 101;
int prime[maxn], pNum = 0;
bool p[maxn] = {0};
void findPrime() {
    for (int i = 2; i < maxn; i++) {
        if (!p[i]) {
            prime[pNum++] = i;
            for (int j = i + i; j < maxn; j += i) {
                p[j] = true;
            }
        }
    }
}

质因子分解

一个重要结论：对一个正整数n来说，如果它存在[2,n]范围内的质因子，要么这些质因子全部小于等于sqrt（n），要么只存在一个大于sqrt（n）的质因子，而其余质因子全部小于等于sqrt（n）。

模版如下：

1
2
3
4
5
6
7
8
9
if (n % prime[i] == 0) {
    fac[num].x = prime[i];
    fac[num].cnt = 0;
    while (n % prime[i] == 0) {
        fac[num].cnt++;
        n /= prime[i];
    }
    num++;
}

大整数运算

大整数储存

1
2
3
4
5
6
7
8
struct bign {
    int d[1000];
    int len;    // 储存该大整数的长度，很有用
    bign () {   // 初始化该结构体，默
        memset(d, 0, sizeof(d));
        len = 0;
    }
};

高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
bign add (bign a, bign b) {
    bign c;
    int carry = 0;  // 表示进位值
    for (int i = 0; i < a.len || i < b.len; i++) {
        int temp = a.d[i] + b.d[i] + carry;
        c.d[c.len++] = temp % 10;
        carry = temp / 10;
    }
    if (carry != 0) {   // 如果最后进位不为0，则直接赋值给最高位
        c.d[c.len++] = carry;
    }
    return c;
}

高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bign sub(bign a, bign b) {  // a为减数，b为被减数
    bign c;
    for (int i = 0; i < a.len || i < b.len; i++) {
        if (a.d[i] < b.d[i]) {
            a.d[i+1]—-;
            a.d[i] += 10; 
        }
        c.d[c.len++] = a.d[i] - b.d[i];
    }
    while (c.len - 1 > 1 && c.d[c.len-1] == 0) {
        c.len—-;    // 去除最高位的0，同时至少保留一位最低位
    }
    return c;
}

高精度与低精度的乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bign multi(bign a, int b) {
    bign c;
    int carry = 0;
    for (int i = 0; i < a.len; i++) {
        int temp = a.d[i] * b + carry;
        c.d[len++] = temp % 10;
        carry = temp / 10;
    }
    while (carry != 0) {
        c.d[c.len++] = carry % 10;
        carry /= 10;
    }
    return c;
}

高精度与低精度的除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bign divide(bign a, bign b, int& r) {
    bign c;
    c.len = a.len;  // 被除数的每一位和商的每一位是一一对应的，先令长度相等
    for（int i = a.len - 1; i >= 0; i--) {   // 从高位开始
        r = r * 10 + a.d[i];    // 与上一位留下的余数组合
        if (r < b) c.d[i] = 0;  // 不够除，该位为0
        else {  // 够除
            c.d[i] = r / b;
            r = r % b;
        }
    }
    while (c.len - 1 >= 1 && c.d[c.len - 1] == 0) {
        c.len--;
    }
    return c;
}

拓展欧几里得算法

给定两个非零整数a和b，求一组整数解（x，y），使得ax + by = gcd（a，b）成立。推导可以得到一个递推公式，，。其中x1，y1表示新值，x2，y2表示旧值。

1
2
3
4
5
6
7
8
9
10
11
12
int exGcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;   // 此处的a即为边界的gcd
    }
    int g = exGcd(b, a % b, x, y);
    int temp = x;   // 存放x值
    x = y;   // 更新x = y（old）
    y = temp - a / b * y;   // 更新y = x(old) - a / b * y(old)
    return g;
}

此处x和y使用引用是因为保留对x和y的更新。

组合数

求n！中有多少个质因子p。

1
2
3
4
5
6
7
8
9
// 计算n！中有多少质因子p
int cal(int n, int p) {
    int ans = 0;
    while (n) {
        ans += n / p;   // 累加n/p^k
        n /= p;     // 相当于分母多乘一个p
    }
    return ans;
}

此处代入cal(n, 5)可以很快得到n！末尾有多少个零。因为末尾0的个数等于因子中10的个数，每个10都可以且只能分解出一个5，所以数目相等。

  • 本文标题：算法笔记学习记录
  • 本文作者：ZOU
  • 创建时间：2021-05-05 11:33:17
  • 本文链接：https://yipeng.xyz/2021/05/05/算法笔记学习记录/
  • 版权声明：可随意使用，但是转载请联系我！
 评论