4-7笔试记录

第一题：
幼儿园老师安排小朋友做游戏，现在需要给N为小朋友进行分组，老师想让每个同学写一个名字，代表这位小朋友想和谁分到一组，请问老师在满足所有小朋友意愿的情况下，最多可以将班级分成多少组？
输入描述：
第一行输入N， 0 < N <= 100000
接下来是N行代表每个小朋友希望和谁分到一组，如“John Jack ”，代表John希望和Jack分到一组，两个名字之间以空格分割，名字本身不存在空格
输出描述：
分组的最多数量
例1：
6
Jack Tom
Alice John
Jessica Leonie
Tom Alice
John Jack
Leonie Jessica
2

例2：
6
Jack Tom
Alice John
Jessica Tom
Tom Alice
John Jack
Leonie Jessica
1

例3：
3
Xiaoming Xiaohong
Xiaohong Xiaoqiang
Xiaoqiang Xiaoming
1

并查集（LeetCode 547省份的数量)

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

class DisjointSet{
public:
    DisjointSet(int n) :parent(vector<int>(n)), rank(vector<int>(n)), count(n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void merge(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx == rooty) {
            return;
        }
        if (rootx != rooty) {
            if (rank[rootx] < rank[rooty]) {
                swap(rootx, rooty);
            }
            parent[rooty] = rootx;
            if (rank[rootx] == rank[rooty]) rank[rootx] += 1;
        }
        count--;
    }

    int getCount() {
        return count;
    }

private:
    vector<int> parent;
    vector<int> rank;
    int count;
};

int main() {
    int n;
    cin >> n;
    DisjointSet disjoint_set(n);

    vector<string> s1;
    vector<string> s2;
    string name;
    int result = 0;
    while (n--) {
        cin >> name;
        s1.push_back(name);
        cin >> name;
        s2.push_back(name);
    }

    unordered_map<string, int> umap;
    for (int i = 0; i < s1.size(); i++) {
        umap[s1[i]] = i;
    }

    for (int i = 0; i < s1.size(); i++) {
        disjoint_set.merge(umap[s1[i]], umap[s2[i]]);
    }
    cout << disjoint_set.getCount() << endl;
    system("pause");
    return 0;
}

第二题：
给定N个任务（1 <= N <=100）,任务编号从0开始顺序累加，这N个任务在系统中排队顺序执行，每个任务的自身执行时间为非负数，依次为t1,t2,...tn。部分任务之间存在依赖关系，某任务所依赖的任务如果没有执行，则该任务需要重回对尾重新排队。只有任务执行以及任务排队等待消耗时间，其余操作消耗时间忽略不计。请计算每个任务的实际执行时间（实际执行时间 = 任务自身执行的时间 + 在队列中等待其他任务执行的时间）

输入描述：
第一行输入按照任务编号递增的顺序表示N个任务的自身执行时间，为逗号分隔的字符串，执行时间取值范围[1,999]。例如：1,3,4(逗号前后没有空格)。第二行为循环依赖关系如0 —>2，表示0号任务的执行依赖2好任务的执行。
输出描述：
按照任务编号递增的顺序，输出每个任务的实际执行时间。以逗号为分隔，逗号前后不要有空格，例如：8, 3, 7
实例1：
输入：
1,3,4
0—>2
输出：
8, 3, 7

说明：
输入参数中的依赖关系通过任务序号表示，例如0—>2, 表示0号任务的执行依赖2好任务的执行，输出为每个任务的实际消耗时间，顺序和输入的任务顺序一致。

实例2：
输入：
1,3,4,5,8,5,3,6
0—>2,2—>4,2—>6
输出：
35,3,34,8,16,21,24,30

拓扑排序（LeetCode207课程表）

#include <iostream>
#include <queue>
#include <string>
#include <sstream>
using namespace std;

int main() {
    string s;
    string t;
    cin >> s;
    stringstream ss(s);
    // 将任务编号与时间构造为pair插入到队列当中
    queue<pair<int,int>> que;
    int i = 0;
    while (getline(ss, t, ',')){
        que.push(pair<int,int>(i++, stoi(t)));
    }
    // 计算边的依赖关系和每个任务的入度
    vector<vector<int>> edges(que.size());
    vector<int> indeg(que.size(),0);
    cin >> s;
    stringstream input(s);
    while (getline(input, t, ',')) {
        edges[t[3] - '0'].push_back(t[0] - '0');
        indeg[t[0] - '0']++;
    }
    // 模拟任务队列执行
    vector<int> result(que.size(), 0);
    int time = 0;
    while (!que.empty()) {
        pair<int, int> u = que.front();
        que.pop();
        if (indeg[u.first] == 0) {
            time += u.second;
            result[u.first] = time;
            // 如果任务成功执行，将依赖于该任务的节点入度减一
            for (auto v : edges[u.first]) {
                --indeg[v];
            }
        }
        else {
            que.push(u);
        }
    }
    // 输出结果
    for (int i = 0; i < result.size() - 1; i++) {
        cout << result[i] << ',';
    }
    cout << result[result.size() - 1] << endl;

    system("pause");
    return 0;
}

第三题：
到香港旅游，最后一站决定去迪士尼乐园打卡，因为返程机票已经订好，所以我们必须在剩余可游玩时间t分钟内完成游玩，才能不耽误行程，请你为我们设计一条最佳游玩路线，选择规则如下：
1、游玩总时长不能超过t,但最接近t
2、游玩时不想走回头路，仅向右或向下两个方向，畅玩到出口
乐园被划分为一个row*col的风格区域地图，在每个方格区域上，标注了游玩的最佳时长，从入园口[0,0]出发，选定最佳游玩路线，一路畅玩到出口[row-1,col-1]

输入描述：
首行输入以单个空格分割的三个正整数row和col以及t，row代表地图行数（0 < row <=13）,col代表地图列数（0 < col <= 13）,t代表剩余可游玩时间（0 < t <= 600）:
接下来row行，每一行包括col个以单个空格分割的数字，代表该方格区域最佳游玩时长time分钟（0 < time < 100）
输出描述：
最佳游玩线路游玩总时长，若不存在，请输出-1

例1
5 5 30
3 5 4 2 3
4 5 3 4 3
4 3 5 3 2
2 5 3 3 5
5 3 4 4 1
输出
30
一种可能的游玩路线是[0,0]—>[1,0]—>[2,0]—>[3,0]—>[4,0]—>[4,1]—>[4,2]—>[4,3]—>[4,4]，刚好30分钟玩完整个项目，剩余时间可玩时间t没有任何偏差，因此输出30

例2
5 5 10
3 5 4 2 3
4 5 3 4 3
4 3 5 3 2
2 5 3 3 5
5 3 4 4 1
输出-1
说明：
无论走哪条路线，其游玩时间都会超过剩余可玩时间t，因此输出-1

三维DP

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, t;
    cin >> n >> m >> t;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    int temp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> temp;
            grid[i][j] = temp;
        }
    }
    // 先用一个2维DP求出到达每个点有多少种路径  LeetCode 62题 不同路径
    vector<vector<int>> dp(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        dp[i][0] = 1;
    }
    for (int j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    // 初始化一个3维DP数组，dp[i][j][k]的含义经过不同路径达该点处的时间
    int q = dp[n - 1][m - 1];
    vector<vector<vector<int>>> dpq(n, vector<vector<int>>(m, vector<int>(q, 0)));
    dpq[0][0][0] = grid[0][0];
    for (int i = 1; i < n; i++) {
        dpq[i][0][0] = dpq[i - 1][0][0] + grid[i][0];
    }
    for (int j = 1; j < n; j++) {
        dpq[0][j][0] = dpq[0][j - 1][0] + grid[0][j];
    }

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            int p = 0;
            for (int k = 0; k < dp[i- 1][j]; k++) {
                dpq[i][j][k] = dpq[i - 1][j][k] + grid[i][j];
                p++;
            }
            for (int k = 0; k < dp[i][j - 1]; k++) {
                dpq[i][j][k + p] = dpq[i][j - 1][k] + grid[i][j];
            }
        }
    }
    // 将dpq[n - 1][m - 1]中大于t的值全部置0
    int result = 0;
    for (int i = 0; i < q; i++) {
        if (dpq[n - 1][m - 1][i] > t) {
            dpq[n - 1][m - 1][i] = 0;
        }
    }
    // 求剩余值中的最大值
    for (int i = 0; i < q; i++) {
        if (dpq[n - 1][m - 1][i] > result) {
            result = dpq[n - 1][m - 1][i];
        }
    }

    // 如果求得最大值则返回，如果没有则返回-1
    if (result != 0) {
        cout << result << endl;
    }
    else {
        cout << -1 << endl;
    }

    system("pause");

    return 0;
}