这里是paoxiaomo，一个现役ACMer，之后将会持续更新算法笔记系列以及笔试题题解系列
本文章面向想打ICPC/蓝桥杯/天梯赛等程序设计竞赛，以及各个大厂笔试的选手
感谢大家的订阅➕ 和 喜欢💗
有什么想看的算法专题可以私信博主

（本文题面由清隆学长收集）

01.二叉搜索树的构建与查找

问题描述

LYA 是一名计算机专业的学生,最近她正在学习数据结构中的二叉搜索树。二叉搜索树是一种常用的数据结构,它可以实现快速的查找和插入操作。

现在,LYA 有一个由 $2^n-1$ 个不同的正整数组成的数列（$1\le n\le 10$,且 $n$ 为整数）。她想用这些数构建一棵平衡的满二叉搜索树。

二叉搜索树满足以下性质：

1. 节点的左子树只包含小于当前节点的数。
2. 节点的右子树只包含大于当前节点的数。
3. 所有左子树和右子树也必须是二叉搜索树。

例如,对于数列 $[1,2,3,4,5,6,7]$,可以构建出如下图所示的满二叉搜索树：

    4/ \2   6/ \ / \
1  3 5  7

现在,给定一个待查找的数,请你帮助 LYA 计算查找该数的路径和结果。

输入格式

第一行包含若干个用空格分隔的正整数,表示给定的数列。

第二行包含一个正整数,表示待查找的数。

输出格式

输出查找的路径和结果。

路径从根节点开始,用 S 表示。查找左子树用 L 表示,查找右子树用 R 表示。查找到结果用 Y 表示,未找到结果用 N 表示。

样例输入 1

2 1 3 7 5 6 4
6

样例输出 1

SRY

样例解释 1

从根节点开始,所以路径的第一部分为 S。待查找数为 $6$,大于根节点 $4$,所以要查找右子树,路径增加 R,正好找到,因此最后增加 Y。最终输出 SRY。

样例输入 2

4 2 1 3 6 5 7
5

样例输出 2

SRLY

样例解释 2

从根节点开始,先查找右子树,再查找左子树,最终找到结果 $5$,因此输出 SRLY。

样例输入 3

1 2 3 4 5 6 7
8

样例输出 3

SRRN

样例解释 3

从根节点开始查找,标记 S。待查找数 $8$ 大于根节点 $4$,所以查找右子树,标记 R。继续查找右子树,标记 R。$8$ 比右子树节点 $7$ 还大,但已经到达叶子节点,没有找到,因此最后标记 N。

数据范围

• $1\le n\le 10$
• 给定的数列中的数互不相同

【题目解析】

这个问题可以通过递归地在二叉搜索树中搜索给定的数来解决。首先，我们需要构建一个平衡的满二叉搜索树，然后再搜索给定的数。

构建平衡的满二叉搜索树可以采用递归的方式，每次选取数列的中间元素作为当前节点，然后递归地构建左右子树。

接下来，我们搜索给定的数，按照二叉搜索树的性质，从根节点开始，如果给定的数比当前节点的值小，就向左子树搜索，如果给定的数比当前节点的值大，就向右子树搜索，直到找到该数或者搜索到空节点为止。

cpp

#include <bits/stdc++.h>using namespace std;// 定义二叉树节点
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 构建平衡的满二叉搜索树
TreeNode* buildBST(vector<int>& nums, int start, int end) {if (start > end) return nullptr;int mid = start + (end - start) / 2;TreeNode* root = new TreeNode(nums[mid]);root->left = buildBST(nums, start, mid - 1);root->right = buildBST(nums, mid + 1, end);return root;
}// 搜索给定的数
string search(TreeNode* root, int target) {if (root == nullptr) return "N";if (root->val == target) return "Y";else if (target < root->val) return "L" + search(root->left, target);else return "R" + search(root->right, target);
}int main() {// 读取输入数据vector<int> nums;int num;while (cin >> num) {nums.push_back(num);if (cin.get() == '\n') break; // 读到换行符结束输入}sort(nums.begin(),nums.end());int target;cin >> target;// 构建平衡的满二叉搜索树TreeNode* root = buildBST(nums, 0, nums.size() - 1);// 搜索给定的数string result = search(root, target);cout<<'S'<<endl;// 输出结果cout << result << endl;return 0;
}

02.球员能力评估

题目描述

K教练正在对足球队的 $n$ 名球员进行射门能力评估。评估共进行 $m$ 次训练,每次训练时,若球员射门得分则记为1,否则记为0。现在K教练需要根据以下规则对球员进行排名:

1. 进球总数较多的球员排名靠前。
2. 如果进球总数相同,则最长连续进球次数较多的球员排名靠前。
3. 如果最长连续进球次数也相同,则第一次未进球的训练序号较大的球员排名靠前。如果第一次未进球的训练序号也相同,则比较第二次、第三次……直到比较出结果。
4. 如果按照前三条规则仍然无法区分排名,则编号较小的球员排名靠前。

请你帮助K教练生成一个球员排名。

输入格式

第一行包含两个正整数 $n$ 和 $m$,表示参与评估的球员数量和训练次数,球员编号从1到 $n$。

第二行包含 $n$ 个空格分隔的长度为 $m$ 的字符串,第 $i$ 个字符串表示编号为 $i$ 的球员在这 $m$ 次训练中的进球记录。

输出格式

输出一行,包含 $n$ 个空格分隔的正整数,表示球员编号按照射门能力从高到低排列的结果。

数据范围

• $1\le n\le 1000$
• $1\le m\le 1000$

样例输入

4 5
11100 00111 10111 01111

样例输出

4 3 1 2

样例解释

• 球员3和球员4的进球总数均为4个,多于球员1和球员2的3个。
• 球员4的最长连续进球次数为4,大于球员3的3,因此球员4排名第一,球员3第二。
• 球员1第2次训练时未进球,早于球员2的第1次,因此球员1第三,球员2第四。

【题目解析】

这个问题可以通过自定义比较函数来排序解决。首先，我们需要定义一个结构体来存储球员的信息，包括进球总数、最长连续进球次数以及第一次未进球的训练序号。然后，我们对这些球员进行排序，按照题目中的规则进行比较。

cpp

#include <bits/stdc++.h>using namespace std;// 定义球员结构体
struct Player {int id;int totalGoals;int maxConsecutiveGoals;int firstMissedTraining;// 定义比较函数bool operator<(const Player& other) const {if (totalGoals != other.totalGoals) {return totalGoals > other.totalGoals;} else if (maxConsecutiveGoals != other.maxConsecutiveGoals) {return maxConsecutiveGoals > other.maxConsecutiveGoals;} else if (firstMissedTraining != other.firstMissedTraining) {return firstMissedTraining < other.firstMissedTraining;} else {return id < other.id;}}
};int main() {int n, m;cin >> n >> m;vector<Player> players(n);for (int i = 0; i < n; ++i) {players[i].id = i + 1;players[i].totalGoals = 0;players[i].maxConsecutiveGoals = 0;players[i].firstMissedTraining = m + 1;}for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {char goal;cin >> goal;if (goal == '1') {players[i].totalGoals++;players[i].maxConsecutiveGoals++;} else {players[i].maxConsecutiveGoals = 0;players[i].firstMissedTraining = min(players[i].firstMissedTraining, j + 1);}}}// 排序sort(players.begin(), players.end());// 输出结果for (int i = 0; i < n; ++i) {cout << players[i].id << " ";}cout << endl;return 0;
}

03.微服务调用分析

题目描述

K小姐是一名软件工程师,她正在对公司的 $n$ 个微服务进行调用情况分析。这些微服务使用 $0$ 到 $n-1$ 的整数进行编号。

K小姐得到了一个长度为 $n$ 的数组 $edges$,其中 $edges[i]$ 表示存在一个从微服务 $i$ 到微服务 $edges[i]$ 的调用关系。

如果多个微服务形成了一个环,我们称之为一个微服务群组。对于一个微服务群组,我们定义:

• $L$ 表示该群组内所有微服务的数量。
• $V$ 表示能够调用到该群组内微服务的微服务数量。
• 该群组的内聚值 $H=L-V$。

已知给定的调用关系数据中至少存在一个微服务群组,请你计算所有群组的内聚值,并按照以下规则对它们进行排序:

1. 按照内聚值 $H$ 从大到小排序。
2. 如果内聚值相同,则按照群组内最大编号从小到大排序。

最后,请输出排序后的第一个微服务群组,要求从群组内编号最小的微服务开始,按照调用关系的顺序输出其中所有微服务的编号。

输入格式

第一行包含一个正整数 $n$,表示微服务的数量。
第二行包含 $n$ 个整数,表示数组 $edges$,相邻整数之间用空格分隔。其中 $edges[i]$ 表示存在一个从微服务 $i$ 到微服务 $edges[i]$ 的调用关系。

输出格式

输出一行整数,表示内聚值最大的微服务群组,其中微服务编号按照调用关系顺序输出,起始编号为群组内最小编号。相邻整数之间用空格分隔。

数据范围

• $2\le n\le 10^5$
• $0\le edges[i]\le n-1$
• $edges[i]\ne i$

样例输入1

4
3 3 0 2

样例输出1

0 3 2

样例输入2

12
2 6 10 1 6 0 3 0 5 4 5 8

样例输出2

0 2 10 5

【题目解析】

首先，我们需要编写一个函数来找到所有的微服务群组，并计算它们的内聚值。然后，我们按照规则对这些群组进行排序，并输出内聚值最大的群组。首先定义了一个 ServiceGroup 结构体，用于存储每个微服务群组的信息。然后，使用 findServiceGroups 函数找到所有的微服务群组，并计算它们的内聚值。最后，使用 compareGroups 函数对群组进行排序，并输出内聚值最大的群组。

cpp

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;struct ServiceGroup {int start;int size;int accessible_count;int cohesion;ServiceGroup(int _start, int _size, int _accessible_count) : start(_start), size(_size), accessible_count(_accessible_count) {cohesion = size - accessible_count;}
};// Function to find all service groups
vector<ServiceGroup> findServiceGroups(const vector<int>& edges) {int n = edges.size();vector<bool> visited(n, false);vector<ServiceGroup> groups;for (int i = 0; i < n; ++i) {if (!visited[i]) {int current = i;int group_start = i;int group_size = 0;int accessible_count = 0;while (!visited[current]) {visited[current] = true;group_size++;current = edges[current];}current = group_start;while (visited[current]) {visited[current] = false; // Reset visited flag for next iterationaccessible_count++;current = edges[current];}groups.push_back(ServiceGroup(group_start, group_size, accessible_count));}}return groups;
}// Comparator function for sorting service groups
bool compareGroups(const ServiceGroup& a, const ServiceGroup& b) {if (a.cohesion != b.cohesion) {return a.cohesion > b.cohesion;} else {return a.start < b.start;}
}int main() {int n;cin >> n;vector<int> edges(n);for (int i = 0; i < n; ++i) {cin >> edges[i];}vector<ServiceGroup> groups = findServiceGroups(edges);sort(groups.begin(), groups.end(), compareGroups);// Output the first groupfor (int i = groups[0].start; i < groups[0].start + groups[0].size; ++i) {cout << i << " ";}cout << endl;return 0;
}

整理试题不易，你的关注是我更新的最大动力！关注博主 带你看更多面试及竞赛试题和实用算法。