【华为笔试题汇总】2024-04-10-华为春招笔试题(第二套)-三语言题解(CPP/Python/Java)

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

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

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

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

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

🧷 01.K小姐的生日派对

问题描述

K小姐即将迎来自己的生日,为了庆祝这一天,她邀请了许多朋友来参加生日派对。派对结束后,K小姐发现有一位朋友在派对上出现的次数超过了所有朋友总出现次数的一半。K小姐很想知道这位朋友是谁,你能帮助她找出这位神秘朋友吗?

输入格式

输入包含一行,为一个以逗号分隔的正整数列表,表示每位朋友的编号。编号范围为 $1$ 到 $100000$,朋友总数不超过 $1000$。

输出格式

输出一个整数,表示出现次数超过总出现次数一半的朋友编号。如果不存在这样的朋友,则输出 $0$。

当朋友总数为偶数 $n$ 时,超过总数一半意味着出现次数大于 $\frac{n}{2}$;当朋友总数为奇数 $n$ 时,超过总数一半意味着出现次数大于 $\frac{n+1}{2}$。

样例输入

1,2,3,2,2

样例输出

2

数据范围

• $1\le$ 朋友编号 $\le 100000$
• $1<$ 朋友总数 $<1000$

题解

本题可以使用模拟的方法求解。我们可以用一个数组 $cnt$ 来记录每个朋友出现的次数,然后遍历这个数组,判断是否存在出现次数超过总出现次数一半的朋友。

具体步骤如下:

1. 初始化一个长度为 $100001$ 的数组 $cnt$,用于记录每个朋友出现的次数。
2. 读入朋友编号序列,对于每个编号 $x$,将 $cnt[x]$ 的值加 $1$,同时累加朋友总数 $total$。
3. 计算出现次数的临界值 $half$,即 $\lfloor \frac{total}{2}\rfloor$。
4. 遍历数组 $cnt$,判断是否存在某个元素的值大于 $half$,如果存在则输出对应的朋友编号,否则输出 $0$。

时间复杂度为 $O(n)$,其中 $n$ 为朋友总数。空间复杂度为 $O(m)$,其中 $m$ 为朋友编号的范围。

参考代码

• Python

friends = list(map(int, input().split(',')))
cnt = [0] * 100001
total = 0for x in friends:cnt[x] += 1total += 1half = total // 2for i in range(1, 100001):if cnt[i] > half:print(i)exit(0)print(0)

• Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String[] input = sc.nextLine().split(",");int[] cnt = new int[100001];int total = 0;for (String x : input) {int num = Integer.parseInt(x);cnt[num]++;total++;}int half = total / 2;for (int i = 1; i <= 100000; i++) {if (cnt[i] > half) {System.out.println(i);return;}}System.out.println(0);}
}

• Cpp

#include <iostream>
using namespace std;const int MAXN = 100001;int main() {int cnt[MAXN] = {0};int total = 0;string input;getline(cin, input);int pos = 0;while (pos < input.size()) {int num = 0;while (pos < input.size() && input[pos] != ',') {num = num * 10 + (input[pos] - '0');pos++;}cnt[num]++;total++;pos++;}int half = total / 2;for (int i = 1; i < MAXN; i++) {if (cnt[i] > half) {cout << i << endl;return 0;}}cout << 0 << endl;return 0;
}

🔗 02.LYA 的生日派对邀请函传递

问题描述

LYA 正在筹备自己的生日派对,她邀请了公司里的许多同事。为了方便传递邀请函,LYA 决定采用一种特殊的方式:当一位同事收到邀请函后,如果 TA 所在的部门在允许传递的部门列表中,就将邀请函传递给周围(上、下、左、右)的同事;否则,就不再传递。

公司的办公室可以看作一个 $n\times m$ 的网格,每个格子代表一个工位。LYA 的工位位于 $(x,y)$,她会在这里开始传递邀请函。

给定办公室的布局、LYA 的工位坐标以及允许传递邀请函的部门列表,请问最终会有多少人收到邀请函?

输入格式

第一行包含两个整数 $n$ 和 $m$,表示办公室的行数和列数。

接下来 $n$ 行,每行包含 $m$ 个整数,表示办公室的布局。每个整数代表该位置上同事所在的部门编号。

再接下来一行包含两个整数 $x$ 和 $y$,表示 LYA 的工位坐标。

最后一行包含若干个整数,表示允许传递邀请函的部门列表,整数之间用空格隔开。

输出格式

输出一个整数,表示最终收到邀请函的人数。

样例输入

5 5
1 3 5 2 3
2 2 1 3 5
2 2 1 3 3
4 4 1 1 1
1 1 5 1 2
2 2
1

样例输出

5

数据范围

• $1\le n,m\le 1000$
• $1\le$ 部门编号 $\le 50$
• $0\le x<n$
• $0\le y<m$
• $1\le$ 允许传递的部门数量 $\le 50$

题解

本题可以使用 BFS 算法求解。从 LYA 的工位开始,将邀请函传递给周围的同事,如果这些同事所在的部门允许传递邀请函,就将他们加入队列中,并标记为已访问。不断从队列中取出同事,重复上述过程,直到队列为空。最终访问过的同事数量就是收到邀请函的人数。

具体步骤如下:

1. 使用二维数组 $grid$ 存储办公室的布局,$grid[i][j]$ 表示位置 $(i,j)$ 上同事所在的部门编号。
2. 使用集合 $allowed$ 存储允许传递邀请函的部门列表。
3. 使用二维数组 $vis$ 标记每个位置是否被访问过,初始时除了 LYA 的工位外,其余位置都未被访问。
4. 创建一个队列 $q$,将 LYA 的工位坐标 $(x,y)$ 加入队列,并标记为已访问。
5. 初始化答案 $ans=0$,表示收到邀请函的人数。
6. 当队列不为空时,重复以下步骤:
   • 从队列中取出一个位置 $(i,j)$。
   • 枚举 $(i,j)$ 的四个相邻位置 $(ni,nj)$:
     • 如果 $(ni,nj)$ 在网格范围内,且未被访问过,且 $grid[ni][nj]$ 在 $allowed$ 中,则将 $(ni,nj)$ 加入队列,标记为已访问,并将 $ans$ 加 $1$。
7. 返回答案 $ans$。

时间复杂度 $O(nm)$,空间复杂度 $O(nm)$。其中 $n$ 和 $m$ 分别为办公室的行数和列数。

参考代码

• Python

from collections import dequen = int(input())
m = int(input())
grid = [list(map(int, input().split())) for _ in range(n)]
x, y = map(int, input().split())
allowed = set(map(int, input().split()))vis = [[False] * m for _ in range(n)]
vis[x][y] = Trueq = deque([(x, y)])
ans = 0while q:i, j = q.popleft()for ni, nj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:if 0 <= ni < n and 0 <= nj < m and not vis[ni][nj] and grid[ni][nj] in allowed:vis[ni][nj] = Trueq.append((ni, nj))ans += 1print(ans)

• Java

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt();int[][] grid = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {grid[i][j] = sc.nextInt();}}int x = sc.nextInt(), y = sc.nextInt();Set<Integer> allowed = new HashSet<>();while (sc.hasNextInt()) {allowed.add(sc.nextInt());}boolean[][] vis = new boolean[n][m];vis[x][y] = true;Queue<int[]> q = new LinkedList<>();q.offer(new int[]{x, y});int ans = 0;int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};while (!q.isEmpty()) {int[] pos = q.poll();int i = pos[0], j = pos[1];for (int[] dir : dirs) {int ni = i + dir[0], nj = j + dir[1];if (ni >= 0 && ni < n && nj >= 0 && nj < m && !vis[ni][nj] && allowed.contains(grid[ni][nj])) {vis[ni][nj] = true;q.offer(new int[]{ni, nj});ans++;}}}System.out.println(ans);}
}

• Cpp

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}int x, y;cin >> x >> y;unordered_set<int> allowed;int dept;while (cin >> dept) {allowed.insert(dept);}vector<vector<bool>> vis(n, vector<bool>(m, false));vis[x][y] = true;queue<pair<int, int>> q;q.push({x, y});int ans = 0;int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};while (!q.empty()) {auto [i, j] = q.front();q.pop();for (int k = 0; k < 4; k++) {int ni = i + dx[k], nj = j + dy[k];if (ni >= 0 && ni < n && nj >= 0 && nj < m && !vis[ni][nj] && allowed.count(grid[ni][nj])) {vis[ni][nj] = true;q.push({ni, nj});ans++;}}}cout << ans << endl;return 0;
}

📎 03.LYA 的生日蛋糕订购

问题描述

LYA 的生日快到了,她打算订购一个特别的生日蛋糕。蛋糕店提供了若干种口味的蛋糕,每种口味的蛋糕都有对应的卡路里。为了保持身材,LYA 希望蛋糕的总卡路里在一定范围内。

现在给定蛋糕店提供的各种口味蛋糕的卡路里,以及 LYA 希望的总卡路里范围,请问 LYA 有多少种选择方案?

注意:

1. 每种口味的蛋糕可以选择任意多个。
2. 不同口味的蛋糕卡路里各不相同。

输入格式

第一行包含两个整数 $low$ 和 $high$,表示 LYA 希望的蛋糕总卡路里的下限和上限。

第二行包含若干个整数,表示蛋糕店提供的各种口味蛋糕的卡路里,整数之间用空格隔开。

输出格式

输出一个整数,表示 LYA 的选择方案数。

样例输入

350 500
100 200 500

样例输出

7

数据范围

• $1\le low\le 1000$
• $1\le high\le 1000$
• $1\le$ 蛋糕种类数 $\le 100$
• $100\le$ 每种蛋糕的卡路里 $\le 1000$

题解

本题可以转化为一个完全背包问题。我们可以将蛋糕店提供的各种口味蛋糕看作物品,每种蛋糕的卡路里看作物品的重量,LYA 希望的总卡路里范围看作背包的容量范围。

定义 $dp[i]$ 表示总卡路里恰好为 $i$ 的方案数。初始时 $dp=1$,表示不选任何蛋糕的方案数为 $1$。

对于每种蛋糕,我们可以选择任意多个。因此,对于第 $j$ 种蛋糕,我们可以从 $i=cal[j]$ 开始更新 $dp$ 数组:

$$dp[i]=dp[i]+dp[i-cal[j]]$$

其中 $cal[j]$ 表示第 $j$ 种蛋糕的卡路里。

最后,将 $dp[low]$ 到 $dp[high]$ 的值累加起来,就得到了 LYA 的选择方案数。

时间复杂度 $O(n\times high)$,空间复杂度 $O(high)$。其中 $n$ 为蛋糕种类数,$high$ 为总卡路里上限。

参考代码

• Python

low, high = map(int, input().split())
cal = list(map(int, input().split()))dp = [0] * (high + 1)
dp[0] = 1for c in cal:for i in range(c, high + 1):dp[i] += dp[i - c]print(sum(dp[low:high+1]))

• Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int low = sc.nextInt();int high = sc.nextInt();int n = 0;while (sc.hasNextInt()) {n++;sc.nextInt();}int[] cal = new int[n];for (int i = 0; i < n; i++) {cal[i] = sc.nextInt();}long[] dp = new long[high + 1];dp[0] = 1;for (int c : cal) {for (int i = c; i <= high; i++) {dp[i] += dp[i - c];}}long ans = 0;for (int i = low; i <= high; i++) {ans += dp[i];}System.out.println(ans);}
}

• Cpp

#include <iostream>
#include <vector>
using namespace std;int main() {int low, high;cin >> low >> high;vector<int> cal;int c;while (cin >> c) {cal.push_back(c);}vector<long long> dp(high + 1, 0);dp[0] = 1;for (int c : cal) {for (int i = c; i <= high; i++) {dp[i] += dp[i - c];}}long long ans = 0;for (int i = low; i <= high; i++) {ans += dp[i];}cout << ans << endl;return 0;
}

写在最后

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