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;
} 
同程旅行工作强度 17人发布
查看12道真题和解析