PAT甲级题目

西红柿炒鸡蛋

发布于 2020-03-20 17:30:38

4460

发布于 2020-03-20 17:30:38

文章被收录于专栏：自学笔记自学笔记

PAT甲级的题目有关于树的题目，1053，1086，1090，1102，1106，1115，1119，1038，1110，1020，1043

A1053

这题目比较简单，给定一棵树，给定一个数字，要你找到所有和等于给定数字的路径。这个题目的树没有给出是二叉树，自然不能按照原来二叉树的方法来构建了。其实就是BFS，用DFS也是可以的，不过考虑到DFS还要新开一个数组来存储路径，还是使用BFS。首先是树的结构，只需要在原来二叉树的基础上修改一下就好了。

typedef struct treeNode {
    int val;
    int weight;
    vector<struct treeNode *> generator;
    int parent = -1;
} *TreeNode, treeNode;

把原来的左右子树修改成一个vector存储即可。树的结构中新添加了一个parent，是用于找到根节点，因为题目给出的树是一个列表，接着是树的父节点，不添加parent找不到父节点。如果parent是-1那么就是根节点了。

TreeNode createTree(int n, TreeNode *array, int allNodes) {
    for (int i = 0; i < n; ++i) {
        int index;
        int num;
        cin >> index >> num;
        index_map[index] = true;
        for (int j = 0; j < num; ++j) {
            int next;
            cin >> next;
            array[next]->parent = index;

            array[index]->generator.push_back(array[next]);

        }
        sort(array[index]->generator.rbegin(), array[index]->generator.rend(), cmp);

    }

    for (int k = 0; k < allNodes; ++k) {
        if (array[k]->parent == -1) {
            return array[k];
        }
    }
    return nullptr;
}

创建树的过程，注意后面有一个排序操作，题目的输出要求按照次序输出。然后就是BFS操作了。

void findWeights(TreeNode root, int sum, vector<int> weightsAdd, int equalWeights) {
    if (sum > equalWeights) {
        return;
    } else if (sum < equalWeights) {
        sum += root->weight;
        weightsAdd.push_back(root->weight);
        if (sum == equalWeights) {

            if (!index_map[root->val]) {
                weights_path.push_back(weightsAdd);
                weightsAdd.clear();
            }
            return;
        }
        for (int i = 0; i < root->generator.size(); ++i) {
            TreeNode current = root->generator[i];
            findWeights(current, sum, weightsAdd, equalWeights);
        }
    }
}

BFS把weightsAdd当成是一个拷贝过来的局部变量，不需要回滚操作，比DFS简单多了。然后就是输出了，只需要注意最后不要空格就好。其实也可以用数组来完成，所占空间可能更小。

1086

这个题目做了很久，要是在上机考试碰见这个题目应该就只有10来分了。题目大意是给定一个入栈出栈的序列，这个出入栈完成后得到的出栈序列是中序遍历的序列，要你求这棵树的后续遍历。我直接从序列入手，发现push操作就是：如果当前节点有左子树，就插入左子树，否则就插入右子树；pop操作是回退到上一课树，按照这个操作就可以创建出一棵树，然后后续遍历即可。然而内存爆炸了。

之前考408的时候遇到过这样的操作，好像是天勤ds里面，中序遍历如果使用栈来实现，入栈顺序就是前序遍历次序。所以题目表面上是给了一个序列，实际上给了前序和中序遍历，让你求后续遍历。这个就很简单了。

TreeNode create(int preL, int preR, int inL, int inR, int *preOrder, int *inOrder) {
    int rootNum = preOrder[preL];
    TreeNode root = new treeNode;
    root->val = rootNum;
    if (preL == preR) {
        root->val = rootNum;
        root->leftChild = root->rightChild = nullptr;
        return root;
    }

    if (preL > preR) {
        return nullptr;
    }

    int mid = -1;

    for (int i = inL; i <= inR; ++i) {
        if (inOrder[i] == rootNum) {
            mid = i;
            break;
        }
    }

    int leftNumber = mid - inL;
    int rightNumber = inR - mid;

    root->leftChild = create(preL + 1, preL + leftNumber, inL, mid - 1, preOrder, inOrder);
    root->rightChild = create(preR - rightNumber + 1, preR, mid + 1, inR, preOrder, inOrder);
    return root;
}

关键就是创建树的操作，天勤的代码题出过这类，主要就是前中序遍历的边界数对就行。

1090

这个题目一开始读的没太懂，两次都超了，只有14分。一开始还以为最后要给出的是路径上零售商的数量，没想到是路径的个数。很明显是BFS，和上上题一样：

//typedef struct treeNode {
//    int val;
//    vector<struct treeNode *> children;
//    int parent = -1;
//} *TreeNode, treeNode;

double maxPrice = -1;
int maxNumber = -1;

//void BFS(TreeNode root, double currentPrice, double r, vector<int> path) {
//    if (root) {
//        path.push_back(root->val);
//        currentPrice = currentPrice * ((100 + r) / 100);
//        if (maxPrice < currentPrice) {
//            maxPrice = currentPrice;
//            maxNumber = path.size();
//        }
//        for (int i = 0; i < root->children.size(); ++i) {
//            BFS(root->children[i], currentPrice, r, path);
//        }
//    }
//}

建树是不行的，直接就内存爆炸。如此那就直接用数组吧，于是想到从尾巴开始，然而题目有关键一句：It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.假设在供应链上的每名成员都只有一个供应者，除了根部的供应者，没有环，那么就不需要像图一样设置访问标记。

//    for (int j = 0; j < n; ++j) {
//        if (!visited[j]) {
//            int paths = 0;
//            int fa = array[j];
//            while (fa != -1) {
//                visited[fa] = true;
//                fa = array[fa];
//                paths++;
//            }
//            maxNumber = ((maxNumber > paths) ? maxNumber : paths);
//        }
//    }

还是超时了，因为如果从底部开始，会出现很多重复的道路，所以最好还是从底部开始访问，我也是在这里看了别人题解之后才知道，原来输出的最后一个数字应该是路径的个数，翻译错了。

vector<int> v[100010];

void bfs(int root, int depth) {
    if (v[root].size() == 0) {
        if (maxPrice < depth) {
            maxPrice = depth;
            maxNumber = 1;
        } else if (maxPrice == depth) {
            maxNumber++;
        }
        return;
    }
    for (int i = 0; i < v[root].size(); ++i) {
        bfs(v[root][i], depth + 1);
    }
}

用一个vector数组把所有儿子串起来，遍历访问即可。

1102

输入详情：每一个输入包含了一个测试样例。对于每一个例子，第一行给出一个正整数，也及是树的总节点数，因此，节点编号从0到N-1，然后下面N行每一行对应节点0到N-1，每一行给出左右子树。如果子树不存在，用-来代替，每一对孩子用空格分离。

输出详情：对于每一个样例，第一行打印翻转树的层序遍历序列，然后第二行打印翻转树的中序遍历序列，用空格隔开，最后不能有空格。

这个题目就非常简单了，唯一的考点就是交换两树的左右子树，直接后序遍历交换就好了，释放树的内存也是后序遍历实现。

    for (int i = 0; i < n; ++i) {
        array[i].val = i;
        string left, right;
        cin >> left >> right;
        if (left == "-") {
            array[i].leftChild = nullptr;
        } else {
            array[i].leftChild = &array[string2Number(left)];
            array[string2Number(left)].parent = i;
        }
        if (right == "-") {
            array[i].rightChild = nullptr;
        } else {
            array[i].rightChild = &array[string2Number(right)];
            array[string2Number(right)].parent = i;
        }
    }

创建树和前面几个题目一样。

void postExchange(TreeNode root) {
    if (root) {
        postExchange(root->leftChild);
        postExchange(root->rightChild);

        TreeNode temp = root->leftChild;
        root->leftChild = root->rightChild;
        root->rightChild = temp;
    }
}

1106

一条供应链网络由零售商，经销商，供应商组成，每一总角色在这条网络（产品从生产者到消费者）中都起到相应的作用。从根节点的供应者开始，每个人从供应商以P的价格购买，以比P价格高上百分之r的价格卖给经销商或者是零售商。只有零售商才会面对客户，假设每一个成员只有一个提供者，而且没有循环。

输出详情：每一个输入包含一个测试样例。对于每一个样例，第一行包含一个正整数，标识供应链中成员总数，P标识根供应者的价格，也就是初始价格。r是比率，每经过一个经销商或者是零售商价格需要提升r比率。接下来N行中，每一行描述的格式：K,ID,......。第i行中Ki表示总共有Ki个接受者，其实就是说第i号的提供者有这么多个接受者。中间空格隔开。

输出详情：对于每一个测试样例，打印出零售商的最低价格，也就是最后一个`叶子的最低价格，精确到四位小数，有多少个零售商可以拿到最低价格。

读完题，一看就知道BFS，和前面那道题没有什么区别。

void BFS(int root, int depth, treeNode *array) {

    if (depth > minDepth && minNumber > 0) {
        return;
    }

    if (array[root].childen.size() == 0) {
        if (depth < minDepth) {
            minDepth = depth;
            minNumber = 1;
        } else if (depth == minDepth) {
            minNumber++;
        }
        return;
    }
    for (int i = 0; i < array[root].childen.size(); ++i) {
        BFS(array[root].childen[i], depth + 1, array);
    }
}

仅仅修改此处即可。不过值得注意的是，我一开始是创建了一颗树，后来发现超时，我一开始还以为是递归调用超时，于是我添加了：

    if (depth > minDepth && minNumber > 0) {
        return;
    }

如果已经找到了一个更短的，那么如果还有，要么和其相同，要么更短，所以如果还有比他长的直接去掉。但是加上后PAT评测的时间有减少，但是还是有两个数据是段错误，修改一下，把一些多余数据去掉就可以了。推测原因应该是内存超限了。

1115

这个题目就不翻译了，非常简单，就要你找倒数第一和倒数第二层的节点数加起来。层序遍历是最为适合的了，BFS也可以。关键有几个地方，构建树：

TreeNode insert(TreeNode root, int num) {
    if (root) {
        if (root->val < num) {
            root->rightChild = insert(root->rightChild, num);
        } else {
            root->leftChild = insert(root->leftChild, num);
        }
        return root;
    } else {
        root = new treeNode;
        root->val = num;
        root->leftChild = root->rightChild = nullptr;
        return root;
    }
}

在树的结构中添加一个层次属性，记录属于第几层。

void level(TreeNode root) {
    fill(depth, depth + MAX, 0);
    queue<TreeNode> Queue;
    Queue.push(root);
    while (!Queue.empty()) {
        TreeNode cur = Queue.front();
        Queue.pop();
        depth[cur->depth]++;
        maxDepth = ((maxDepth > cur->depth) ? maxDepth : cur->depth);
        if (cur->leftChild) {
            cur->leftChild->depth = cur->depth + 1;
            Queue.push(cur->leftChild);
        }
        if (cur->rightChild) {
            cur->rightChild->depth = cur->depth + 1;
            Queue.push(cur->rightChild);
        }
    }
}

每一次取出节点的时候顺便直接存进数组里面计数，免得害得遍历一次数组。水题一道。

1119

假设在二叉树中所有的关键字都是互不相同的正整数。一颗独一无二的二叉树可以由一对后序和中序遍历序列得到，或者是前序和中序得到。但是，如果只给了后续和前序遍历，那么对应的二叉树并非是唯一的。

现在给一串后序和中序遍历序列，你应该要输出对应的中序遍历的序列，如果此树不唯一，只需要输出他们其中一个即可。

输入详情：每一个输入包含一个测试样例，对于每一个样例，第一个是一个正整数，表示整个二叉树有多少个节点。第二行给出前序遍历序列，第三行给出后续遍历序列，所有的数字之间右空格分隔。

输出详情：对于每一个测试样例，如果树是唯一的，输出yes，如果不是，输出no。下一行输出中序遍历序列。如果解不是唯一的，任何答案都可以。保证至少有一个解。

这个题目第一眼看到是一点思路都没有，上了考场标准0分。首先分析一下前序遍历和后续遍历。前序遍历：根，左子树，右子树；后序遍历：左子树，右子树，根。那么如果这一棵树都有左右子树，那么这棵树就是唯一的，如果这棵树只有左子树，或者右子树，那就有可能有多种情况，这唯一的一棵树可以在左边也可以在右边。这也就是为什么不能唯一确定的原因，这个问题在考408的时候都没有深究。

那么关键就是切分了：

TreeNode create(int preL, int preR, int postL, int postR, int *preSequences, int *postSequences) {
    if (preL > preR) {
        return nullptr;
    }
    TreeNode root = new treeNode;
    root->val = preSequences[preL];
    root->leftChild = root->rightChild = nullptr;
    if (preL == preR) {
        return root;
    }

如果如果只有一个元素，说明就是一个节点，没有左右子树，直接返回。

    if (k - preL > 1) {
        root->leftChild = create(preL + 1, k - 1, postL, postL + k - preL - 2, preSequences, postSequences);
        root->rightChild = create(k, preR, postL + k - preL - 1, postR - 1, preSequences, postSequences);
    } else {
        flag = false;
        root->leftChild = create(k, preR, postL + k - preL - 1, postR - 1, preSequences, postSequences);
    }

如果发现包括根节点在内是大于1的，那么说明存在左右子树，那么肯定唯一，如果不是大于1，那说明只有一颗子树，放左放右都可以。最后遍历即可。

1083

给出一段数字,你应该可以用他们组成最小的数字，举个例子，我们组成许多数字如32-321-0229-87or0229-321-3214等等不同组成方式的数字段。

这个题目真的非常简单，之前在洛谷刷过差不多的。主要是几个字符串比较的情况，如123 1230，如果是这样，排序必须是1230123，因为最后的0是小于前面的第一个数1的，但如果是123 1235，那么就要倒过来了，1231235。其实就是贪心就好了。我也不知道为什么这个题目会归类到树这一块。

int cmp(string a, string b) {
    return a + b < b + a;
}

这句就是最关键的了，注意一些特殊情况，当全是0的时候要输出0即可。之前就是因为直接把打头的0去掉，导致如果result = 0那么什么都不输出。

1147

水题一道，题目直接给出是完全二叉树了，直接用数组表示即可。

bool isHeap(int *array, int n, bool maxHeap) {
    for (int i = 1; i <= n / 2; ++i) {
        int left = i * 2;
        int right = left + 1;
        if (left <= n) {
            if (maxHeap) {
                if (array[left] > array[i]) {
                    return false;
                }
            } else {
                if (array[left] < array[i]) {
                    return false;
                }
            }
        }

        if (right <= n) {
            if (maxHeap) {
                if (array[right] > array[i]) {
                    return false;
                }
            } else {
                if (array[right] < array[i]) {
                    return false;
                }
            }
        }
    }
    return true;
}

考查一下是否符合堆的要求即可。

1151

这个题目写出来本以为胜券在握，这个规律很好找，前序遍历是根左右，中序遍历是左根右，那么在中序遍历里面给出的两个关键字的根一定在两个关键字之间，比如中序遍历7 2 3 4 6 5 1 8，找26的最短祖先，祖先看定在3，4之间。对于前序遍历，祖先肯定在26的前面，以此类推就好了。

所以首要一步就是要找到当前两个关键字的位置，然后看他中间的数是不是在前序遍历的那两个关键字的前面即可。一开始是直接遍历找位置，结果超时了。

//        map<int, bool> map_match;
//
//        int first, second;
//
//        if (aIndex > bIndex) {
//            first = bIndex;
//            second = aIndex;
//        } else {
//            first = aIndex;
//            second = bIndex;
//        }
//
//        for (int j = first; j <= second; ++j) {
//            map_match[inOrder[j]] = true;
//        }
//
//        for (int l = 0; l <= aPreIndex && l <= bPreIndex; ++l) {
//            if (map_match[preOrder[l]]) {
//                if (preOrder[l] != a && preOrder[l] != b) {
//                    cout << "LCA of " << a << " and " << b << " is " << preOrder[l] << "." << endl;
//                    break;
//                } else if (preOrder[l] == a) {
//                    cout << a << " is an ancestor of " << b << "." << endl;
//                    break;
//
//                } else if (preOrder[l] == b) {
//                    cout << b << " is an ancestor of " << a << "." << endl;
//                    break;
//
//                }
//            }
//        }

超时的想法是先把中序遍历里面的在关键字之间的变量都存在一个map里面，然后遍历前序遍历直到遇到关键字，结果超时了。在输入的时候，就应该事先把遍历的位置用map存下来，然后就只需要遍历一次了：

//
// Created by GreenArrow on 2020/3/15.
//
#include <iostream>
#include <map>

using namespace std;

int main() {
    int m, n;
    cin >> m >> n;

    int preOrder[n];
    int inOrder[n];

    map<int, int> positionPre, positionIn;

    for (int i = 0; i < n; ++i) {
        cin >> inOrder[i];
        positionIn[inOrder[i]] = i;
    }

    for (int j = 0; j < n; ++j) {
        cin >> preOrder[j];
        positionPre[preOrder[j]] = j;
    }

    for (int k = 0; k < m; ++k) {

        int a, b;
        cin >> a >> b;

        int aIndex = -1;
        int bIndex = -1;
        int aPreIndex = -1;
        int bPreIndex = -1;

        if (positionIn.count(a)) {
            aIndex = positionIn[a];
        }
        if (positionIn.count(b)) {
            bIndex = positionIn[b];
        }

        if (aIndex == -1 && bIndex == -1) {
            cout << "ERROR: " << a << " and " << b << " are not found." << endl;
            continue;
        } else if (aIndex != -1 && bIndex == -1) {
            cout << "ERROR: " << b << " is not found." << endl;
            continue;
        } else if (aIndex == -1) {
            cout << "ERROR: " << a << " is not found." << endl;
            continue;
        }

        if (a == b) {
            cout << a << " is an ancestor of " << b << "." << endl;
            continue;
        }


        for (int i = 0; i < n; ++i) {
            int temp = preOrder[i];
            int inPosition = positionIn[temp];

            if (temp == a) {
                cout << a << " is an ancestor of " << b << "." << endl;
                break;
            } else if(temp == b){
                cout << b << " is an ancestor of " << a << "." << endl;
                break;
            }

            if(inPosition > aIndex && inPosition < bIndex){
                cout << "LCA of " << a << " and " << b << " is " << temp << "." << endl;
                break;
            } else if(inPosition > bIndex && inPosition < aIndex){
                cout << "LCA of " << a << " and " << b << " is " << temp << "." << endl;
                break;
            }
        }

1110

这个题目想了挺久的，有点意思，完全二叉树的数组是全满的，所以只需要看看数组是不是全部能访问就好了。首先建树找根节点：

    for (int i = 0; i < n; ++i) {
        string left, right;
        cin >> left >> right;
        if (left == "-") {
            array[i].left = -1;
        } else {
            array[i].left = string2number(left);
            father[array[i].left] = i;
        }
        if (right == "-") {
            array[i].right = -1;
        } else {
            array[i].right = string2number(right);
            father[array[i].right] = i;
        }
    }

    int root = -1;
    for (int j = 0; j < n; ++j) {
        if (father[j] == -1) {
            root = j;
        }
    }

father的用处就是看看是不是根节点而已。没有什么太大用处，接着就是遍历填数组了，用前中后序遍历填写都可以，这里还是用层次遍历好了：

int level(node *array, int root, int *array_tree) {
    queue<int> Queue;
    Queue.push(root);
    array[root].index = 0;
    array_tree[array[root].index] = 1;
    vector<int> sequences;
    while (!Queue.empty()) {
        int cur = Queue.front();
        sequences.push_back(cur);
        Queue.pop();
        if (array[cur].left != -1) {
            Queue.push(array[cur].left);
            array_tree[array[cur].index * 2 + 1] = 1;
            array[array[cur].left].index = array[cur].index * 2 + 1;
        }
        if (array[cur].right != -1) {
            Queue.push(array[cur].right);
            array_tree[array[cur].index * 2 + 2] = 1;
            array[array[cur].right].index = array[cur].index * 2 + 2;
        }
    }

    return sequences[sequences.size() - 1];
}

然后只要看看遍历过的数组有没有空的，有空的那就不是完全二叉树了。

1020

给定后序遍历和中序遍历求前序遍历，这个考408的时候就写过了，水题一道，直接上代码。

//
// Created by GreenArrow on 2020/2/21.
//

#include <iostream>
#include <queue>

using namespace std;

typedef struct node {
    int data;
    node *left;
    node *right;
} node;

node *create(int postl, int postr, int inl, int inr, int *post, int *in) {

    if (postl > postr) {
        return nullptr;
    }

    node *root = new node;

    root->data = post[postr];

    int index = 0;
    for (int i = inl; i <= inr; ++i) {
        if (in[i] == post[postr]) {
            index = i;
            break;
        }
    }

    int leftTreeNumber = index - inl;
    int rightTreeNumber = inr - index;

    root->left = create(postl, postl + leftTreeNumber - 1, inl, index - 1, post, in);
    root->right = create(postl + leftTreeNumber, postr - 1, index + 1, inr, post, in);

    return root;


}

void levelOrder(node *root) {
    queue<node *> Queue;
    Queue.push(root);
    int index = 0;
    int arr[10010];
    while (!Queue.empty()) {
        node *next = Queue.front();
        arr[index++] = next->data;
        Queue.pop();
        if (next != nullptr && next->left) {
            Queue.push(next->left);
        }
        if (next != nullptr && next->right) {
            Queue.push(next->right);
        }
    }

    for (int i = 0; i < index; ++i) {
        cout << arr[i];
        if (i != index - 1) {
            cout << " ";
        }
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    int postOrder[n], inOrder[n];
    for (int i = 0; i < n; ++i) {
        cin >> postOrder[i];
    }
    for (int j = 0; j < n; ++j) {
        cin >> inOrder[j];
    }

    node *root = create(0, n - 1, 0, n - 1, postOrder, inOrder);


    levelOrder(root);
}

1043

这个题也是水题，就是麻烦，也就镜像哪里有点麻烦，遍历的时候先遍历右边再遍历左边就好了，代码不贴了，占篇幅。

有关图的题目：1122，1142，1150，1026，1013，1021，1034，1003，1018，1030，1087，1111

1122

这个题目能不能做出来就看你能不能记得简单回路是啥玩意了。简单回路就是在回路序列里面，除了第一个与最后一个顶点相同，其他顶点各不相同；那么哈密顿回路就再加上访问所有节点的条件。访问到所有节点，只有第一个与最后一个节点相同，中间访问的节点只访问一次就叫哈密顿回路。

那么判断的几个条件：

1.总点数是否等于n+1

2.第一项是否等于最后一项

3.相邻节点之间是否能访问

4.是否访问了所有节点

bool Hamilton(int n, int *array, int vertex_n) {
    if (vertex_n + 1 != n) {
        return false;
    }

    bool visited[vertex_n + 1];
    fill(visited + 1, visited + vertex_n + 1, false);

    int pre = array[1];
    visited[pre] = true;
    for (int i = 2; i <= n; ++i) {
        if (chess[pre][array[i]] != 1 && chess[array[i]][pre] != 1 && array[i] != pre) {
            return false;
        }
        pre = array[i];
        visited[pre] = true;
    }

    for (int j = 1; j <= vertex_n; ++j) {
        if (!visited[j]) {
            return false;
        }
    }

    if (array[1] != array[n]) {
        return false;
    }

    return true;
}

1142

这个题目也是水题，遍历就好了，还不超时。首先遍历一遍看看序列之间的数字是否都有通路，其次遍历剩下不再序列里面的点看看能不能加入即可。

string isMaxClique(int vertex_n, int n, int *array) {


    if(n == 0){
        return "Not a Clique";
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (array[i] != array[j] && chess[array[i]][array[j]] == 0) {
                return "Not a Clique";
            }
        }
    }

    for (int k = 1; k <= vertex_n; ++k) {
        bool flag = true;
        if (!visited[k]) {
            for (int i = 1; i <= vertex_n; ++i) {
                if (i == k) {
                    continue;
                }
                if (!visited[i]) {
                    continue;
                }
                if (chess[k][i] != 1) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return "Not Maximal";
            }
        }
    }

    return "Yes";

}

水题一道。

1150

存在一个旅行推销员的问题，给定一个城市列表和这些城市之间的距离，问，哪条最短的路能够访问所有的城市并且最后能回到出发的城市？这是哪个NPhard的问题，也就是指示复杂度类型的问题，在运筹学研究和计算机科学理论研究上有很重要的意义。

在这个问题里，你应该要从这些城市列表里面找到一个循环，这个循环是旅行者问题的解。

输入详情：每一个输入包含一个测试样例。对于每一个案例，第一行给出两个正整数，分别是城市的数量以及边数。接下来是M行，每一个描述一条边，边的格式如下：城市1，城市2，距离。城市编号从1到N且距离为正数不超过100。接下来一行给出正整数K，路径的数量，紧接着K行描述路径，路径格式为n,C1,C2......。

输出详情：对于每一条路，打印出路径PathX:TotalDist，x是标号，totalDist是路径的总距离。差不多就这样。

这个题目读起来，很繁杂，一开始看的时候还以为他要我算出所有的简单回路。其实也就是遍历操作即可。和前面一道图的题目类似，注意一些细节操作即可，水题一道。

int getClassification(int vertex_n, int n, int *array, int &classification) {
    int pre = array[0];
    int sum = 0;
    int result = 0;
    for (int i = 1; i < n; ++i) {
        if (chess[pre][array[i]] != INT_MAX) {
            sum += chess[pre][array[i]];
            pre = array[i];
        } else {
            result = INT_MAX;
            classification = 2;
            return result;
        }
    }


    if (array[0] != array[n - 1]) {
        classification = 2;
        result = sum;
        return result;
    }

    bool flag2 = false;
    for (int j = 1; j <= vertex_n; ++j) {
        if (visited[j] == 0) {
            classification = 2;
            result = sum;
            return result;
        }

        if (visited[j] >= 2) {
            if (j == array[0] && visited[j] > 2) {
                flag2 = true;
            }

            if (j != array[0] && visited[j] > 1) {
                flag2 = true;
            }
        }

    }

    if (flag2) {
        classification = 3;
        result = sum;
        return result;
    }

    classification = 1;

    result = sum;
    return result;


}

1126

在图论中，一条路径如果能访问每条边一次就叫做欧几里得路径。相同的，一条欧几里得环一条起点和终点相同的欧几里得路径。在1736年，欧拉等人第一次在解决著名的七....问题是提出。如果一个图是联通图并且所有的顶点的度为偶数，那么它会存在一条欧几里得环，这样的图我们称为Eulerian。（欧几里得人？？？）如果此图恰好有两个奇数度的顶点，则所有的欧几里得路径都是从其中一个顶点出发到另一个顶点结束，只有欧几里得路径而没有欧几里得环的图称为semi-Eulerian

输入详情：每一个输入文件包含一个测试样例，每一个案例开头第一行包含两个数字，N和M，分别是顶点总数和边的总数。接下来的M行描述一条边的两端。

输出描述：第一行打印出顶点的度，按照顶点序号递增的次序，第二行输出图的类型。大概就是这样吧。

这个题目很容易瞎了眼，条件有几个，其一连通图，其二度的数量。首先可以用BFS或者DFS判断是否是联通图，然后再判断度的数量即可。先随机找一个点开始BFS，如果一次BFS完成之后所有的点都被访问了，那么这个图就是联通图，看到很多答案都是每一个点都BFS，其实没有必要，仅仅一个点进行BFS即可。

void BFS(int v) {
    visited[v] = true;
    for (int i = 0; i < nodes[v].size(); ++i) {
        if (!visited[nodes[v][i]]) {
            BFS(nodes[v][i]);
        }
    }
}

后面的判断degress奇偶没有很简单，也是水题。

1013

这也是一个连通图问题，给出n个城市，m条路，问你如果这个城市消失了，需要添加多少条道路才能联通。也是个水题，你把当前要消失的城市包括其有关路径都去掉，然后看看有多少个联通分量，有多少个联通分量就证明有多少个地区是分开的，然后减一就是公路的数量。一开始的做法是复制一份新的地图，把敌对城市去掉，超时了，然而我这么做是多余的，完全可以在深度遍历的时候忽略敌对城市即可。

    for (int k = 0; k < K; ++k) {
        fill(visited, visited + N + 1, false);
        int city;
        scanf("%d", &city);

        visited[city] = true;
        int index = 0;
        for (int l = 1; l <= N; ++l) {
            if (!visited[l]) {
                BFS(l, city);
                index++;
            }
        }

直接把敌对城市设置成已经访问即可，这样BFS不会去寻找已经访问的节点。

1021

如果一个图是联通的而且又没有环，那么就可以看成是一颗树。树的高度就依赖于选择的根是哪一个点。现在要求你找出高度最高的树的根，这样的根称为最深根。

输入详情：每一个输入包含一个测试样例，对于每一个样例，第一行一个正整数，表示顶点的数量，因此，顶点编号从1到N，接下来N-1行描述边。

输出详情：对于每一个测试样例，打印出深的根，如果根不是唯一，打印出所有的根，并按照升序排列。如果不是树，打印出联通分量的个数。

考查深度优先和联通分量，也是水题，BFS遍历查找最深的根，同时BFS把联通分量给找出来，因为查找最深的根和查找联通分量是可以合在一起，关键就是怎么合起来了。修改一下BFS，让其返回最深的层次：

void BFS(int v, int depth) {
    visited[v] = true;


    bool flag = true;
    for (int i = 0; i < graph[v].size(); ++i) {
        int u = graph[v][i];
        if (!visited[u]) {
            flag = false;
            BFS(u, depth + 1);
        }
    }

    if (flag) {
        if (max_BFS < depth) {
            max_BFS = depth;
        }
    }
}

每一次就看看当前节点的下一个节点是不是全部都访问过了，如果都访问过了那就说明到底了，对比之前的然后返回。完成后注意清空visited：

    for (int j = 1; j <= N; ++j) {
        fill(visited, visited + N + 1, false);
        max_BFS = INT_MIN;
        BFS(j, 0);

每一次完成需要清空，需要遍历所有的点找到最深的根。顺便在第一次BFS遍历的时候看看是否有访问到了所有的节点，如果没有，那就没有必要再找最深的点了，直接找联通分量了：

    int max = INT_MIN;
    int index_ = 0;
    bool flag = false;
    for (int j = 1; j <= N; ++j) {
        fill(visited, visited + N + 1, false);
        max_BFS = INT_MIN;
        BFS(j, 0);
        //cout << max_BFS << endl;
        index_++;
        if (!flag)
            for (int i = 1; i <= N; ++i) {
                if (!visited[i]) {
                    flag = true;
                    //不联通
                    for (int k = j + 1; k <= N; ++k) {
                        if (!visited[k]) {
                            BFS(k, 0);
                            index_++;
                        }

                        bool connected = true;

                        for (int l = 1; l <= N; ++l) {
                            if (!visited[l]) {
                                connected = false;
                                break;
                            }
                        }

                        if (connected) {
                            cout << "Error: " << index_ << " components" << endl;
                            return 0;
                        }

                    }

                }
            }

1034

警察找到犯罪团伙透明的方法是检查他们的手机，如果在A和B之间存在了电话联系，那么久说A和B是有关系的。关系的权重是定义了双方通话的总时长。一个帮派是指帮派成员超过两个人，并且这些人之间互相都有联系，且通话量超过既定阈值K。在每一个帮派，存在一个通话量权重最高的人，以此人为首。现在给定一些通话列表，你应该团伙以及头目。

一开始没看清题目，以为名字是三个字母相同的，从A-Z，就26个，然后写出来只对了两个点。然后做出来发现不是。我这里使用的是用向量存储图，单独存储边，如果要计算一个图的权重，遍历图中节点相加即可。这里的关系的双向关系，也就是无向图，但是通话量是单向的，在计算联通分量的时候需要按照无向图计算，计算权重的时候要按照有向图的边相加。如果按照上述做法，就麻烦了，我就是这么做的，其实A->B和B->A的权重是可以相加当成一条边计算，然后权重相加的时候只需要加一次就好了，代码优化的地方可以很多，首先就是使用的存储图的结构就可以使用矩阵，然后权重计算不用分开算，相加在一起当成是无向图。

    for (int i = 0; i < n; ++i) {
        string A, B;
        int weight;
        cin >> A >> B >> weight;
        int ANumber = string2number(A), BNumber = string2number(B);

        name[ANumber] = A;
        name[BNumber] = B;

        visited[ANumber] = false;
        visited[BNumber] = false;

        graphs[ANumber].push_back(BNumber);
        graphs[BNumber].push_back(ANumber);

        if (edges.count(ANumber) == 0) {
            vector<edge> e;
            e.emplace_back(BNumber, weight);
            edges[ANumber] = e;
        } else {
            edges[ANumber].push_back(edge(BNumber, weight));
        }

        totalPhone[ANumber] += weight;
        totalPhone[BNumber] += weight;
    }

这块在输入的时候把输入的name给量化了，把所有通过节点的通话量加起来，后面要选择一个团伙的头目需要使用到。边也存储下来，数组下标就是起始点，边存储终点和权值。

void BFS(int v, int &size, int &total, vector<int> &gangs) {
    visited[v] = true;
    for (int i = 0; i < graphs[v].size(); ++i) {
        if (!visited[graphs[v][i]]) {
            
            gangs.push_back(graphs[v][i]);

            total = addEdges(graphs[v][i], total);

            size++;

            BFS(graphs[v][i], size, total, gangs);
        }
    }
}

然后就是调用BFS了，最后还需要进行排序输出。

1003

找最短路径，算出最短路径有多少条，每一个城市会有相应的人员，经过这个城市就可以带走这些人员，在这些最短路径里面最多能带走多少人。

很明显是属于最短路径的问题，最短路径很容易，关键是如何存储下最短路径的条数。可以使用一个Num数组存储，一开始num[source] = 1，代表当前只有这一条路径，当出现了多条路径之后，也就是在更新到达路径的时候d[v]如果和之前的是相同的，num[v] += num[source]，这样其实模拟了一个乘法增长的过程，因为后面的每一条路增加，其实都是倍数增长。

void Dijikstra(int v, int n) {

    fill(d, d + MAX, INT_MAX);
    fill(visited, visited + MAX, false);
    fill(w, w + MAX, 0);
    fill(num, num + MAX, 0);
    w[v] = people[v];
    num[v] = 1;
    d[v] = 0;

    for (int i = 0; i < n; ++i) {
        int min = INT_MAX;
        int u = -1;
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && min > d[j]) {
                min = d[j];
                u = j;
            }
        }

        if (u == -1)
            return;

        visited[u] = true;

        for (int k = 0; k < n; ++k) {
            if (!visited[k] && chess[u][k] != INT_MAX) {

                if (d[k] > d[u] + chess[u][k]) {
                    d[k] = d[u] + chess[u][k];
                    w[k] = w[u] + people[k];
                    num[k] = num[u];
                } else if (d[k] == d[u] + chess[u][k]) {
                    num[k] += num[u];
                    if (w[u] + people[k] > w[k]) {
                        w[k] = w[u] + people[k];
                    }
                }

            }
        }

    }

}

就是调用算法即可，如果还需要求路径，只需要用一个vector即可。

1018

大概就是说有几个车站，当容量为一半的时候是最佳状态，现在需要去某一个车站，问你那一条路径是路径最短，填补车辆最少，回收车辆最少。看上去好像是最短路径，但是事实上这是一个深度搜索的问题，最短路径没有办法保证送回和送出的数据是全局最优的。

void DFS(int s, int end, int tempSend, int tempBack, int tempDis) {
    visited[s] = true;
    tempPath.push_back(s);

    if (s == end) {
        if (minDis > tempDis) {
            path = tempPath;
            minDis = tempDis;
            minSend = tempSend;
            minBack = tempBack;
        } else if (minDis == tempDis) {
            if (minSend > tempSend) {
                path = tempPath;
                minSend = tempSend;
                minBack = tempBack;
            } else if (minSend == tempSend) {
                if (minBack > tempBack) {
                    path = tempPath;
                    minSend = tempSend;
                    minBack = tempBack;
                }
            }
        }
        return;
    }

    for (int i = 1; i <= n; ++i) {
        if (!visited[i] && chess[s][i] != INT_MAX) {

            int temp = bikes[i] - capacity / 2;
            int tempB = tempBack;
            int tempS = tempSend;
            if (temp >= 0) {
                tempB += temp;
            } else {
                if (temp + tempB < 0) {
                    tempS -= (temp + tempB);
                    tempB = 0;
                } else {
                    tempB = (temp + tempB);
                }
            }
            DFS(i, end, tempS, tempB, tempDis + chess[s][i]);
            tempPath.pop_back();
            visited[i] = false;
        }
    }
}

有点复杂，用Dijiskra也只能有25分，主要容易搞混的其实就是回收和放出那里：

            int temp = bikes[i] - capacity / 2;
            int tempB = tempBack;
            int tempS = tempSend;
            if (temp >= 0) {
                tempB += temp;
            } else {
                if (temp + tempB < 0) {
                    tempS -= (temp + tempB);
                    tempB = 0;
                } else {
                    tempB = (temp + tempB);
                }
            }

先算出当前点需要多少，如果不需要了还多出盈余，那就加上前面需要送回的；如果缺了，就看看以往需要送回的能不能填补，如果能填补，那么减去已经填补的，如果不能填补，那么就要继续送剩下的。

1030

给出一张旅行者地图，地图给出城市之间的距离已经花费，现在要求你写出程序帮助旅行者决定最短的路径，如果路径最短并非唯一，则给出最小花费，次最小花费的最短路径保证唯一。

输入详情：每一个输入包含了一个测试样例，每一个样例由4个正整数开始，分别是城市数量，告诉公路的数量，起始点和目的地。接下来M行分别就是边的属性。

输出详情：对于每一个测试样例，输出最短路径，路径距离，路径花费。

这个题目相比上面一题要简单不少，就是一个条件而已:

···

void Dijiskra(int s, int n) {

fill(visited, visited + MAX, false);

fill(d, d + MAX, edge(INT_MAX, INT_MAX));

d[s].distance = 0;

d[s].cost = 0;

for (int i = 0; i < n; ++i) {

int u = -1;

int min = INT_MAX;

for (int j = 0; j < n; ++j) {

if (!visited[j] && d[j].distance < min) {

min = d[j].distance;

u = j;

}

if (u == -1) {

return;

}

    visited[u] = true;
    for (int k = 0; k < n; ++k) {
        if (!visited[k] && map[u][k].distance != INT_MAX) {
            if (d[k].distance > d[u].distance + map[u][k].distance) {
                d[k].distance = d[u].distance + map[u][k].distance;
                d[k].cost = d[u].cost + map[u][k].cost;
                path[k] = u;
            } else if (d[k].distance == d[u].distance + map[u][k].distance) {
                if (d[k].cost > d[u].cost + map[u][k].cost) {
                    d[k].distance = d[u].distance + map[u][k].distance;
                    d[k].cost = d[u].cost + map[u][k].cost;
                    path[k] = u;
                }
            }
        }
    }
}

}

···

1087

说是有几个城市，城市之间存在路径，通过路径需要花费，而每经过一个城市就可以获得这个城市的快乐值，问路径最短并且能得到最大快乐值的是那一条路。

这个题目比上上题和上上上题都要简单，和上一题难度差不多，其实就是最短路径加上一点条件而已。

void Dijiskra(int s, int n) {
    fill(visited, visited + MAX, false);
    fill(d, d + MAX, INT_MAX);
    fill(happy_total, happy_total + MAX, 0);
    fill(num, num + MAX, 0);
    num[s] = 1;
    d[s] = 0;

    for (int i = 0; i < n; ++i) {
        int u = -1;
        int min = INT_MAX;
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && d[j] < min) {
                min = d[j];
                u = j;
            }
        }

        visited[u] = true;
        if (u == -1)
            return;

        for (int k = 0; k < n; ++k) {
            if (!visited[k] && chess[u][k] != INT_MAX) {
                if (d[k] > d[u] + chess[u][k]) {
                    d[k] = d[u] + chess[u][k];
                    happy_total[k] = happy_total[u] + name[k].happy;
                    num[k] = num[u];
                    path[k] = u;
                } else if (d[k] == d[u] + chess[u][k]) {
                    num[k] += num[u];
                    if (happy_total[k] < happy_total[u] + name[k].happy) {
                        happy_total[k] = happy_total[u] + name[k].happy;
                        path[k] = u;
                    }
                }
            }
        }
    }
}

1111

这个题目和上一题很类似，两个最短路径就好了，当然了也可以合成一个。首先一个是求路程花费最短的，其次是求时间最短，如果路径最短有多条，那就把时间最短的选出来；如果时间最短的有多条，把经过城市最短的选出来。城市最短可以用一个数组记录，每更新一次，就继承前一点的值加1。

void Dijiskra_t(int s, int n) {
    fill(t, t + MAX, INT_MAX);
    fill(visited_t, visited_t + MAX, false);
    fill(size_time, size_time + MAX, 0);
    size_time[s] = 1;
    t[s] = 0;
    for (int i = 0; i < n; ++i) {
        int u = -1;
        int min = INT_MAX;
        for (int j = 0; j < n; ++j) {
            if (!visited_t[j] && t[j] < min) {
                u = j;
                min = t[j];
            }
        }

        visited_t[u] = true;

        for (int k = 0; k < n; ++k) {
            if (!visited_t[k] && chess[u][k].time != INT_MAX) {
                if (t[k] > t[u] + chess[u][k].time) {
                    t[k] = t[u] + chess[u][k].time;
                    size_time[k] = size_time[u] + 1;
                    path_t[k] = u;
                } else if (t[k] == t[u] + chess[u][k].time) {
                    if (size_time[k] > size_time[u] + 1) {
                        size_time[k] = size_time[u] + 1;
                        path_t[k] = u;
                    }
                }
            }
        }
    }
}

DFS，BFS：1004，1021，1018（这两题图论已写）

1004

规定了根节点是1号，让你找出每一层的叶子节点。这个题目也是个水题，但是有些小坑，稍不注意就拿不了30。可以用BFS也可以用DFS，我是用BFS做的，因为直接在树的结构里面加上层次属性就可以了。测试点2有一个小坑，当输入1 0的时候要输出1，因为在BFS里面我的最大层次是初始-1，如果输入1 0那么就不会进入到while循环里面，结果什么都不输出了，所以把最大层次初始化为0就好；还有当n=0的时候不做处理，什么都不输出，需要直接return 0；

int levelOrder(treeNode *root) {
    int max = 0;
    queue<treeNode *> Queue;
    Queue.push(root);
    root->depth = 0;
    while (!Queue.empty()) {
        treeNode *cur = Queue.front();
        Queue.pop();
        if (!cur->children.size())
            depth[cur->depth]++;
        for (int i = 0; i < cur->children.size(); ++i) {
            cur->children[i]->depth = cur->depth + 1;
            Queue.push(cur->children[i]);
            if (cur->children[i]->depth > max) {
                max = cur->children[i]->depth;
            }
        }
    }
    return max;
}

1076

这个题目，一开始看错题目了，把粉丝和up主的关系看反了，第一行3 2 3 4应该是2 3 4号用户关注了1才对。这个题目其实也很简单，就是广度优先就好了：

int BFS(int s, int L, vector<int> graph[MAX]) {
    fill(visited, visited + MAX, false);
    fill(layer, layer + MAX, 0);
    int number = 0;
    layer[s] = 0;
    visited[s] = true;
    queue<int> Queue;
    Queue.push(s);
    while (!Queue.empty()) {
        int cur = Queue.front();
        Queue.pop();
        if (layer[cur] <= L && cur != s) {
            number++;
        }
        for (int i = 0; i < graph[cur].size(); ++i) {
            int v = graph[cur][i];
            if (!visited[graph[cur][i]]) {
                Queue.push(graph[cur][i]);
                layer[graph[cur][i]] = layer[cur] + 1;
                visited[graph[cur][i]] = true;
            }
        }
    }

    return number;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

二叉树

编程算法