PAT甲级C++总结（二）

1.STL 中的find(begin,end,val)方法用于查找某对象，begin和end为查找的首尾地址，区间是左闭右开，val为查找的值，如果找到将返回指定的地址，如果没找到，将返回参数end

2.dfs算法中，如果对于图的路径数组maps[N][N]出现了内存受限，可以使用vector<int> maps[N]来替代

3.deque插入元素：push_back(),push_front()分别是从后插入元素和从前插入元素
删除元素：pop_back(),pop_front()分别是从后面删除元素和从前删除元素

4.用scanf为string赋值的方法：先用scanf用char数组赋值，再用char数组为string类型赋值

char n[100];
scanf("%s",n);
string s=string(n);

5.dfs通常的vis数组的写法用于无向图，对于有向图的深度优先遍历这里提供一个思路，设置一个map<type,vector<type>>的容器，type类型表示每个结点，把每个路径都设置给对应的容器[type],这样在写dfs的时候对这个容器遍历即可,下面案例只有关键部分的代码

map<string,vector<string>> relates;
void dfs(string a){
    vis[a]=1;
    cnt++;
    total+=times[a];
    if(times[a]>times[head]){
        head=a;
    }
    for(unsigned int i=0;i<relates[a].size();i++){
        if(vis[relates[a][i]]==0){
            dfs(relates[a][i]);
        }
    }
}
int main(){
for(int i=0;i<n;i++){
        string a,b;
        int time;
        cin>>a>>b>>time;
        relates[a].push_back(b);
    }
    return 0;
}

6.对树的序列遍历无非是想办法找到一个任意根结点的左右子树的根，然后按照指定的序列进行递归，下面是一个先序遍历的例子（取自柳神代码）：

void getpost(int root, int tail) {
    if(root > tail) return ;
    int i = root + 1, j = tail;
    if(!isMirror) {
        while(i <= tail && pre[root] > pre[i]) i++;
        while(j > root && pre[root] <= pre[j]) j--;
    } else {
        while(i <= tail && pre[root] <= pre[i]) i++;
        while(j > root && pre[root] > pre[j]) j--;
    }
    if(i - j != 1) return ;
    getpost(root + 1, j);
    getpost(i, tail);
    post.push_back(pre[root]);
}

7.代码中出现两层遍历往往可能会超时，这时如果想不到别的方法怎么办，尝试用二分法遍历来代替第二层遍历吧

8.写链表题一定要注意数据里可能会有不在链表中的多余结点，在进行操作前需要先进行排序