复杂算法总结

1.dfs

模板样例

//走河卒(适用低数据复杂度)

#include<iostream>
using namespace std;
int n,m,ans,mx,my;
int vis[26][26];
int dx[]={0,1},dy[]={1,0},dX={1,-1},dY={2,-2};
int ju(int x,int y)
{
    return x>=0&&x<=n&&y>=0&&y<=n;
}
void dfs(int x,int y)
{
    if(x==n&&y==m)
    {
        ans++;
        return;
    }
    for(int i=0;i<2;i++)
    {
        int nx=dx[i]+x,ny=y+dy[i];
        if(ju(nx,ny)||vis[nx][ny])continue;
        dfs(nx,ny);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    cin>>n>>m>>mx>>my;
    for(int i=0;i<2;i++)//标记不能走的
        for(int j=0;j<2;j++)
        {
             mx+=dX[i],my+=dY[i];
            if(ju(mx,my))vis[mx][my]=1;
            mx+=dX[j],my+=dY[i];
            if(ju(mx,my))vis[mx][my]=1;
        }
    dfs(0,0);
}

//迷宫

 #include <iostream>
using namespace std;
 int n, m, x1, y1, t, x, y, tx, ty, cnt;
 int a[6][6], book[6][6];
 int dx[4] = { 0, 0, 1, -1 };
 int dy[4] = { 1, -1, 0, 0 };
 void dfs(int x, int y) {
if (x == x1 && y == y1) {
    cnt++;
    return;
}

book[x][y] = 1;

for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];

    if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && book[nx][ny] == 0 && a[nx][ny] != -1) {
        dfs(nx, ny);
    }
}
book[x][y] = 0; // Reset the book[x][y] after backtracking
}

 int main() {
ios::sync_with_stdio(false);

cin >> n >> m >> t >> x >> y >> x1 >> y1;

for (int i = 1; i <= t; i++) {
    cin >> tx >> ty;
    a[tx][ty] = -1;
}
cnt = 0; // Initialize cnt
dfs(x, y);
cout << cnt << endl;
return 0;
 }

2.floodfill算法

链接：https://www.acwing.com/activity/content/code/content/7518658/

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char a[N][N];
int n,m;
bool v,vis[N][N];
int d[8][2]={{0,1},{1,0},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};
void dfs(int x,int y)
{
    vis[x][y]=true;
    for(int i=0;i<8;i++)
    {
        int nx=d[i][0]+x,ny=y+d[i][1];
        if(a[nx][ny]=='W'&&nx>0&&nx<=n&&ny>0&&ny<=m&&!vis[nx][ny])
       dfs(nx,ny);
    }
}
int main()
{
    ios::sync_with_stdio(false);cin.tie();cout.tie();
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)cin>>a[i][j];
    long long cnt=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        if(a[i][j]=='W'&&!vis[i][j])
        {
            dfs(i,j);
             cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

2.bfs

洛谷---地下城主

走迷宫模板

#include<iostream>
using namespace  std;
#include<queue>
char e[31][31][31];
int a, b, c;
int dx[] = { 0,0,1,-1,0,0 }, dy[] = { 1,-1,0,0,0,0 }, dz[] = { 0,0,0,0,1,-1 };
struct node {
    int x, y, z, t;//x代表横坐标，y代表纵坐标，z代表高坐标，t代表当前是第几个
};
queue<node>p;

bool ju(int x, int y, int z)
{
    return (x >= 1 && x <= b && y >= 1 && y <= c && z >= 1 && z <= a&& e[x][y][z] != '#') ? true : false;
}
int bfs(int x, int y, int z, int mx, int my, int mz)
{
    e[x][y][z] ='#';//代表当前点位已经走过
        p.push(node{ x,y,z });//入队
    while (!p.empty())//判断队列是否为空//循环判断枚举周围元素
    {
        int xx = p.front().x;
        int yy = p.front().y;
        int zz = p.front().z;
        int tt = p.front().t;
        p.pop();//出队
        for (int i = 0; i < 6; i++)
        {
          int  nx = xx + dx[i], ny = yy + dy[i], nz = zz + dz[i];
            if (nx == mx && ny == my && nz == mz)return tt + 1;
            if (ju(nx, ny, nz))
            {
                e[nx][ny][nz] = '#';//标志走过
                p.push(node{ nx,ny,nz,tt + 1 });//入队新的元素
            }
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> a >> b >> c;
    int i, j, k, i1, j1, k1;
    for (int z = 1; z <= a; z++)
        for (int x = 1; x <= b; x++)
            for (int y = 1; y <= c; y++)
            {
                cin >> e[x][y][z];
                if (e[x][y][z] == 'S')
                    i = x, j = y, k = z;
                else if (e[x][y][z] == 'E')
                    i1 = x, j1 =y, k1 = z;
            }
    int cnt = bfs(i, j, k, i1, j1, k1);
    if (cnt)
    {
        cout << "Escaped in " << cnt << " minute(s).";
    }
    else
        cout << "Trapped!";
    return 0;
}

3.hash表

hash用来解决映射，字符串比较问题

char a[100000]="anbsduijfbjafcnak";

如上是一个字符串

给定一个P作为标准值 通常为131与13331

将字符串看成一个p进制的数

ha[i]=ha[i-1]*P+a[i];//每个数值由ascill码值代替，递推式

p[i]=p[i-1]*P;//每一个阶段的P数用来实现字符串区间比较

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
ull P=131;
ull a[10010];
char s[10010];
int n,ans=1;//ans初始化为1，因为至少一个序列
ull hashs(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=ans*P+(ull)s[i];//计算hash值
    return ans;
}
main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",s);
        a[i]=hashs(s);
    }
    sort(a+1,a+n+1);
    for (int i=2;i<=n;i++)//排序过了，所以相邻比较就行了
        if (a[i]!=a[i-1])
            ans++;
    printf("%d\n",ans);
}

4.双指针

1.双指针去重(set直接排序去重)

//o(nlogn)时间复杂度，主要是排序带来的
#include<iostream>
using namespace std;
#include<algorithm>
const int N = 10000;
int a[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + 1 + n);
    int l = 1, r = 2;
    while (l <= r && l <=n)
    {
        if (a[l] != a[r])
        {
            cout << a[l] << ' ';
            l++, r++;
        }
        else
            l = r, r = r + 1;
               
    }
    return 0;
}

5.二分

//lower_bound upper_bound    

6.一维二维坐标转换

x*一行的元素数量+y

acwing--八数码问题
八数码问题(算法基础课)------经典bfs问题

//用map保存步数，如果考是否达到状态，用set去重也可以
#include<bits/stdc++.h>
using namespace std;
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};
int bfs(string s)
{
    unordered_map<string,int>dist;
    string end="12345678x";
    queue<string>q;
    dist[s]=0;
    q.push(s);
    while(q.size())
    {
        auto t=q.front();q.pop();
        int r=dist[t];
          if(t==end)return r;
        int e=t.find('x');
        int x=e/3,y=e%3;
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i],ny=y+dy[i];
           int f=nx*3+ny;
           if(nx<0||nx>2||ny<0||ny>2)continue;
           swap(t[f],t[e]);
           if(dist[t]==0)
           {
               dist[t]=r+1;
           q.push(t);
           }
             swap(t[f],t[e]);           
        }
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie();cout.tie();
    string s;
 for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++)
    {
        char c;
        cin>>c;
        s+=c;
    }
    cout<<bfs(s);
    return 0;
}

跳蚱蜢(蓝桥杯)-----八数码类问题

用set,map去重都可以

7.并查集求反集

反集合并

在初始化并查集时我们初始化两倍于数据范围大小的并查集，超出数据范围部分称为反集，用来储存性质于并查集维护集合相反的集合。 并且两个集合中的元素性质互斥。 并查集的反集适用于只有元素只有两种性质的题目，也就是说，这个元素不属于并查集维护集合，则其必定属于另一个集合。

洛谷p1892----团伙

关于反集

我也是做这道题才知道的

如果a和b是敌人，合并n+b和a，n+a和b

如果c和a是敌人，合并n+c和a，n+a和c

那么b和c就并在一起了

这样就符合了题目敌人的敌人是朋友的规则

  for(int i=1;i<=n*2;i++)//初始化两倍数据范围
      p[i]=i;  
f[find(a+n)]=find(b);
 f[find(b+n)]=find(a);//反集合并

#include<bits/stdc++.h>
using namespace std;
int p[5010],q[5010];
int n,m;
int find(int x)
{
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}

int main()
{
    ios::sync_with_stdio(false);cin.tie();cout.tie();
    cin>>n>>m;
      for(int i=1;i<=n*2;i++)
      p[i]=i;
    while(m--)
    {
        char a;
        cin>>a;
        if(a=='F')
        {
            int x,y;
            cin>>x>>y;
            p[find(x)]=find(y);
        }
        else
        {
            int x,y;
            cin>>x>>y;
            p[find(x+n)]=find(y);
            p[find(y+n)]=find(x);
        }
    }
    long long res=0;
   for(int i=1;i<=n;i++)if(p[i]==i)res++;
   cout<<res;
    return 0;
}

本栏目推荐文章
• 2024/1/13 算法笔记
• Openharmony 跑 CV 算法
• .NET中的加密算法总结(自定义加密Helper类续)
• 算法练习题
• 算法学习Day26组合总和、分割回文串
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• 【SPFA】最短路的一种算法
• [Python学习记]个人感受(持续更新）
• arthas热更新class
• 基于融合语义信息改进的内容推荐算法。Improved content recommendation algorithm integrating semantic information.

实时更新 算法 实时实时更新 算法 实时 一体机 算法 实时 边缘 网关 高楼 算法 实时 算法 实时facebook浏览器 风电 粒子 算法 实时 算法 实时 深度 专题 实时 实时更新 实时性 实时flink