🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

🍍01.LYA 的云服务计费系统

问题描述

LYA 是一家云服务提供商，她需要为客户提供云服务计费功能。现在，她有一份包含多条计费日志的文件，每条日志包含时间戳、客户标识、计费因子和计费时长四个字段。此外，她还有一份计费因子的单价列表。

LYA 需要编写一个程序，根据计费日志和计费因子单价列表，计算每个客户的话单总费用。需要注意的是，如果同一客户在相同时间戳上报了多条相同计费因子的日志，只能计费一次，并且选择先上报的日志进行计费。

输入格式

第一行包含一个正整数 $n$，表示计费日志的条数，$1\le n\le 1000$。

接下来的 $n$ 行，每行包含四个字段，分别表示时间戳（长度为 $10$ 的数字字符串）、客户标识（长度为 $1\sim 16$ 的字符串）、计费因子（长度为 $1\sim 16$ 的字符串）和计费时长（范围为 $0\sim 100$ 的整数），字段之间用逗号分隔。如果计费因子在单价列表中查不到，则认为其单价为 $0$；如果计费时长不在 $0\sim 100$ 的范围内，则认为计费时长为 $0$。

接下来一行包含一个正整数 $m$，表示计费因子的数量，$1\le m\le 100$。

最后的 $m$ 行，每行包含两个字段，分别表示计费因子（长度为 $1\sim 16$ 的字符串）和单价（范围为 $1\sim 100$ 的整数），字段之间用逗号分隔。

输出格式

输出每个客户的话单总费用，每行包含两个字段，分别表示客户标识和话单费用，字段之间用逗号分隔。输出按照客户标识的字典序升序排列。

样例输入

5
1627845600,client1,factorA,10
1627845605,client2,factorB,15
1627845610,client1,factorA,5
1627845615,client1,factorB,10
1627845620,client2,factorB,20
2
factorA,5
factorB,7

样例输出

client1,131
client2,245

数据范围

• $1\le n\le 1000$
• $1\le m\le 100$
• 时间戳是长度为 $10$ 的数字字符串
• 客户标识和计费因子是长度为 $1\sim 16$ 的字符串
• 计费时长的范围为 $0\sim 100$
• 计费因子的单价范围为 $1\sim 100$

题解

本题可以使用哈希表来解决。

首先，可以使用一个哈希表 fac 来存储计费因子和对应的单价。

然后，遍历计费日志，对于每条日志，可以提取出时间戳、客户标识、计费因子和计费时长。如果同一客户在相同时间戳上报了多条相同计费因子的日志，只计费一次，并且选择先上报的日志进行计费。为了实现这个功能，可以使用一个哈希集合 ss 来记录已经处理过的日志。

接下来，可以使用另一个哈希表 val 来存储每个客户的话单费用。对于每条有效的日志，可以根据计费因子在 fac 中查找对应的单价，然后将单价乘以计费时长，累加到对应客户的话单费用中。

最后，将 val 中的数据转换为列表，按照客户标识进行字典序排序，然后输出每个客户的话单费用即可。

时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

参考代码

• Python

n = int(input())
logs = []
seen = set()
for _ in range(n):
    ts, cid, fac, dur = input().split(',')
    key = ts + cid + fac
    if key not in seen:
        logs.append((ts, cid, fac, int(dur)))
        seen.add(key)

prices = {}
m = int(input())
for _ in range(m):
    fac, price = input().split(',')
    prices[fac] = int(price)

bills = {}
for ts, cid, fac, dur in logs:
    if cid not in bills:
        bills[cid] = 0
    if dur < 0 or dur > 100:
        dur = 0
    bills[cid] += prices.get(fac, 0) * dur

ans = sorted(bills.items())
for cid, bill in ans:
    print(f'{cid},{bill}')

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        
        List<String[]> logs = new ArrayList<>();
        Set<String> seen = new HashSet<>();
        for (int i = 0; i < n; i++) {
            String[] log = sc.nextLine().split(",");
            String key = log[0] + log[1] + log[2];
            if (!seen.contains(key)) {
                logs.add(log);
                seen.add(key);
            }
        }
        
        int m = sc.nextInt();
        sc.nextLine();
        Map<String, Integer> prices = new HashMap<>();
        for (int i = 0; i < m; i++) {
            String[] price = sc.nextLine().split(",");
            prices.put(price[0], Integer.parseInt(price[1]));
        }
        
        Map<String, Integer> bills = new HashMap<>();
        for (String[] log : logs) {
            String cid = log[1];
            String fac = log[2];
            int dur = Integer.parseInt(log[3]);
            if (dur < 0 || dur > 100) {
                dur = 0;
            }
            bills.put(cid, bills.getOrDefault(cid, 0) + prices.getOrDefault(fac, 0) * dur);
        }
        
        List<String> ans = new ArrayList<>(bills.keySet());
        Collections.sort(ans);
        for (String cid : ans) {
            System.out.println(cid + "," + bills.get(cid));
        }
    }
}

• Cpp

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    cin.ignore();
    
    vector<vector<string>> logs;
    unordered_set<string> seen;
    for (int i = 0; i < n; i++) {
        string line;
        getline(cin, line);
        vector<string> log;
        size_t pos = 0;
        while ((pos = line.find(',')) != string::npos) {
            log.push_back(line.substr(0, pos));
            line.erase(0, pos + 1);
        }
        log.push_back(line);
        string key = log[0] + log[1] + log[2];
        if (!seen.count(key)) {
            logs.push_back(log);
            seen.insert(key);
        }
    }
    
    int m;
    cin >> m;
    cin.ignore();
    unordered_map<string, int> prices;
    for (int i = 0; i < m; i++) {
        string line;
        getline(cin, line);
        size_t pos = line.find(',');
        string fac = line.substr(0, pos);
        int price = stoi(line.substr(pos + 1));
        prices[fac] = price;
    }
    
    unordered_map<string, int> bills;
    for (auto& log : logs) {
        string cid = log[1];
        string fac = log[2];
        int dur = stoi(log[3]);
        if (dur < 0 || dur > 100) {
            dur = 0;
        }
        bills[cid] += prices[fac] * dur;
    }
    
    vector<pair<string, int>> ans(bills.begin(), bills.end());
    sort(ans.begin(), ans.end());
    for (auto& [cid, bill] : ans) {
        cout << cid << "," << bill << endl;
    }
    
    return 0;
}

🍎 02.LYA 的图片分类算法

问题描述

LYA 是一位图像处理工程师，她需要设计一个算法来对一批图片进行分类。首先，她对每张图片提取特征，并计算任意两张图片之间的相似度。然后，根据以下规则将图片归类：

1. 如果两张图片的相似度大于 $0$，则认为它们是相似的；
2. 如果图片 $A$ 和 $B$ 相似，$B$ 和 $C$ 相似，但 $A$ 和 $C$ 不相似，则认为 $A$ 和 $C$ 是间接相似的，可以将 $A$、$B$、$C$ 归为一类，但不计算 $A$ 和 $C$ 的相似度；
3. 如果一张图片与所有其他图片都不相似，则它自成一类，相似度为 $0$。

给定一个大小为 $N\times N$ 的矩阵 $M$，其中 $M[i][j]$ 表示第 $i$ 张图片和第 $j$ 张图片的相似度，请按照从大到小的顺序返回每个相似类中所有图片的相似度之和。

输入格式

第一行包含一个正整数 $N$（$1\le N\le 900$），表示矩阵 $M$ 中图片的数量。

接下来的 $N$ 行，每行包含 $N$ 个用空格分隔的非负整数，表示矩阵 $M$。其中，$0\le M[i][j]\le 100$，并且保证 $M[i][j]=M[j][i]$。

注意：输入的矩阵元素之间的分隔符可能是一个或多个连续的空格。

输出格式

输出每个相似类的相似度之和，按照从大到小的顺序输出。每个数占一行，相邻两个数之间用一个空格分隔。

样例输入

5
0 0 50 0 0
0 0 0 25 0
50 0 0 0 15
0 25 0 0 0
0 0 15 0 0

样例输出

65 25

数据范围

• $1\le N\le 900$
• $0\le M[i][j]\le 100$

题解

本题可以使用并查集来解决。

首先，为每张图片创建一个集合，初始时每个集合只包含一张图片。然后，我们遍历矩阵 $M$，对于任意两张图片 $i$ 和 $j$，如果它们的相似度大于 $0$，则将它们所在的集合合并。

在合并集合时，需要将相似度累加到集合的根节点上。这样，在合并完成后，每个集合的根节点上的相似度之和就是该相似类的相似度之和。

最后，遍历所有图片，找出每个集合的根节点，将根节点上的相似度之和加入答案数组中。将答案数组按照从大到小的顺序排序后输出即可。

时间复杂度 $O(N^2\log N)$，空间复杂度 $O(N)$。

参考代码

• Python

def find(x):
    if p[x] != x:
        root = find(p[x])
        p[x] = root
        return root
    return x

n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]

p = list(range(n))
s = [0] * n

for i in range(n):
    for j in range(i + 1, n):
        if g[i][j] > 0:
            a, b = find(i), find(j)
            if a != b:
                s[a] += s[b]
                p[b] = a
            s[a] += g[i][j]

ans = [s[i] for i in range(n) if p[i] == i]
ans.sort(reverse=True)

print(*ans)

• Java

import java.io.*;
import java.util.*;

public class Main {
    static int[] p;
    static int[] s;

    static int find(int x) {
        if (p[x] != x) {
            int root = find(p[x]);
            p[x] = root;
            return root;
        }
        return x;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] g = new int[n][n];
        for (int i = 0; i < n; i++) {
            String[] row = br.readLine().split("\\s+");
            for (int j = 0; j < n; j++) {
                g[i][j] = Integer.parseInt(row[j]);
            }
        }

        p = new int[n];
        s = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (g[i][j] > 0) {
                    int a = find(i), b = find(j);
                    if (a != b) {
                        s[a] += s[b];
                        p[b] = a;
                    }
                    s[a] += g[i][j];
                }
            }
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (p[i] == i) {
                ans.add(s[i]);
            }
        }
        Collections.sort(ans, Collections.reverseOrder());

        for (int i = 0; i < ans.size(); i++) {
            System.out.print(ans.get(i));
            if (i < ans.size() - 1) {
                System.out.print(" ");
            }
        }
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 910;
int p[N], s[N];

int find(int x) {
    if (p[x] != x) {
        int root = find(p[x]);
        p[x] = root;
        return root;
    }
    return x;
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> g[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        p[i] = i;
    }

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (g[i][j] > 0) {
                int a = find(i), b = find(j);
                if (a != b) {
                    s[a] += s[b];
                    p[b] = a;
                }
                s[a] += g[i][j];
            }
        }
    }

    vector<int> ans;
    for (int i = 0; i < n; i++) {
        if (p[i] == i) {
            ans.push_back(s[i]);
        }
    }
    sort(ans.rbegin(), ans.rend());

    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i];
        if (i < ans.size() - 1) {
            cout << " ";
        }
    }

    return 0;
}

🍌 03.网络入侵检测

问题描述

K小姐是一名网络安全工程师，她负责维护一个由 $N$ 个节点组成的内部网络。这个网络的连通性可以用一个 $N\times N$ 的矩阵 $matrix$ 来表示，其中 $matrix[i][j]=p$ 表示从节点 $i$ 到节点 $j$ 需要的最低权限等级为 $p$（$p=0$ 表示不连通）。如果成功访问了节点 $j$，则该节点的权限等级会被调整为 $p$。

某天，K小姐发现有一些节点暴露在了公网上，存在被外部攻击的风险。暴露节点的编号保存在数组 $exposed$ 中。如果攻击者从公网入侵了某个暴露节点，则该节点的权限等级会变为最高等级 $10$。同时，入侵可以在网络内部传播，只要满足权限等级的要求即可。

为了尽快控制损失，K小姐决定立即将某个暴露节点从公网断开。她希望你能帮忙计算，断开哪个节点能够使最终被入侵的节点数量最少。如果有多个答案，则输出编号最小的节点。

输入格式

第一行包含一个正整数 $N$，表示网络中节点的数量。

接下来 $N$ 行，每行包含 $N$ 个空格分隔的整数，表示矩阵 $matrix$。

最后一行包含若干个空格分隔的整数，表示数组 $exposed$。

输出格式

输出一个整数，表示应该断开的节点编号。

样例输入

4
1 0 0 0
0 1 2 0
0 1 1 4
0 0 3 1
1 3

样例输出

3

数据范围

• $2\le N\le 24$
• $0\le matrix[i][j]\le 10$
• $0\le exposed[i]<N$

题解

本题可以用DFS求解。基本思路如下：

1. 枚举断开的节点 $x$，将其从 $exposed$ 中移除。
2. 对于 $exposed$ 中的每个节点 $u$，从 $u$ 开始DFS搜索所有可达的节点，并记录数量。权限等级初始为 $10$。
3. 如果当前节点 $u$ 可以访问节点 $v$（即 $matrix[u][v]$ 不为 $0$ 且不超过当前权限等级），则将 $v$ 加入DFS，并将权限等级更新为 $matrix[u][v]$。
4. 选择最终被入侵节点数量最少的 $x$ 作为答案。如有多个，取编号最小的。

时间复杂度 $O(N^3)$，空间复杂度 $O(N^2)$。

参考代码

• Cpp

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
const int N = 30;
int a[N][N];
bool st[N];

int dfs(int id, int ra) {
    int num = 0, sm = 0;
    for (int i = 0; i < n; i++) {
        if (id == i || !a[id][i]) continue;
        if (ra >= a[id][i]) {
            if (st[i]) continue;
            st[i] = true;
            num += dfs(i, a[id][i]);
            st[i] = false;
        }
    }
    return num + 1;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    int x;
    int res = -1, ans = 0;
    while (cin >> x) {
        for (int i = 0; i < n; i++) {
            if (x == i) continue;
            st[x] = true;
            int t = dfs(x, 10);
            st[x] = false;
            if (t > ans) {
                ans = t;
                res = x;
            }
        }
    }
    cout << res;
    return 0;
}

• Python

n = int(input())
N = 30
a = [[0] * N for _ in range(N)]
st = [False] * N

def dfs(id, ra):
    num = 0
    for i in range(n):
        if id == i or a[id][i] == 0:
            continue
        if ra >= a[id][i]:
            if st[i]:
                continue
            st[i] = True
            num += dfs(i, a[id][i])
            st[i] = False
    return num + 1

for i in range(n):
    a[i] = list(map(int, input().split()))

x = int(input())
res, ans = -1, 0
while True:
    if x == -1:
        break
    for i in range(n):
        if x == i:
            continue
        st[x] = True
        t = dfs(x, 10)
        st[x] = False
        if t > ans:
            ans = t
            res = x
    x = int(input())

print(res)

• Java

import java.util.Scanner;

public class Main {
    static int n;
    static final int N = 30;
    static int[][] a = new int[N][N];
    static boolean[] st = new boolean[N];

    public static int dfs(int id, int ra) {
        int num = 0;
        for (int i = 0; i < n; i++) {
            if (id == i || a[id][i] == 0) continue;
            if (ra >= a[id][i]) {
                if (st[i]) continue;
                st[i] = true;
                num += dfs(i, a[id][i]);
                st[i] = false;
            }
        }
        return num + 1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = scanner.nextInt();
            }
        }
        int x;
        int res = -1, ans = 0;
        while (scanner.hasNextInt()) {
            x = scanner.nextInt();
            for (int i = 0; i < n; i++) {
                if (x == i) continue;
                st[x] = true;
                int t = dfs(x, 10);
                st[x] = false;
                if (t > ans) {
                    ans = t;
                    res = x;
                }
            }
        }
        System.out.println(res);
    }
}

写在最后

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。