[数据结构与算法] C++柳诺的stl+模板总结

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> C++柳诺的stl+模板总结 -> 正文阅读

[数据结构与算法]C++柳诺的stl+模板总结

文章目录

模板

bool isPrime(int n) {
    if (n == 0 || n == 1) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

中序加后序建树
在这里插入图片描述

Djstl最短路：

const int N = 1010, INF = 0x3f3f3f3f;
int g[N][N];
int a[N];
int n, m;
int check()
{
    int used[N] = {0},dist[N] = {0};
    memset(dist,0x3f,sizeof dist);
    dist[a[1]] = 0;
    for(int i = 1 ; i <= n; i ++)
    {
        int u = -1;
        for(int v = 1 ; v <= n ; v ++)
            if(!used[v] && (u == -1 || dist[u] > dist[v] )) u = v;
        if(dist[u] != dist[a[i]])
            return 0;
        used[u] = 1;
        for(int v = 1 ; v <= n; v ++)
            if(v == u) continue;
            else dist[v] = min(dist[v],dist[u]+g[u][v]);
    }
    return 1;
}

int main()
{
    
    scanf("%d %d", &n, &m);
    memset(g, 0x3f, sizeof(g));
    for(int i = 0 ; i < m ; i++)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        g[a][b] = g[b][a] = c;
    }
    int k;
    scanf("%d",&k);
    for(int i = 0 ; i < k ; i++)
    {
        for(int j = 1 ;j <= n ; j++)
            scanf("%d", &a[j]);
        if(check()) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}

在这里插入图片描述

DFS

在这里插入图片描述

二叉树

在这里插入图片描述

Counting leaves

vector<int> t[100];
int d[100]={0},manh=0;
void dfs(int index,int depth){
    manh=max(manh,depth);
    if(t[index].size()==0){
        d[depth]++;
        return;
    }
    for(int i=0;i<t[index].size();i++)
        dfs(t[index][i],depth+1);
}

    dfs(1,1);

BFS

在这里插入图片描述

最短路

Dijkstra迪杰斯特啦

在这里插入图片描述

并查集

在这里插入图片描述

string类

在这里插入图片描述
c_str() 以 char* 形式传回 string 内含字符串
如果一个函数要求char*参数，可以使用c_str()方法：
string s = “Hello World!”;
printf(“%s”, s.c_str()); //输出 “Hello World!”
string反转：
string s = "hello";reverse(s.begin(),s.end());

vector

在这里插入图片描述
v1.resize(len,value)：长度为len，len个元素值都为value

在这里插入图片描述

set

在这里插入图片描述

map

在这里插入图片描述
如果偶尔刷题时候?map或者set超时了，可以考虑?
unordered_map（或者unordered_set）缩短代码运?时间、提?代码效率～?于?法和map、set
map.find()!=map.end()
是?样的～

else if (num == 3) {
            unordered_map<string, int> m;
            for (int j = 0; j < n; j++)
                if (v[j].t.substr(4, 6) == s) m[v[j].t.substr(1, 3)]++;
            for (auto it : m) ans.push_back({it.first, it.second});
        }//ans is vector