网易笔试 网易笔试题 0921
笔试时间：2024年09月21日 秋招
历史笔试传送门：2023秋招笔试合集
第一题
题目
小明家附近有两个购物超市A、B，两家超市中的商品种类都一致齐全,其中A超市离小明家更近，是小明购物的首选超市，但是B超市的有些商品会比A超市价格便宜，而且B超市有个购物规定，每次买东西只能选1件或多件相互挨着的商品，不能随意挑选。假设小明要采购一系列商品，每件只购买一次，只能在A或B超市中采购，并且他最多只去B超市采购一次，请你帮助计算本次采购全部商品清单所需的最低费用。
输入描述
输入包括两行，每行均为n个数字，用空格分隔，1<=n<10000000
第一行为本次需采购的n个商品在A超市的价格列表
第二行为本次需采购的n个商品在B超市的价格列表第二行非0正整数，且小于100。
输出描述
最低费用。
样例输入
36 87 47 55 51
39 77 46 57 50
样例输出
265
参考题解
作差，D[i] = B[i] - A[i]。然后求D数组的最小连续子数组和 min，输出 sum(A) + min。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
string lineA;
getline(cin, lineA);
string lineB;
getline(cin, lineB);
vector<int> A;
int num;
ll sumA = 0;
stringstream ssA(lineA);
while (ssA >> num)
{
A.push_back(num);
sumA += num;
}
stringstream ssB(lineB);
ll min_s = 0;
ll cur_s = 0;
int i = 0;
while (ssB >> num && i < A.size())
{
int D = num - A[i];
cur_s += D;
if (cur_s < min_s)
{
min_s = cur_s;
}
if (cur_s > 0)
{
cur_s = 0;
}
i++;
}
ll ans = sumA + min_s;
if (min_s >= 0)
{
ans = sumA;
}
cout << ans;
}
Java：[此代码未进行大量数据的测试，仅供参考]
Python：[此代码未进行大量数据的测试，仅供参考]
第二题
题目
有一座城市共有n个公交站点，站点编号为0到n-1。共有m辆公交车，每辆公交车的运行区间为a-b，表示公交车从a站点运行到b站点(a < b)，乘客可以在区间内的任意站点上下车进行换乘。小明需要从x站点乘坐公交到达v站点，请问至少需要乘坐几趟公交车?如果无法到达，则返回-1。如果起点和终点相同，则返回0。
输入描述
第一行输入为站点数n和公交数m，其中2<=n<=100，1<=m<=50
第二行输入为小明的起点站x和终点站y，其中0<=x<=y<=n-1
接下来m行为每趟公交车的起点站a和终点站b，其中0<=a<b<=n-1。
输出描述
输出最小需乘坐的公交次数，如果无法到达，则返回-1。如果起点和终点相同，则返回 0。
补充说明：m辆公交车的区间都不相同，但区间可能存在重叠。可将公交车视为单向运行，不用考虑往返
样例输入一
5 3
0 4
0 2
1 3
3 4
样例输出一
3
说明：第一趟从站点0乘坐到站点2，第二趟从站点2乘坐到站点3，第三趟从站点3乘坐到站点4，最少需要乘坐3趟公交。
样例输入二
3 1
0 2
0 1
样例输出二
-1
说明：无法达到
样例输入三
4 4
1 1
0 1
1 2
2 3
0 3
样例输出三
0
说明：小明从站点1到1不用车
参考题解
bfs。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
while (cin >> n >> m)
{
int x, y;
cin >> x >> y;
vector<pair<int, int>> buses(m);
for (auto &p : buses)
cin >> p.first >> p.second;
if (x == y)
{
cout << 0 << "\n";
continue;
}
unordered_map<int, vector<int>> g;
for (int i = 0; i < m; i++)
{
for (int j = buses[i].first; j <= buses[i].second; j++)
{
g[j].push_back(i);
}
}
queue<int> q;
vector<bool> vis1(n, false);
vector<bool> vis2(m, false);
q.push(x);
vis1[x] = true;
int res = 0;
bool found = false;
while (!q.empty())
{
int size = q.size();
res++;
for (int i = 0; i < size; i++)
{
int current = q.front();
q.pop();
for (auto bus : g[current])
{
if (vis2[bus])
continue;
vis2[bus] = true;
for (int j = buses[bus].first; j <= buses[bus].second; j++)
{
if (j == y)
{
found = true;
break;
}
if (!vis1[j])
{
vis1[j] = true;
q.push(j);
}
}
if (found)
break;
}
if (found)
break;
}
if (found)
{
cout << res << "\n";
break;
}
}
if (!found)
cout << -1 << "\n";
}
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int n = sc.nextInt();
int m = sc.nextInt();
int x = sc.nextInt();
int y = sc.nextInt();
List<int[]> buses = new ArrayList<>();
for (int i = 0; i < m; i++) {
int first = sc.nextInt();
int second = sc.nextInt();
buses.add(new int[]{first, second});
}
if (x == y) {
System.out.println(0);
continue;
}
Map<Integer, List<Integer>> g = new HashMap<>();
for (int i = 0; i < m; i++) {
for (int j = buses.get(i)[0]; j <= buses.get(i)[1]; j++) {
g.computeIfAbsent(j, k -> new ArrayList<>()).add(i);
}
}
Queue<Integer> q = new LinkedList<>();
boolean[] vis1 = new boolean[n + 1];
boolean[] vis2 = new boolean[m];
q.add(x);
vis1[x] = true;
int res = 0;
boolean found = false;
while (!q.isEmpty()) {
int size = q.size();
res++;
for (int i = 0; i < size; i++) {
int current = q.poll();
for (int bus : g.getOrDefault(current, new ArrayList<>())) {
if (vis2[bus]) continue;
vis2[bus] = true;
for (int j = buses.get(bus)[0]; j <= buses.get(bus)[1]; j++) {
if (j == y) {
found = true;
break;
}
if (!vis1[j]) {
vis1[j] = true;
q.add(j);
}
}
if (found) break;
}
if (found) break;
}
if (found) {
System.out.println(res);
break;
}
}
if (!found) System.out.println(-1);
}
sc.close();
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
from collections import deque, defaultdict
while True:
try:
n, m = map(int, input().split())
x, y = map(int, input().split())
buses = []
for _ in range(m):
first, second = map(int, input().split())
buses.append((first, second))
if x == y:
print(0)
continue
g = defaultdict(list)
for i in range(m):
for j in range(buses[i][0], buses[i][1] + 1):
g[j].append(i)
q = deque([x])
vis1 = [False] * (n + 1)
vis2 = [False] * m
vis1[x] = True
res = 0
found = False
while q:
size = len(q)
res += 1
for _ in range(size):
current = q.popleft()
for bus in g[current]:
if v
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解，包含python、C++、Java多种语言版本，持续更新中。
查看6道真题和解析