🍭 大家好這里是KK愛(ài)Coding ，一枚熱愛(ài)算法的程序員

? 本系列打算持續(xù)跟新華為近期的春秋招筆試題匯總～

💻 ACM銀牌🥈| 多次AK大廠筆試 ｜ 編程一對(duì)一輔導(dǎo)

👏 感謝大家的訂閱? 和 喜歡💗

📧 KK這邊最近正在收集近一年互聯(lián)網(wǎng)各廠的筆試題匯總，如果有需要的小伙伴可以關(guān)注后私信一下 KK領(lǐng)取，會(huì)在飛書(shū)進(jìn)行同步的跟新。

🧷 01.K小姐的生日派對(duì)

問(wèn)題描述

K小姐即將迎來(lái)自己的生日,為了慶祝這一天,她邀請(qǐng)了許多朋友來(lái)參加生日派對(duì)。派對(duì)結(jié)束后,K小姐發(fā)現(xiàn)有一位朋友在派對(duì)上出現(xiàn)的次數(shù)超過(guò)了所有朋友總出現(xiàn)次數(shù)的一半。K小姐很想知道這位朋友是誰(shuí),你能幫助她找出這位神秘朋友嗎?

輸入格式

輸入包含一行,為一個(gè)以逗號(hào)分隔的正整數(shù)列表,表示每位朋友的編號(hào)。編號(hào)范圍為 $1$ 到 $100000$,朋友總數(shù)不超過(guò) $1000$。

輸出格式

輸出一個(gè)整數(shù),表示出現(xiàn)次數(shù)超過(guò)總出現(xiàn)次數(shù)一半的朋友編號(hào)。如果不存在這樣的朋友,則輸出 $0$。

當(dāng)朋友總數(shù)為偶數(shù) $n$ 時(shí),超過(guò)總數(shù)一半意味著出現(xiàn)次數(shù)大于 $\frac{n}{2}$;當(dāng)朋友總數(shù)為奇數(shù) $n$ 時(shí),超過(guò)總數(shù)一半意味著出現(xiàn)次數(shù)大于 $\frac{n+1}{2}$。

樣例輸入

1,2,3,2,2

樣例輸出

2

數(shù)據(jù)范圍

• $1\le$ 朋友編號(hào) $\le 100000$
• $1<$ 朋友總數(shù) $<1000$

題解

本題可以使用模擬的方法求解。我們可以用一個(gè)數(shù)組 $cnt$ 來(lái)記錄每個(gè)朋友出現(xiàn)的次數(shù),然后遍歷這個(gè)數(shù)組,判斷是否存在出現(xiàn)次數(shù)超過(guò)總出現(xiàn)次數(shù)一半的朋友。

具體步驟如下:

1. 初始化一個(gè)長(zhǎng)度為 $100001$ 的數(shù)組 $cnt$,用于記錄每個(gè)朋友出現(xiàn)的次數(shù)。
2. 讀入朋友編號(hào)序列,對(duì)于每個(gè)編號(hào) $x$,將 $cnt[x]$ 的值加 $1$,同時(shí)累加朋友總數(shù) $total$。
3. 計(jì)算出現(xiàn)次數(shù)的臨界值 $half$,即 $?\frac{total}{2}?$。
4. 遍歷數(shù)組 $cnt$,判斷是否存在某個(gè)元素的值大于 $half$,如果存在則輸出對(duì)應(yīng)的朋友編號(hào),否則輸出 $0$。

時(shí)間復(fù)雜度為 $O(n)$,其中 $n$ 為朋友總數(shù)。空間復(fù)雜度為 $O(m)$,其中 $m$ 為朋友編號(hào)的范圍。

參考代碼

• 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 的生日派對(duì)邀請(qǐng)函傳遞

問(wèn)題描述

LYA 正在籌備自己的生日派對(duì),她邀請(qǐng)了公司里的許多同事。為了方便傳遞邀請(qǐng)函,LYA 決定采用一種特殊的方式:當(dāng)一位同事收到邀請(qǐng)函后,如果 TA 所在的部門(mén)在允許傳遞的部門(mén)列表中,就將邀請(qǐng)函傳遞給周?chē)?上、下、左、右)的同事;否則,就不再傳遞。

公司的辦公室可以看作一個(gè) $n\times m$ 的網(wǎng)格,每個(gè)格子代表一個(gè)工位。LYA 的工位位于 $(x,y)$,她會(huì)在這里開(kāi)始傳遞邀請(qǐng)函。

給定辦公室的布局、LYA 的工位坐標(biāo)以及允許傳遞邀請(qǐng)函的部門(mén)列表,請(qǐng)問(wèn)最終會(huì)有多少人收到邀請(qǐng)函?

輸入格式

第一行包含兩個(gè)整數(shù) $n$ 和 $m$,表示辦公室的行數(shù)和列數(shù)。

接下來(lái) $n$ 行,每行包含 $m$ 個(gè)整數(shù),表示辦公室的布局。每個(gè)整數(shù)代表該位置上同事所在的部門(mén)編號(hào)。

再接下來(lái)一行包含兩個(gè)整數(shù) $x$ 和 $y$,表示 LYA 的工位坐標(biāo)。

最后一行包含若干個(gè)整數(shù),表示允許傳遞邀請(qǐng)函的部門(mén)列表,整數(shù)之間用空格隔開(kāi)。

輸出格式

輸出一個(gè)整數(shù),表示最終收到邀請(qǐng)函的人數(shù)。

樣例輸入

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

數(shù)據(jù)范圍

• $1\le n,m\le 1000$
• $1\le$ 部門(mén)編號(hào) $\le 50$
• $0\le x<n$
• $0\le y<m$
• $1\le$ 允許傳遞的部門(mén)數(shù)量 $\le 50$

題解

本題可以使用 BFS 算法求解。從 LYA 的工位開(kāi)始,將邀請(qǐng)函傳遞給周?chē)耐?如果這些同事所在的部門(mén)允許傳遞邀請(qǐng)函,就將他們加入隊(duì)列中,并標(biāo)記為已訪問(wèn)。不斷從隊(duì)列中取出同事,重復(fù)上述過(guò)程,直到隊(duì)列為空。最終訪問(wèn)過(guò)的同事數(shù)量就是收到邀請(qǐng)函的人數(shù)。

具體步驟如下:

1. 使用二維數(shù)組 $grid$ 存儲(chǔ)辦公室的布局,$grid[i][j]$ 表示位置 $(i,j)$ 上同事所在的部門(mén)編號(hào)。
2. 使用集合 $allowed$ 存儲(chǔ)允許傳遞邀請(qǐng)函的部門(mén)列表。
3. 使用二維數(shù)組 $vis$ 標(biāo)記每個(gè)位置是否被訪問(wèn)過(guò),初始時(shí)除了 LYA 的工位外,其余位置都未被訪問(wèn)。
4. 創(chuàng)建一個(gè)隊(duì)列 $q$,將 LYA 的工位坐標(biāo) $(x,y)$ 加入隊(duì)列,并標(biāo)記為已訪問(wèn)。
5. 初始化答案 $ans=0$,表示收到邀請(qǐng)函的人數(shù)。
6. 當(dāng)隊(duì)列不為空時(shí),重復(fù)以下步驟:
   • 從隊(duì)列中取出一個(gè)位置 $(i,j)$。
   • 枚舉 $(i,j)$ 的四個(gè)相鄰位置 $(ni,nj)$:
     • 如果 $(ni,nj)$ 在網(wǎng)格范圍內(nèi),且未被訪問(wèn)過(guò),且 $grid[ni][nj]$ 在 $allowed$ 中,則將 $(ni,nj)$ 加入隊(duì)列,標(biāo)記為已訪問(wèn),并將 $ans$ 加 $1$。
7. 返回答案 $ans$。

時(shí)間復(fù)雜度 $O(nm)$,空間復(fù)雜度 $O(nm)$。其中 $n$ 和 $m$ 分別為辦公室的行數(shù)和列數(shù)。

參考代碼

• 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 的生日蛋糕訂購(gòu)

問(wèn)題描述

LYA 的生日快到了,她打算訂購(gòu)一個(gè)特別的生日蛋糕。蛋糕店提供了若干種口味的蛋糕,每種口味的蛋糕都有對(duì)應(yīng)的卡路里。為了保持身材,LYA 希望蛋糕的總卡路里在一定范圍內(nèi)。

現(xiàn)在給定蛋糕店提供的各種口味蛋糕的卡路里,以及 LYA 希望的總卡路里范圍,請(qǐng)問(wèn) LYA 有多少種選擇方案?

注意:

1. 每種口味的蛋糕可以選擇任意多個(gè)。
2. 不同口味的蛋糕卡路里各不相同。

輸入格式

第一行包含兩個(gè)整數(shù) $low$ 和 $high$,表示 LYA 希望的蛋糕總卡路里的下限和上限。

第二行包含若干個(gè)整數(shù),表示蛋糕店提供的各種口味蛋糕的卡路里,整數(shù)之間用空格隔開(kāi)。

輸出格式

輸出一個(gè)整數(shù),表示 LYA 的選擇方案數(shù)。

樣例輸入

350 500
100 200 500

樣例輸出

7

數(shù)據(jù)范圍

• $1\le low\le 1000$
• $1\le high\le 1000$
• $1\le$ 蛋糕種類數(shù) $\le 100$
• $100\le$ 每種蛋糕的卡路里 $\le 1000$

題解

本題可以轉(zhuǎn)化為一個(gè)完全背包問(wèn)題。我們可以將蛋糕店提供的各種口味蛋糕看作物品,每種蛋糕的卡路里看作物品的重量,LYA 希望的總卡路里范圍看作背包的容量范圍。

定義 $dp[i]$ 表示總卡路里恰好為 $i$ 的方案數(shù)。初始時(shí) $dp=1$,表示不選任何蛋糕的方案數(shù)為 $1$。

對(duì)于每種蛋糕,我們可以選擇任意多個(gè)。因此,對(duì)于第 $j$ 種蛋糕,我們可以從 $i=cal[j]$ 開(kāi)始更新 $dp$ 數(shù)組:

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

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

最后,將 $dp[low]$ 到 $dp[high]$ 的值累加起來(lái),就得到了 LYA 的選擇方案數(shù)。

時(shí)間復(fù)雜度 $O(n\times high)$,空間復(fù)雜度 $O(high)$。其中 $n$ 為蛋糕種類數(shù),$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;
}

寫(xiě)在最后

📧 KK這邊最近正在收集近一年互聯(lián)網(wǎng)各廠的筆試題匯總，如果有需要的小伙伴可以關(guān)注后私信一下 KK領(lǐng)取，會(huì)在飛書(shū)進(jìn)行同步的跟新。