发表更新算法12 分钟读完 (大约1764个字)

算法模板总结

​​点击阅读更多查看文章内容

（小菜鸡的第一篇博客保存了一些算法的模板+例题，以防用到的时候找不到）
博客里面都是一些最最最基本的模板，大佬请自动忽略。。。。

一、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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<queue>
const int maxx = 205;
using namespace std;
int n, m;
int vis[maxx][maxx];
int dis[maxx][maxx];
int loc[4][4] = { {-1,0},{1,0},{0,1},{0,-1} };
char s[maxx][maxx];
int ans;
void bfs(int ss,int sd)
{
	//pair<int,int> p;
	//p.first 第一个元素 p.second 第二个元素
	queue<pair<int, int>> q;
	q.push(make_pair(ss, sd));
	vis[ss][sd] = 1;
	while (!q.empty())
	{
		int l = q.front().first;
		int r = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int u = l + loc[i][0];
			int v = r + loc[i][1];
			if (s[u][v] != '#' && u <= n && u > 0 && v <= m && v > 0&&vis[u][v]==0)
			{
				dis[u][v] = dis[l][r] + 1;
				if (s[u][v] == 'x')
					dis[u][v]++;
				vis[u][v] = 1;
				q.push(make_pair(u, v));
				if (s[u][v] == 'r'&&dis[u][v]<ans)
					ans=dis[u][v];
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	int ss, sd;
	while (cin >> n >> m)
	{
		memset(vis, 0, sizeof vis);
		memset(dis, 0, sizeof dis);
		ans = 99999;
		for (int i = 1; i <= n; i++)
		{
			cin >> (s[i] + 1);
			for (int j = 1; j <= m; j++)
			{
				if (s[i][j] == 'a')
				{
					ss = i;
					sd = j;
				}
			}	
		}
		bfs(ss, sd);	
		if (ans==99999)
		{
			cout << "Poor ANGEL has to stay in the prison all his life.\n";
     	}
		else
			cout <<ans << endl;
	}
}

二、DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs()
{
	if (到达终点状态)
	{
		...
			return;
	}
	if (越界或者是不合法状态)
		return;
	if (特殊状态)
		return;
	for (扩展方式)
	{
		if (扩展方式所到达状态合法)
		{
			修改操作;//根据题意来添加标记
			dfs();
			还原标记;
			//是否还原标记根据题意
			//如果加上(还原标记)就是回溯法
		}
	}
}

三、DP

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
//动态规划dp
//过河卒 洛谷P1002
#include<iostream>
using namespace std;
int a[25][25] = {0};
int dp[25][25] = {0};
int fx[8] = { 2,1,-1,-2,-2,-1,1,2 };
int fy[8] = { 1,2,2,1,-1,-2,-2,-1 };
int n, m, p, q;

void init()
{
	a[p][q] = 1;
	for (int i = 0; i <= 7; i++)
	{
		if (p + fx[i] >= 0 && p + fx[i] <= n  && q + fy[i] >= 0 && q + fy[i] <= m )
		{
			a[p + fx[i]][q + fy[i]] = 1;
		}
	}
}

void dpp()
{
	dp[0][0] = 0;
	for (int j = 1; j<=m; j++)
	{
		if (a[0][j] != 1)
			dp[0][j] = 1;
		else
			break;
	}
	for (int i = 1; i<=n; i++)
	{
		if (a[i][0] != 1)
			dp[i][0] = 1;
		else
			break;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (a[i][j] == 1)
				dp[i][j] == 0;
			else
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		}
	}
}

int main()
{
	cin >> n >> m >> p >> q;
	init();
	dpp();
	cout << dp[n][m];
}

四、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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
using namespace std;

void makeNext(const char P[], int next[])
{
	int q, k;//q是当前要计算第q个字符的next值，k是对应的next值
	int m = strlen(P);
	next[0] = 0;
	for (q = 1, k = 0; q < m; q++)
	{
		while (k > 0 && P[k] != P[q])
		{
			k = next[k - 1];
		}
		if (P[q] == P[k])
		{
			k++;
		}
		next[q] = k;
	}
}

int  kmp(const char T[], const char P[], int next[])
{
	int n, m;
	n = strlen(T);
	m = strlen(P);
	makeNext(P, next);
	int i = 0;
	int j = 0;
	while (i < n && j < m)
	{
		if ( j==0||T[i] == P[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j-1];
		}
	}
	if (j == m)
		return  i - m + 1;
	else
		return -1;
	
}
int main()
{
	int next[100] = { 0 };
	char T[] = "abababababc";
	char P[] = "abc";
    cout<<kmp(T, P, next);
    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
#include<iostream>
using namespace std;
bool str[100010]; 					//开始定义一个全局变量数组 
void prime()						//这个函数可以将1~100010内的所有素数都找出来，所以在main()函数开头执行一遍就行了 
{
	str[1] = 1;						//希望读者能将这一块跟第二种方法进行一个比较，便于理解 
	for (int i = 2; i * i <= 100010; i++)
	{
		if (!str[i])
		{
			for (int j = i * i; j <= 100010; j += i)
				str[j] = 1;
		}
	}
}
int main()
{
	prime(); 						 //执行程序开始的打表操作 
	int n;
	while (cin >> n)
	{
		if (str[n]) cout << "不是素数！" << endl; 	//判断是否为素数 
		else cout << "是素数！" << endl;
	}
	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
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<queue>
#include<vector>
using namespace std;
const int MX = 500 + 10;
int N, M;
vector<int>G[MX];//可约当做声明了一个二维数组
int indegree[MX];//记录各定点入度的数组
queue<int>q;

//初始化，将AOV网存储到数据结构中
void init()
{
	for (int i = 1; i <= M; i++)//M是关系数
	{
		int node1, node2;
		cin >> node1 >> node2;
		G[node1].push_back(node2);
		//在G[node1]的尾部加入数据node2，表示node2是node1的直接后继
		indegree[node2]++;//node2的入度加一
	}
}

int topo_sort()
{
	for (int i = 1; i <= N; i++)
		if (indegree[i] == 0)
			q.push(i);//若i的入度为0，则将i入队
	int cnt = 0;
	while (!q.empty())
	{
		cnt++;
		int tmp = q.front();//记录当前队头元素
		q.pop();
		for (int i = 0; i < G[tmp].size(); i++)//遍历当前队头元素tmp的所有直接后继
		{
			int node = G[tmp][i];//node记录tmp的第i个直接后继（i从0开始）
			indegree[node]--;
			if (indegree[node] == 0)
				q.push(node);//入度为0，则入队
		}
		if (!q.empty())
			cout << tmp << " ";
		else
			cout << tmp;//使最后一个输出数据后面无空格
	}
	if (cnt < N)
		return -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
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
include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 26;
struct Trie
{
    // 代表当前节点可以延伸出的边，数量可变
    Trie* Next[MAXN];
    // 标记当前节点是否是保存信息的结尾，也可以代表前缀个数
    int Flag;
    Trie()
    {
        // 初始化以该信息为前缀的信息个数
        Flag = 1;
        memset(Next, NULL, sizeof(Next));
    }
};

Trie* root = new Trie();

void Insert(string s)
{
	int len = s.length();
	int id;
    Trie* p = root;
    Trie* q;
    //将s的每一个字符插入trie树
	for (int i = 0; i < len; i++)
	{
        id = s[i] - 'a';
        //如果没有边，则新建一个trie节点，产生一条边，用以代表该字符。
        if (p->Next[id] == NULL)
        {
            q = new Trie();
            p->Next[id] = q;
            p = p->Next[id];
        }
        //如果存在边，则沿着该边走。
        else
        {
            p = p->Next[id];
            //累加以该信息为前缀的信息个数
            ++(p->Flag);
        }
	}
}

int Query(const char* str)
{
    int len = strlen(str);
    Trie* p = root;
    //在trie树上顺序搜索str的每一个字符
    for (int i = 0; i < len; ++i)
    {
        int id = str[i] - 'a';
        p = p->Next[id];
        if (p == NULL)
            return 0;
    }
    return p->Flag;
}

void Free(Trie* T)
{
    if (T == NULL)
        return;
    //释放trie树的每一个节点占用的内存
    for (int i = 0; i < MAXN; ++i)
    {
       if(T->Next[i])
        Free(T->Next[i]);
    }
    delete(T);
}

int main()
{
    const char* word[4] = {"banana","band","bee","absolute"};
    const char* fore[4] = { "ba","b","band","abc" };
    for (int i = 0; i < 4; i++)
    {
        Insert(word[i]);
    }

    for (int i = 0; i < 4; i++)
    {
        cout << Query(fore[i]) << endl;
    }
}

八、最短路径

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
//最短路径
// 1.floyed  时间复杂度O(n三次方)
/*void floyed()
{
	for (int i = 1; i <= n; i++)//通过中间顶点进行中转
	{
		for (int k = 1; k <= n; k++)//k为所有的起点
		{
			for (int j = 1; j <= n; j++)//j为终点
			{
				m[k][j] = min(m[k][j], m[k][i] + m[i][j]);
			}
		}
	}
	return;
}*/
// 2.Dijkstra 时间复杂度O(n平方)
void Dijkstra()
{
	for (int i = 1; i <= n - 1; i++)
	{
		//找到离1号顶点最近的顶点
		min1 = inf;//inf为无穷大
		for (int j = 1; j <= n; j++)
		{
			if (book[j] == 0 && dis[j] < min1)//找到距离起点最近的点
			{
				min1 = dis[j];//更新离当前顶点最近的顶点
				u = j;
			}
		}

		book[u] = 1;//标记u这个点进入S集合
		for (int v = 1; v <= n; v++)
		{
			if (e[u][v] < inf)//u,v之间想通
			{
				if (dis[v] > e[u][v] + dis[u])//松弛
				{
					dis[v] = dis[u] + e[u][v];//更新最短的路径
				}
			}
		}
	}
}

九、快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void quickSort(int s[], int l, int r)
{
    int mid = s[(l + r) / 2];
    int i = l, j = r;
    do
    {
        while (s[i] < mid)
            i++;
        while (s[j] > mid)
            j--;
        if (i <= j)
        {
            swap(s[i], s[j]);
            i++;
            j--;
        }
    } while (i <= j);
    if (l < j)
        quickSort(s, l, j);
    if (i < r)
        quickSort(s, i, r);
}

十、背包

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
//01背包
#include <bits/stdc++.h>
using namespace std;
int n,v,w,c,dp[1010];//dp[i]表示装入物品的质量为i时能获得的最大价值
int main()
{
    cin>>v>>n;//v为背包容量，n为物品数量
    for(int i=1;i<=n;i++)
    {
        cin>>w>>c;//w为每个物品重量，c为每个物品价值
        for(int j=v;j>=w;j--)//背包容量从大到小遍历
        dp[j]=max(dp[j],dp[j-w]+c);//选择不放入背包dp[j]还是放入背包dp[j-w]+c，更新为最大的dp[j]
    }
    printf("%d\n",dp[v]);//装入物品的质量为v时能获得的最大价值
    return 0;
}
//完全背包
#include <bits/stdc++.h>
using namespace std;
int n,v,w,c,dp[100010];
int main()
{
    cin>>v>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w>>c;
        for(int j=w;j<=v;j++)//背包容量从小到大遍历，这里与01背包循环顺序相反！
        dp[j]=max(dp[j],dp[j-w]+c);
    }
    printf("%d\n",dp[v]);
    return 0;
}

算法模板总结

https://shnpd.github.io/2020/12/18/算法模板总结/

作者

ShiHaonan

发布于

2020-12-18

更新于

2025-03-13

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

目录

最新文章

分类

×