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

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

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

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

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

🧷 01.K小姐的生日派對

問題描述

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

輸入格式

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

輸出格式

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

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

樣例輸入

1,2,3,2,2

樣例輸出

2

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

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

題解

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

具體步驟如下:

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

時間復(fù)雜度為 $O(n)$,其中 $n$ 為朋友總數(shù)?？臻g復(fù)雜度為 $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 決定采用一種特殊的方式:當(dāng)一位同事收到邀請函后,如果 TA 所在的部門在允許傳遞的部門列表中,就將邀請函傳遞給周圍(上、下、左、右)的同事;否則,就不再傳遞。

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

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

輸入格式

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

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

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

最后一行包含若干個整數(shù),表示允許傳遞邀請函的部門列表,整數(shù)之間用空格隔開。

輸出格式

輸出一個整數(shù),表示最終收到邀請函的人數(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$ 部門編號 $\le 50$
• $0\le x<n$
• $0\le y<m$
• $1\le$ 允許傳遞的部門數(shù)量 $\le 50$

題解

本題可以使用 BFS 算法求解。從 LYA 的工位開始,將邀請函傳遞給周圍的同事,如果這些同事所在的部門允許傳遞邀請函,就將他們加入隊列中,并標(biāo)記為已訪問。不斷從隊列中取出同事,重復(fù)上述過程,直到隊列為空。最終訪問過的同事數(shù)量就是收到邀請函的人數(shù)。

具體步驟如下:

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

時間復(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 的生日蛋糕訂購

問題描述

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

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

注意:

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

輸入格式

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

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

輸出格式

輸出一個整數(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)化為一個完全背包問題。我們可以將蛋糕店提供的各種口味蛋糕看作物品,每種蛋糕的卡路里看作物品的重量,LYA 希望的總卡路里范圍看作背包的容量范圍。

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

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

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

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

最后,將 $dp[low]$ 到 $dp[high]$ 的值累加起來,就得到了 LYA 的選擇方案數(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;
}

寫在最后

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