C++柳诺的stl+模板总结

文章目录

• • 模板
  • DFS
  • 二叉树
  • [Counting leaves](https://pintia.cn/problem-sets/994805342720868352/problems/994805521431773184)
  • BFS
  • 最短路
  • • Dijkstra迪杰斯特啦
  • 并查集
  • string类
  • vector
  • set
  • map
  • stack
  • queue
  • sort
  • tostring
  • stoi、stod可以将字符串string转化为对应的int型、double型变量

模板

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

stack

queue

sort

对vector排序：
std::sort(s.begin(),s.end(),cmp);
vector s;

直接set.find()!=set.end()不就好了吗？？vector遍历又麻烦又超时！

tostring

stoi、stod可以将字符串string转化为对应的int型、double型变量