【秋招笔试】09.24华子(海外留学生版)秋招-三语言题解
🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历
✨ 本系列打算持续跟新
春秋招笔试题
👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 笔试合集传送们 -> 🧷春秋招笔试合集
🍒 本专栏已收集
120+
套笔试题,笔试真题
会在第一时间跟新🍄 题面描述等均已改编,如果和你笔试题看到的题面描述不一样请理解,做法和题目本质基本不变。
🍹 感谢各位朋友们的订阅,你们的支持是我们创作的最大动力 💞
🌈 华为秋招(海外留学生版)笔试,来啦!!!
🍥 留学生的题目难度相对于国内来说总体来看会简单一丢丢,但整体题目风格,难度,几乎都是一样的哦~
tips
国内的有些题会复用留学生考过的题目哦,国内机考的朋友可以把留学生的题目也刷一刷本次的
第一题
和第三题
分别是国内校招9.27
和10.9
的原题,懂得都懂,无须多言1️⃣ BFS+思维题,难度较大,有细节和坑点
2️⃣ 并查集+模拟+排序,考查的比较全面
3️⃣ 据说是暴力DFS能过,比较诈骗,大家实际考试的时候可以直接暴力骗分哦~
🌲 01.环保出行计划 评测链接🔗
问题描述
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]; // 存储从早餐店到每个站点的距离
static int[] visited = new int[MAX_STATIONS]; // 用于BFS中标记已访问的路线
static int[] breakfast_route = new int[MAX_ROUTES]; // 标记哪些路线包含早餐店
static long[] route_first_visit = new long[MAX_ROUTES]; // 记录每条路线首次被访问的时间
static List<List<Integer>> station_to_routes = new ArrayList<>(); // 存储每个站点所属的路线
static List<List<Integer>> routes = new ArrayList<>(); // 存储每条路线经过的站点
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
for (int i = 0; i < MAX_STATIONS; i++) {
station_to_routes.add(new ArrayList<>());
}
solve(scanner);
}
static void bfs_to_breakfast(int start, int breakfast) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
dist_to_breakfast[start] = 1; // 起点距离设为1
while (!q.isEmpty()) {
int current = q.poll();
for (int route : station_to_routes.get(current)) {
if (visited[route] == 0) {
route_first_visit[route] = dist_to_breakfast[current] + 1;
for (int station : routes.get(route)) {
if (dist_to_breakfast[station] == 0) {
dist_to_breakfast[station] = dist_to_breakfast[current] + 1;
q.offer(station);
}
}
visited[route] = 1; // 标记路线为已访问
}
}
}
// 标记包含早餐店的路线
for (int i = 1; i < routes.size(); i++) {
if (route_first_visit[i] == dist_to_breakfast[breakfast]) {
if (routes.get(i).contains(breakfast)) {
breakfast_route[i] = 1;
}
}
}
}
static void bfs_from_breakfast(int breakfast, int end) {
Arrays.fill(visited, 0); // 重置visited数组
Queue<Integer> q = new LinkedList<>();
q.offer(breakfast);
dist_from_breakfast[breakfast] = 1; // 早餐店距离设为1
while (!q.isEmpty()) {
int current = q.poll();
for (int route : station_to_routes.get(current)) {
if (visited[route] == 0) {
long distance = dist_from_breakfast[current] + 1;
if (breakfast_route[route] == 1) {
distance--; // 如果是包含早餐店的路线,不增加换乘次数
}
for (int station : routes.get(route)) {
if (dist_from_breakfast[station] == 0) {
dist_from_breakfast[station] = distance;
q.offer(station);
}
}
visited[route] = 1; // 标记路线为已访问
}
}
}
}
static void solve(Scanner scanner) {
// 读取输入
int start = scanner.nextInt();
int breakfast = scanner.nextInt();
int end = scanner.nextInt();
int num_routes = scanner.nextInt();
routes.add(new ArrayList<>()); // 添加一个空列表,使路线编号从1开始
for (int i = 1; i <= num_routes; i++) {
int num_stations = scanner.nextInt();
List<Integer> route = new ArrayList<>();
for (int j = 0; j < num_stations; j++) {
int station = scanner.nextInt();
route.add(station);
station_to_routes.get(station).add(i);
}
routes.add(route);
}
// 执行从起点到早餐店的BFS
bfs_to_breakfast(start, breakfast);
if (dist_to_breakfast[breakfast] == 0) {
System.out.println(-1); // 无法到达早餐店
return;
}
// 执行从早餐店到终点的BFS
bfs_from_breakfast(breakfast, end);
if (dist_from_breakfast[end] == 0) {
System.out.println(-1); // 无法到达终点
return;
}
// 计算并输出结果
System.out.println(dist_to_breakfast[breakfast] + dist_from_breakfast[end] - 2);
}
}
- Cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_STATIONS = 1000005; // 最大站点数
const int MAX_ROUTES = 505; // 最大路线数
// 全局变量声明
int dist_to_breakfast[MAX_STATIONS], dist_from_breakfast[MAX_STATIONS]; // 存储两次BFS的距离
int visited[MAX_STATIONS]; // 用于BFS中标记已访问的路线
int breakfast_route[MAX_ROUTES]; // 标记哪些路线包含早餐店
int route_first_visit[MAX_ROUTES]; // 记录每条路线首次被访问的时间
vector<int> station_to_routes[MAX_STATIONS]; // 存储每个站点所属的路线
vector<vector<int>> routes; // 存储每条路线经过的站点
// 从起点到早餐店的BFS
void bfs_to_breakfast(int start, int breakfast) {
queue<int> q;
q.push(start);
dist_to_breakfast[start] = 1; // 起点距离设为1
while (!q.empty()) {
int current = q.front();
q.pop();
for (auto route : station_to_routes[current]) {
if (!visited[route]) {
route_first_visit[route] = dist_to_breakfast[current] + 1;
for (auto station : routes[route]) {
if (!dist_to_breakfast[station]) {
dist_to_breakfast[station] = dist_to_breakfast[current] + 1;
q.push(station);
}
}
visited[route] = 1; // 标记路线为已访问
}
}
}
// 标记包含早餐店的路线
for (int i = 1; i < routes.size(); i++) {
if
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
这里收集了超全的互联网春秋招笔试题,欢迎大家的订阅,会持续跟新的