Jenner's Blog

不变秃，也要变强！

0%

PAT

发表于 更新于 分类于 ， Valine：

算法初步

排序

使用sort函数，必要时需要自定义cmp比较函数；

散列

常用来打表，比如将字符串散列到一个长数组中；

递归

两个重点：递归边界，递推式；

贪心

局部最优，得到全局最优。应用例如：求最低价格。有时，需要加上对具体题目的规律推断。

二分

Upper_bound(begin, end, value) 找到第一个大于value的元素的地址，不存在则返回end；对数组或容器使用。

two pointers

研究问题与序列的特性，使用两个互相牵制的下标对序列进行扫描；

数学问题

最大公约数

1
2
3
int gcd(int a,int b){
	return !b ? a : gcd(b, a%b);
}

分数的四则运算

利用结构体定义分子分母，分别运算；

素数

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

质因子分解

1
2
3
struct factor{
	int x,cnt;
}fac[10];

从2到sqrt(n)范围的素数表中找质因子与对应的个数；如果没有被sqrt(n)以内的素数除尽，那么他本身是一个素数，质因子为本身；

大整数运算

1
2
3
4
struct bign{
	int d[1000];
	int len;
};

STL

  1. 只有vector和string支持*(it + i)的访问方式；
  2. 遍历容器可以用for(auto it: v)；
  3. String::nops是find函数查找失败的返回值，string的size_type的最大值；
  4. queue在使用front()和pop()之前，要判断empty()；

简单数据结构

栈

STL的stack；

队列

STL的queue；

链表

1
2
3
4
struct Node{
  typename data;
  node* next;
};

静态链表

1
2
3
4
5
6
7
struct Node{
  typename data;
  int next;
  // 有时候需要加上其他标志
  // bool falg; //结点有效状态，排序可以剔除无效结点
  // int address; //记录结点地址
}node[size];

搜索

DFS

常用递归解决；

剪枝

在进入分支前，先进行限制条件的判断；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void DFS(int index, int nowK, int nowSum,int fSum) {
    if (nowSum == n&&nowK == k) {    //递归边界（满足条件）
        if (fSum > maxfSum) {    //题目条件
            ans = temp;
            maxfSum = fSum;
        }
        return;
    }
    if (index == sqr||nowK>k||nowSum>n) return;    //递归边界（剪枝）
    temp.push_back(factor[index]);        //选择加入
    DFS(index , nowK + 1, nowSum + (int)pow(1.0*factor[index], p*1.0), fSum + factor[index]); // 如果不重复选，这里也该是index+1
    temp.pop_back();    //恢复，不加入
    DFS(index + 1, nowK, nowSum, fSum);
}

BFS

队列实现，按层次遍历；

1
2
3
4
5
6
7
8
9
10
11
void BFS(int s){
  queue<int> q;
  q.push(s);
  falg[s] = true; // 标记s入队
  while(!q.empty()){
    int top = q.front(); // 取队首
    // 访问top，进行操作
    q.pop(); //队首出队
    //将top的下一层结点中，未曾入队的进行入队，并设置为已入队
  }
}

当需要对队列中元素修改时，队列存储最好是他们的编号而不是元素本身。

树

  • 二叉树结点
1
2
3
4
5
struct BTNode {
  int data;
  BTNode *l, *r;
  // int layer;
};

建立二叉树

中序inorder+后序postorder 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
BTNode* create(int postL, int postR, int inL, int inR) {
  if (postL > postR||inL>inR)
    return NULL;
  BTNode *root = new BTNode;
  //根据后序找到根结点
  root->data = post[postR]; 
  int i;
  for (i = inL; i <= inR; i++) {
    //找到中序中的根结点位置
    if (in[i] == post[postR]) {  
      break;
    }
  }
  //当前根结点左子树的结点个数
  int leftnum = i - inL;  
  root->l = create(postL,postL+leftnum-1 , inL, i-1);
  root->r = create(postL + leftnum, postR-1, i + 1, inR);
  return root;
}

树的遍历

树的结点

1
2
3
4
5
struct TNode{  
	int w;
  vector<int> child;
  //int len,layer;
}Node[maxn];

树的先根遍历-dfs，层序遍历-bfs

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
// 子节点多于2个时，用静态链表方便
void preorder(int root, vector<int> &q,int sum) {
  sum += Node[root].w;
  //剪枝
  if (sum>s)    
    return;
  //加入
  q.push_back(Node[root].w);    
 //递归边界（满足题目条件）
 if (Node[root].child.size()==0&&sum == s) {  
    print(q);
    //恢复
    q.pop_back();    
    return;
  }
  sort(Node[root].child.begin(),
        Node[root].child.end(), cmp);
  for (int i = 0; i < Node[root].child.size(); i++) {   
     //先根遍历的核心
     preorder(Node[root].child[i], q,sum);
  }
  //不加入
  q.pop_back();        
}

void layerOrder(node *root){
	queue<BTNode*> q;
	q.push(root);
	int num = 0;
	while(q.size()>0){
		node* p = q.front();
		num++;
		cout << p->data;
		if (num < n)
			cout << " ";
		q.pop();
		if (p->l)
			q.push(p->l);
		if (p->r)
			q.push(p->r);
	}
}

void LayerOrder(int root){
  queue<int> q;
  q.push(root);
  Node[root].layer = 0;
  while(!q.empty()){
    int front = q.front();
    // ...访问根结点
    q.pop();
    for(int i=0;i<Node[front].child.size();i++){
      int child = Node[front].child[i];
      Node[child].layer = Node[front].layer + 1;
      q.push(child);
    }
  }
}

二叉查找树

特点：中序遍历有序。

删除（1）root为空，直接返回；（2）root值为x，进入删除处理；（2.0）无左右孩子，直接删除；（2.1）root有左孩子，在左子树中找pre，让pre覆盖root，接着在左子树中删除pre；（2.2）root右孩子类似；（3）root->data 大于x，去root->l删；（4）root->data小于x，去root->r删；

判断给出序列求是否是BST：（1）根据给出序列构建二叉树(insert)；（2）用vector比较是否一样（直接用==）；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void insert(node *&root, int x,bool mirror) {
    if (root == NULL)
    {
        root = new node;
      //需要写这句，或者在struct node初始化里就写好
        root->l = root->r = NULL;
        root->data = x;
        return;
    }
    if (mirror) {
        if (x >= root->data) insert(root->l, x, mirror);
        else
            insert(root->r, x, mirror);
    }
    else {
        if (x >= root->data) insert(root->r, x, mirror);
        else
            insert(root->l, x, mirror);
    }
}
  • 完全二叉查找树：同时有两者的性质，用数组存储，父子结点之间的关系用下标表示，for循环即是层序遍历；完全二叉树的形状已经确定了，又因为是查找树，对数组进行一次中序遍历，即可构建出树。
  • 给n个结点关系，建立二叉查找树：静态链表存储，建树，然后按中序遍历将排序后的数组填入；

AVL树

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
struct node {
    int data, height;    //记录当前树的高度
    node* l,* r;
};

node* newNode(int data) {
    node *root = new node;
    root->l = root->r = NULL;
    root->height = 1;
    root->data = data;
    return root;
}

int getHeight(node *root) {
    if (root == NULL)
        return 0;
    else
        return root->height;
}

void updateHeight(node* &root) {
    root->height = max(getHeight(root->l), getHeight(root->r)) + 1;
}

int getBalance(node* root) {
    return getHeight(root->l) - getHeight(root->r);    //一定是左-右
}
//左旋，注意是引用
void L(node* &root) {
    node* temp = root->r;
    root->r = temp->l;
    temp->l = root;
    updateHeight(root);    //一定先更新更低层的结点高度
    updateHeight(temp);
    root = temp;
}

//右旋
void R(node* &root) {
    node* temp = root->l;
    root->l = temp->r;
    temp->r = root;
    updateHeight(root);
    updateHeight(temp);
    root = temp;
}

void insert(node* &root,int data) {
    if (root == NULL)
    {
        root = newNode(data);
        return;
    }
    if (data >= root->data) {
        insert(root->r, data);    //递归插入，递归更新高度
        updateHeight(root);        //插入点先更新，然后往回退
        if (getBalance(root) == -2)
        {
            //RR
            if (getBalance(root->r) == -1) {
                L(root);
            }
            //RL
            else if (getBalance(root->r) == 1) {
                R(root->r);
                L(root);
            }
        }
    }
    else {
        insert(root->l, data);
        updateHeight(root);
        if (getBalance(root) == 2)
        {
            //LL
            if (getBalance(root->l) == 1) {
                R(root);
            }
            //LR
            else if (getBalance(root->l) == -1) {
                L(root->l);
                R(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
void init(int n) {
    for (int i = 1; i <= n; i++)
        father[i] = i;
}

int findRoot(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 fa = findRoot(a);
    int fb = findRoot(b);
    if (fa != fb) {
        father[fa] = fb;
    }
}

堆排序（求第k大/小的数）

  • 建堆时downAdjust，插入结点用upAdjust；
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 downAdjust(int low,int high) {
    int i = low, j=2*i;
    while (j <= high) {
        if (j+1<=high&&initial[j + 1] > initial[j])    //与较大孩子比较
            j++;
        if (initial[j] > initial[i]) {
            swap(initial[i],initial[j]);
            i = j;
            j = j * 2;
            continue;
        }
        else
            break;
    }
}

//建堆
void createHeap() {
    for (int i = n / 2; i >= 1; i--)    //从最后一个非叶结点开始
        downAdjust(i, n);
}


//deap sort，递增排序
void deap_sort() {
    createHeap();
    for (int i = n; i >= 2; i--) {
        swap(initial[i], initial[1]);    //取出最大值
        downAdjust(1, i - 1);
    }
}
  • 哈夫曼树（非前缀编码），用priority_queue,greater> q;代表小顶堆，每次取出最小两个元素向上建树；

图

遍历

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//每次DFS遍历一个连通块
void DFS(int u) {
    visit[u] = true;
    for (int i = 0; i < Node[u].adj.size(); i++) {
        int v = Node[u].adj[i];
        if (visit[v])
            continue;
        DFS(v);
    }
}

void DFSTrave() {
    for (int u = 0; u < maxn; u++) {
        if (visit[u])
            continue;
        DFS(u);
    ｝
}

BFS

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
struct node {
    int v;    //顶点编号
    int layer;
    node(int _v, int _lay) :v(_v), layer(_lay) {};
};
vector<node> adj[maxn];

void BFS(int query,int l,int &num) {
    bool inq[maxn] = { false };
    queue<node> q;
    node u(query, 0);    //初始点
    q.push(u);
    inq[query] = true;    //入队
    while (q.size() > 0) {
        node now = q.front();
        q.pop();
        int u = now.v;
        for (int i = 0; i < adj[u].size(); i++) {
            node next = adj[u][i];
            next.layer = now.layer + 1;
            if (inq[next.v] == false&&next.layer<=l)    //题目条件
            {
                q.push(next);
                inq[next.v] = true;
                num++;
            }
        }
    }
}
  • 无向图添加x条边使其连通：x=连通块个数-1； 计算连通块个数：DFS或者并查集

单源最短路径

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
const int INF = (1 << 31) - 1;
// s：起点；D：题目要求的终点
void Dijkstra(int s,int D) {
  // d[i]：起点到i点的最短路径长度
    fill(d,d+maxn,INF);
    fill(num,num+maxn,0);
    d[s] = 0;
    c[s] = 0;    //第二标尺
    num[s]=1;        //经过该结点的最短路径条数
    for (int i = 0; i < n; i++)
        pre[i] = i;        //记录前驱结点
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j < n; j++) {
            if (visit[j] == false && d[j] < MIN)    //找出最短边
            {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1 || u == D) return;    //退出
        visit[u] = true;        //加入集合
        for (int v = 0; v < n; v++) {
            if (visit[v] == false && G[u][v] != INF) {
                if (d[u] + G[u][v] < d[v]) {
                    d[v] = d[u] + G[u][v];
                    c[v] = c[u] + cost[u][v];
                    pre[v] = u;
                    num[v]=num[u];
                }
                else if (d[u] + G[u][v] == d[v]) {
                    if (c[u] + cost[u][v] < c[v])
                    {
                        c[v] = c[u] + cost[u][v];
                        pre[v] = u;
                        num[v]+=num[u];
                    }
                }
            }
        }
    }
}

//输出路径
void DFS(int v) {
    if (v == s) {
        printf("%d ", v);
        return;
    }
    DFS(pre[v]);
    printf("%d ", v);
}

多标尺要求通用模板，用Dijkstra+DFS

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
void Dijkstra(int s,int ed) {
    fill(d, d+n, INF);
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j < n; j++) {
            if (visit[j] == false && d[j] < MIN)
            {
                MIN = d[j];
                u = j;
            }
        }
        if (u == -1 || u == ed) return;
        visit[u] = true;
        for (int v = 0; v < n; v++) {
            if (visit[v] == false && G[u][v] != INF) {
                if (d[u] + G[u][v] < d[v]) {
                    d[v] = d[u] + G[u][v];
                    pre[v].clear();        //pre是一个vector<int>
                    pre[v].push_back(u);
                }
                else if (d[u] + G[u][v] == d[v]) {
                    pre[v].push_back(u);
                }
            }
        }
    }
}

vector<int> temppath, path;
int send = INF, back = INF;
void DFS(int v) {
    if (v == 0) {       //到达源点
        temppath.push_back(v);
      
      // 题目条件的第二标尺判断
        int need = 0, remain = 0;
        for (int i = temppath.size() - 2; i >= 0; i--) {
            int id = temppath[i];
            if (ci[id] > 0) {
                remain += ci[id];
            }
            else {
                if (remain > abs(ci[id])) {
                    remain -= abs(ci[id]);
                }
                else {
                    need += abs(ci[id]) - remain;
                    remain = 0;
                }
            }
        }
        if (need < send) {        //根据条件更新最佳路径
            send = need;
            back = remain;
            path = temppath;
        }
        else if (need == send&&remain < back) {
            back = remain;
            path = temppath;
        }
        temppath.pop_back();
        return;
    }
    temppath.push_back(v);    //加入v
    for (int i = 0; i < pre[v].size(); i++) {
        DFS(pre[v][i]);
    }
    temppath.pop_back();        //不加入v
}

// 打印path

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
bool SPFA(int s){
    fill(inq,inq+maxn,false);
    fill(num,num+maxn,0);
    fill(d,d+maxn,INF);
    queue<int> q;
    q.push(s);
    inq[s]=true;
    num[s]++;
    d[s]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inq[u]=false;
        for(int j=0;j<adj[u].size();j++){
            int v=adj[u][j].v;
            int dis=adj[u][j].dis;
            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
void Floyd(){
    for(int k=0;k<n;k++){        //依次加入中间结点
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){    //更新i,j之间的最短距离
                if(dis[i][k]!=INF&&dis[k][j]!=INF&&
                dis[i][k]+dis[k][j]<dis[i][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];
                }
            }
        }
    }
}

最小生成树

prime算法

从源点st开始，依次加入集合S的最短边和对应的结点，代码类似Dijkstra ; d[v]=G[u][v] ；//d[]表示与集合S的距离

kruskal算法

不需要源点，边贪心，先对边排序，选择全图中最短边；用并查集，加入边的时候判断会不会构成回路；

拓扑排序

判断有向无环图：用队列；if(num==n) return true;

关键路径

拓扑排序，建立正拓扑，得到ve（最长路径）；逆拓扑，得到vl（较小值）；

动态规划

主要是状态转移方程和边界。状态转移方程需要保证状态无后效性。

数塔

状态转移方程：dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]

序列问题

注意：子序列可以不连续，子串必须是连续的。

最大连续子序列和

O(n^2) -> O(n)

状态转移方程：dp[i]=max{A[i],dp[i-1]+A[i]}。

备注： dp[i]表示以A[i]结尾的连续子序列最大和。

边界：dp[0]=A[0]。

最长不下降子序列

Longest Increasing Sequence, LIS。O(2^n) -> O(n^2)

状态转移方程：dp[i]=max{dp[i], dp[j]+1}。

备注：dp[i]表示以A[i]结尾的LIS长度。

边界：dp[i]=1。

应用：最爱的颜色，给出序列，子序列需要满足eva最爱的颜色序列，求满足要求的最长序列长度； 同样可以用最长公共子序列做（修改方程）。

1
2
3
4
5
6
7
8
9
10
for(int i=1; i<N; i++)
	{
		for(int j=0;j<i;j++)
		{
			if(A[i] >= A[j])
			{
				dp[i] = Math.max(dp[i], dp[j]+1); //状态转移方程
			}
		}
}

最长公共子序列

Longest Common Subsequence, LCS。O(2^(m+n) * max(m,n)) -> O(nm)

状态转移方程：dp[i][j]=dp[i-1][j-1]+1,A[i]==B[j]；dp[i][j]=max{dp[i-1][j],dp[i][j-1]},A[i]!=B[j]；

备注：dp[i][j]表示A[i]和B[j]之前的LCS长度。

边界:dp[i][0]=dp[0][j]=0；

最长回文子串

状态转移方程：dp[i][j]=dp[i+1][j-1],s[i]==s[j]；dp[i][j]=0, s[i]!=s[j]；

备注：dp[i][j]表示s[i]到s[j]的子串是否回文，是为1，不是为0；

边界：dp[i][i]=1,dp[i][i+1]=(s[i]==s[i+1])?1:0

枚举方式需要改变：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int ans = 1;
// 长度为1和2的字符串进行初始化
for (int i = 0; i < len; i++) {
        dp[i][i] = 1;
        if (i < len - 1) {
            if (str[i] == str[i + 1])
            {
                dp[i][i + 1] = 1;
                ans = 2;
            }
        }
}
//取到等号,l为字符串长度
for (int l = 3; l <= len; l++) {    
        for (int i = 0; i + l - 1 < len; i++) {
            int j = i + l - 1;
            if (str[i] == str[j] && dp[i + 1][j - 1] == 1)
            {
                dp[i][j] = 1;
                ans = l;
            }
        }
}

DAG最长路

状态转移方程：dp[i] = max{dp[i], dp[j]+G[i][j]}

备注：dp[i]表示从i号顶点出发能获得的最大路径长度。j为i能到达的顶点。

边界：出度为0的顶点dp[k]=0。当求到达终点T的最大路径长度时，边界为：dp初始化为-INF，dp[T]=0，还需要visit数组标识是否被计算过。

有向无环图：不使用拓扑排序，可以用递归DFS输出路径。

矩形嵌套问题；

序列满足一定前后继关系，求最长序列；

背包

01背包

状态转移方程：dp[i][v]=max{dp[i-1][v],dp[i-1][v-w[i]]+c[i]}

备注：dp[i][v]表示前i件物品恰好装入容量为v的背包中能获得的最大价值。可以把i纬去掉，但是v必须逆序，从V到0（为了保证dp[v-w[i]]是i-1的值）。

边界：dp[v]=0。

1
2
3
4
5
6
7
8
9
10
11
12
fill(dp, dp + maxn, 0);
// 此处因为要按字典序顺序，需要字典序最小的元素最后更新choice
for (int i = n - 1; i >=0; i--) {
  for (int v = V; v >= w[i]; v--) {
    if (dp[v] <= dp[v - w[i]] + w[i]) {
      dp[v] = dp[v - w[i]] + w[i];
      choice[i][v] = true;
    }
    else
      choice[i][v] = false;
  }
}

完全背包

状态转移方程：dp[i][v]=max{dp[i-1][v], dp[i][v-w[i]]+c[i]}

备注：dp[i][v]表示前i件物品恰好装入容量为v的背包中能获得的最大价值。把i维去掉，v需要正向枚举，因为dp[i][v-w[i]]是i时刻的值，需要已经计算过。

点击下方打赏按钮，获得支付宝二维码