网易历年秋招笔试真题

如需获取完整资料，请点击下方链接领取《2024校招笔试真题秘籍》（实时更新中）

不收费，3人组团即可一块免费领取！限量免费10000个名额

手机端点击免费领取：https://www.nowcoder.com/link/campus_xzbs2

电脑端请扫码领取：

1、仓库配送

【题目描述】

网易严选建有N个自营仓分布在全国各地，标记为仓库1到N。

给定一个配货时间组（v,u,w)，v为出发仓库，u为目标仓库，w为从出发仓库到目标仓库的耗时时间。可能存在仓库间过远，无法支持调拨转货。

指定一个出发仓库K，我们需要将供应商发送到K仓库的货配送到各个仓库。问配送到所有可到达仓库所要最短时间？如果无法全部调拨到，则返回-1。

输入描述：

第一行三个正整数，由空格分割，分别表示仓库个数N，出发仓K，以及配送时间组个数M

接下来 M行，每行三个整数，由空格分割，分别表示（v,u,w)三个数，v为出发仓库，u为目标仓库，w为从出发仓库到目标仓库的耗时时间

输出描述：

一行一个数字表示答案，配送到所有可达仓库到最短时间

备注：

N的区间是[1, 100] ；

K的区间是[1, N] ；

times的最大长度是[1, 6000] ；

所有边 times[i] = (u, v, w)，1<=u, v <= N 0 <= w <= 100

输入样例：

6 2 5

2 1 1

2 6 2

1 3 3

3 4 1

6 5 2

输出样例：

5

说明：

由图可知，所需最短时间为1+3+1=5

【解题思路】

最短路问题，floyd或者dijkstra都可以

【参考代码】

int floyd(vector<vector<int>>& graph, int N, int source)
{
    for (int k = 1; k <= N; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (graph[i][k] != INT_MAX && graph[k][j] != INT_MAX)
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
    int ans = INT_MIN;
    for (int i = 1; i <= N; ++i) {
        ans = max(ans, graph[source][i]);
    }
    if (ans == INT_MAX)return -1;
    return ans;
}
int main()
{
    int N, K, M, v, u, w;
    cin >> N >> K >> M;
    vector<vector<int>> graph(N + 1, vector<int>(N + 1, INT_MAX));
    for (int i = 0; i < M; ++i) {
        cin >> v >> u >> w;
        graph[v][u] = w;
    }
    for (int i = 0; i < N; ++i) {
        graph[i][i] = 0;
    }
    cout << floyd(graph, N, K);
    return 0;
}

2、摩尔斯电码解码

【题目描述】

已知摩尔斯电码和字符映射关系如下：

A -> 0

B -> 1

C -> 10

D -> 11

E -> 100

F -> 101

G -> 110

H -> 111

当前我们获取到了一串01数字字符串，需要进行摩尔斯电码解码，请问共有多少种解码方法？

输入描述：

一行由0和1组成的字符串

输出描述：

一行一个数字表示答案，即解码方法数量

备注：

输入字符串长度范围为1～100

输出解码方法数不超过2147483647

输入样例1：

11

输出样例1：

2

说明1：

有D和BB两种解法

输入样例2：

100

输出样例2：

3

说明2：

有E,BAA和CA三种解法

【解题思路】

动态规划求解，注意当遇到字符'1'的时候，有三种翻译的方式

【参考代码】

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().toCharArray();
        int n = str.length;
        int[] dp = new int[n + 1];
        dp[n] = 1;         // 最后一个字符肯定只能是一种翻译
        // 从后往前遍历字符
        for(int i = n - 1; i >= 0; i--){
            dp[i] = dp[i + 1];     // 单字符码的情况
            if(str[i] == '1'){      // 对于"1"，还有双字符码和三字符码的情况
                if(i + 2 <= n) dp[i] += dp[i + 2];
                if(i + 3 <= n) dp[i] += dp[i + 3];
            }
        }
        System.out.println(dp[0]);
    }
}

3、项目经理

【题目描述】

A公司和B公司有n个合作的子项目，每个子项目由A公司和B公司各一名员工参与。一名员工可以参与多个子项目。

一个员工如果担任了该项目的项目经理，它需要对所参与的该项目负责。一个员工也可以负责多个项目。

A公司和B公司需要保证所有子项目都能有人负责，问最少需要指定几名项目经理？

输入描述：

第一行为A公司的的人员id列表， 0< id数量 < 10000，用空格切分

第二行为B公司的人员id列表， 0< id数量 < 10000，用空格切分

第三行为有已经有多少个匹配数子项目合作关系n

下面有n行，每一行为每个子项目的合作对应关系，为两个id，第一个为A公司的员工id，第二个为B公司的员工id，用空格区分

输出描述：

一个整数，A公司和B公司合起来至少需要指定几名项目经理

输入样例：

0 1 2

3 4 5

6

0 4

0 3

1 3

1 4

2 5

2 4

输出样例：

3

说明：

可行的一个保留人员方案是留下0,1,2即可，这样即可保证所有的子项目都有人cover到。

【解题思路】

二分图最小点覆盖

由Konig定理可知，最小点覆盖数=最大匹配边数

转换为二分图的最大匹配问题

【参考代码】

#include<bits/stdc++.h>
using namespace std;
vector<int> get(string s, int diff) {
    vector<int> a;
    stringstream str(s);
    int temp;
    while (str >> temp) a.push_back(temp + diff);
    return a;
}
const int maxn = 20100;
vector<vector<int>> e;
int match[maxn];
bool vis[maxn];
int ans;
bool dfs(int u) {
    for (int v:e[u]) {
        if (!vis[v]) {
            vis[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
    }
    return false;
}
int main() {
    vector<int> a, b;
    string s;
    getline(cin, s);
    a = get(s, 0);
    getline(cin