【秋招笔试】09.27华子秋招(已改编)-三语言题解
🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历
✨ 本系列打算持续跟新
春秋招笔试题
👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 笔试合集传送们 -> 🧷春秋招笔试合集
🍒 本专栏已收集
100+
套笔试题,笔试真题
会在第一时间跟新🍄 题面描述等均已改编,如果和你笔试题看到的题面描述不一样请理解,做法和题目本质基本不变。
🍹 感谢各位朋友们的订阅,你们的支持是我们创作的最大动力 💞
🌈 华子秋招笔试,来啦!!!
🍥 前两周出过一次 DFS 专场,华子这次直接来一次 BFS 专场,直呼好家伙
1️⃣ 二分图匹配的问题,数据范围比较小,每次可以直接暴力BFS
check
2️⃣ BFS模拟,本次比较难写的一题,中途下车再上同一辆车不算,这个要分开考虑,细节也比较多
3️⃣ BFS模拟题,主要考验大家的代码基本功。
🧸 01.分组问题 评测链接🔗
题目描述
K小姐所在的公司要进行一次员工绩效互评。为了避免员工之间因为私交而给彼此高分,公司决定将员工分成两组,每组员工只能为另一组的员工打分。
现在已知公司共有 名员工,编号从 到 。同时给出一个二维数组 ,其中 包含了与员工 关系密切(例如是好友或者同一个项目组)的其他员工的编号。
请你帮助 K小姐设计一个算法,将这 名员工分成两组,使得每组内部不存在关系密切的员工。如果无法找到满足要求的分组方案,则输出 。
输入格式
第一行包含一个正整数 ,表示员工总数。
接下来 行,第 行包含若干个整数,表示 ,即与员工 关系密切的其他员工的编号。
输出格式
如果存在满足要求的分组方案,则输出两行,每行包含若干个整数,表示一个组内的员工编号。员工编号按从小到大的顺序输出,两组之间的顺序也按照第一个员工编号的大小关系排序。
方案内部也按照编号从小到大排序。输出排序最靠前的一种方案,如无法分成符合条件的两组,则输出
如输出如下两种方案时,选择第一种方案,因为方案一的分组第一个节点编号更小:
分组:
分组:
和
分组:
分组:
如输出如下两种方案时,选择第二种方案,因为方案二的分组第一个节点编号更小:
分组:
分组:
和
分组:
分组:
如果找不到满足要求的分组方案,则输出 。
样例输入1
4
1 3
0 2
1 3
0 2
样例输出1
0 2
1 3
样例输入2
4
1 2 3
0 2
0 1 3
0 2
样例输出2
-1
数据范围
- 中不会包含 ,也不会有重复元素
- 数据保证 是对称的,即如果 ,则
题解
BFS/二分图染色
这道题目本质上是一个图的二分图染色问题。可以将员工看作图中的节点,关系密切的员工之间连一条边。问题就转化为:能否将图中的节点分成两组,使得每条边的两个端点分别属于不同的组。
可以用 BFS
或者 DFS
来对图进行遍历和染色。这里选择使用BFS
具体步骤如下:
-
构建邻接表来表示员工之间的关系。
-
使用一个数组
color
来记录每个员工的分组情况。初始时,所有员工都未分组,用 -1 表示。 -
对于每个未分组的员工,从他开始进行BFS:
- 将他放入队列,并给他染色(比如用 0 表示第一组)
- 不断从队列中取出员工,对于他的每个邻居(关系密切的员工):
- 如果邻居未染色,就给邻居染上相反的颜色,并将邻居加入队列
- 如果邻居已经染色,检查颜色是否与当前员工相同。如果相同,说明无法二分,直接返回 -1
-
如果BFS过程中没有发现冲突,就说明可以成功二分。我们将颜色为 0 的员工放入第一组,颜色为 1 的员工放入第二组。
-
最后,需要按照题目要求对输出进行排序:
- 两个组内部按员工编号从小到大排序
- 两个组之间按第一个员工编号的大小关系排序
时间复杂度分析:构建邻接表的时间复杂度是 ,其中 是员工数, 是关系的总数。BFS的时间复杂度也是 。排序的时间复杂度是 。因此,总的时间复杂度是 。
参考代码
- Python
from collections import deque
def solve():
# 读取输入
n = int(input())
graph = [[] for _ in range(n)]
for i in range(n):
relations = list(map(int, input().split()))
graph[i] = relations
# 初始化颜色数组,-1表示未染色
color = [-1] * n
# BFS函数
def bfs(start):
q = deque([start])
color[start] = 0
while q:
u = q.popleft()
for v in graph[u]:
if color[v] == -1:
color[v] = 1 - color[u]
q.append(v)
elif color[v] == color[u]:
return False
return True
# 对每个未染色的节点进行BFS
for i in range(n):
if color[i] == -1:
if not bfs(i):
print(-1)
return
# 将节点分组
group0 = [i for i in range(n) if color[i] == 0]
group1 = [i for i in range(n) if color[i] == 1]
# 对组内元素排序
group0.sort()
group1.sort()
# 如果需要交换两组
if group1 and (not group0 or group1[0] < group0[0]):
group0, group1 = group1, group0
# 输出结果
print(*group0)
print(*group1)
solve()
- Java
import java.util.*;
public class Main {
static List<List<Integer>> graph;
static int[] color;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.nextLine(); // 消耗换行符
// 初始化图和颜色数组
graph = new ArrayList<>(n);
color = new int[n];
Arrays.fill(color, -1);
// 读取输入并构建图
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
String[] relations = scanner.nextLine().split(" ");
for (String r : relations) {
graph.get(i).add(Integer.parseInt(r));
}
}
// 对每个未染色的节点进行BFS
for (int i = 0; i < n; i++) {
if (color[i] == -1 && !bfs(i)) {
System.out.println(-1);
return;
}
}
// 将节点分组
List<Integer> group0 = new ArrayList<>();
List<Integer> group1 = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (color[i] == 0) group0.add(i);
else group1.add(i);
}
// 对组内元素排序
Collections.sort(group0);
Collections.sort(group1);
// 如果需要交换两组
if (!group1.isEmpty() && (group0.isEmpty() || group1.get(0) < group0.get(0))) {
List<Integer> temp = group0;
group0 = group1;
group1 = temp;
}
// 输出结果
printGroup(group0);
printGroup(group1);
}
// BFS函数
static boolean bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
color[start] = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph.get(u)) {
if (color[v] == -1) {
color[v] = 1 - color[u];
queue.offer(v);
} else if (color[v] == color[u]) {
return false;
}
}
}
return true;
}
// 打印组
static void printGroup(List<Integer> group) {
for (int i = 0; i < group.size(); i++) {
System.out.print(group.get(i));
if (i < group.size() - 1) System.out.print(" ");
}
System.out.println();
}
}
- Cpp
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graph;
vector<int> color;
// BFS函数
bool bfs(int start) {
queue<int> q;
q.push(start);
color[start] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
if (color[v] == -1) {
color[v] = 1 - color[u];
q.push(v);
} else if (color[v] == color[u]) {
return false;
}
}
}
return true;
}
int main() {
int n;
cin >> n;
// 初始化图和颜色数组
graph.resize(n);
color.assign(n, -1);
// 读取输入并构建图
for (int i = 0; i < n; i++) {
string line;
getline(cin >> ws, line);
int num;
istringstream iss(line);
while (iss >> num) {
graph[i].push_back(num);
}
}
// 对每个未染色的节点进行BFS
for (int i = 0; i < n; i++) {
if (color[i] == -1 && !bfs(i)) {
cout << -1 << endl;
return 0;
}
}
// 将节点分组
vector<int> group0, group1;
for (int i = 0; i < n; i++) {
if (color[i] == 0) group0.push_back(i);
else group1.push_back(i);
}
// 对组内元素排序
sort(group0.begin(), group0.end());
sort(group1.begin(), group1.end());
// 如果需要交换两组
if (!group1.empty() && (group0.empty() || group1[0] < group0[0])) {
swap(group0, group1);
}
// 输出结果
for (int i = 0; i < group0.size(); i++) {
cout << group0[i] << (i < group0.size() - 1 ? " " : "\n");
}
for (int i = 0; i < group1.size(); i++) {
cout << group1[i] << (i < group1.size() - 1 ? " " : "\n");
}
return 0;
}
🌈 02.环保出行计划 评测链接🔗
问题描述
LYA 是一位热衷于环保的上班族。为了减少碳排放,她每天都选择乘坐公共交通工具上班。城市的公交系统由多条单向循环路线组成,每条路线都有固定的站点序列。例如,25 路公交的路线为 ,那么公交车会按照 的顺序循环行驶。
LYA 的日常通勤路线包括三个关键站点:最近的上车站、最喜欢的早餐店所在站点,以及离公司最近的下车站。她希望在保证买到早餐的前提下,用最少的换乘次数完成整个通勤过程。
你的任务是帮助 LYA 规划最优的乘车路线,使得她乘坐的公交车总数最少。需要注意的是,如果在同一条公交路线中下车再上车,仍然视为乘坐同一辆车。
输入格式
第一行包含 3 个整数 、、,分别表示 LYA 的上车站点编号、早餐店所在站点编号和下车站点编号。
第二行包含一个整数 ,表示公交路线的数量。
接下来的 行,每行描述一条公交路线。每行的第一个整数 表示该路线的站点数量,后面跟着 个整数,表示该路线经过的站点编号(按顺序排列)。
输出格式
输出一个整数,表示 LYA 需要乘坐的公交车数量的最小值。如果无法找到满足条件的路线,输出 。
样例输入 1
1 3 5
4
3 1 2 6
3 2 3 7
3 5 6 8
2 5 7
样例输出 1
3
样例解释 1
LYA 可以按以下路线行进:
- 在站点 1 乘坐第一条路线的公交车。
- 在站点 2 下车,换乘第二条路线的公交车。
- 在站点 3 下车购买早餐,然后继续乘坐第二条路线的公交车。
- 在站点 7 下车,换乘第四条路线的公交车。
- 最终在站点 5 下车到达公司。
总共乘坐了 3 辆不同的公交车(),因此输出 3。
样例输入 2
1 3 4
2
3 1 2 4
3 3 5 6
样例输出 2
-1
样例解释 2
LYA 只能乘坐第 1 条公交路线上车,但无法通过该路线的站台换乘到第 2 条公交路线购买早餐,因此没有匹配的路线,返回 -1。
样例输入 3
4 19 28
5
5 3 4 7 8 10
6 10 12 16 19 27 28
4 5 7 11 17
4 17 19 22 23
3 23 27 28
样例输出 3
2
样例解释 3
LYA 可以选择 的公交路线,乘坐的公交车总数为 2。虽然也可以选择 的公交路线,但这样需要乘坐 4 辆公交车。因此,最佳的乘车路线是 ,结果为 2。
数据范围
- 公交路线数量 的范围:。
- 公交站台编号的范围:。
- 每条公交路线经过的站台数量范围:。
- 保证起点站台、早餐站点和终点站台互不相同。
- 每条路线中的站台编号按升序排列,且不包含重复的站台。
题解
两次BFS+思维
关键点在于理解题目的特殊规则:在早餐店换乘同一辆车不算额外的换乘次数。这就好比在早餐店门口下车,买完早餐后又坐回同一辆车,这种情况下不需要额外付车费。
解决这个问题的思路其实很直观。首先,从起点出发,找到到达早餐店的最短路径。然后,从早餐店出发,找到到达公司的最短路径。这两段路径加起来就是整个旅程的最优解。
具体来说,可以使用两次(BFS)来实现:
- 第一次BFS:从起点到早餐店。
- 第二次BFS:从早餐店到公司。
在第二次BFS中,需要特别注意处理在早餐店的特殊换乘规则。如果某条路线经过早餐店,那么在这条路线上继续前进不需要增加换乘次数。
举个例子,假设有以下公交路线:
1号线:1 -> 2 -> 3 -> 4
2号线:2 -> 5 -> 6
3号线:4 -> 5 -> 7
起点在1,早餐店在4,终点在7。
第一次BFS会得到路径:1 -> 2 -> 3 -> 4(1号线),换乘次数为0。 标记1号线为包含早餐店的路线。
第二次BFS时,从4出发:
- 可以直接使用1号线到达其他站点,不增加换乘次数。
- 使用3号线时需要增加换乘次数。
最终路径可能是:1 -> 2 -> 3 -> 4(1号线)-> 5 -> 7(3号线),总换乘次数为 1。
参考代码
- Python
from collections import deque
MAX_STATIONS = 1000005 # 最大站点数
MAX_ROUTES = 505 # 最大路线数
# 初始化全局变量
dist_to_breakfast = [0] * MAX_STATIONS # 存储从起点到每个站点的距离
dist_from_breakfast = [0] * MAX_STATIONS # 存储从早餐店到每个站点的距离
visited = [0] * MAX_STATIONS # 用于BFS中标记已访问的路线
breakfast_route = [0] * MAX_ROUTES # 标记哪些路线包含早餐店
route_first_visit = [0] * MAX_ROUTES # 记录每条路线首次被访问的时间
station_to_routes = [[] for _ in range(MAX_STATIONS)] # 存储每个站点所属的路线
routes = [] # 存储每条路线经过的站点
def bfs_to_breakfast(start, breakfast):
q = deque([start])
dist_to_breakfast[start] = 1 # 起点距离设为1
while q:
current = q.popleft()
for route in station_to_routes[current]:
if not visited[route]:
route_first_visit[route] = dist_to_breakfast[current] + 1
for station in routes[route]:
if not dist_to_breakfast[station]:
dist_to_breakfast[station] = dist_to_breakfast[current] + 1
q.append(station)
visited[route] = 1 # 标记路线为已访问
# 标记包含早餐店的路线
for i in range(1, len(routes)):
if route_first_visit[i] == dist_to_breakfast[breakfast]:
if breakfast in routes[i]:
breakfast_route[i] = 1
def bfs_from_breakfast(breakfast, end):
global visited
visited = [0] * MAX_STATIONS # 重置visited数组
q = deque([breakfast])
dist_from_breakfast[breakfast] = 1 # 早餐店距离设为1
while q:
current = q.popleft()
for route in station_to_routes[current]:
if not visited[route]:
distance = dist_from_breakfast[current] + 1
if breakfast_route[route]:
distance -= 1 # 如果是包含早餐店的路线,不增加换乘次数
for station in routes[route]:
if not dist_from_breakfast[station]:
dist_from_breakfast[station] = distance
q.append(station)
visited[route] = 1 # 标记路线为已访问
def solve():
# 读取输入
start, breakfast, end = map(int, input().split())
num_routes = int(input())
global routes
routes = [[] for _ in range(num_routes + 1)] # 路线编号从1开始
for i in range(1, num_routes + 1):
route = list(map(int, input().split()))
routes[i] = route[1:] # 第一个数字是站点数量,跳过
for station in routes[i]:
station_to_routes[station].append(i)
# 执行从起点到早餐店的BFS
bfs_to_breakfast(start, breakfast)
if not dist_to_breakfast[breakfast]:
print(-1) # 无法到达早餐店
return
# 执行从早餐店到终点的BFS
bfs_from_breakfast(breakfast, end)
if not dist_from_breakfast[end]:
print(-1) # 无法到达终点
return
# 计算并输出结果
print(dist_to_breakfast[breakfast]+ dist_from_breakfast[end] - 2)
solve() # 执行主函数
- Java
import java.util.*;
public class Main {
static final int MAX_STATIONS = 1000005; // 最大站点数
static final int MAX_ROUTES = 505; // 最大路线数
// 初始化全局变量
static long[] dist_to_breakfast = new long[MAX_STATIONS]; // 存储从起点到每个站点的距离
static long[] dist_from_breakfast = new long[MAX_STATIONS]
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
这里收集了超全的互联网春秋招笔试题,欢迎大家的订阅,会持续跟新的