2025.3.7 餓了么筆試（個人整理，僅供參考）
筆試時間：2025年3月7日 春招實(shí)習(xí)
第一題
題目：小紅的字符串
小紅拿到了一個01串s。
她將進(jìn)行恰好一次以下操 作:選擇下標(biāo)i,j(i≠j)，交換si和sj。
小紅想知道，不同的操作方案，最終能生成多少不 同的字符串？
輸入描述
一個僅由'0'和"1'構(gòu)成的字符串。字符串長度不小于2，不大于200000。
輸出描述
一個整數(shù)，代表最終的方案數(shù)。
樣例輸入
1100
樣例輸出
5
說明：
共有以下5種不同字符串:
交換第一個和第二個字符，形成1100
交換第二個和第三個字符，形成1010
交換第二個和第四個字符，形成1001
交換第一個和第三個字符，形成0110
交換第一個和第四個字符，形成0101
答案
import java.util.Scanner;
/**
* 本題思路：所有的交換分為兩種：相同數(shù)字的交換 和 不同的數(shù)字交換
* 1.相同數(shù)字的交換：只有1種結(jié)果，即為輸入的字符串本身
* 2.不同的數(shù)字交換：只有不同的數(shù)字交換才能產(chǎn)生新結(jié)果，1和0交換 與 0和1交換 是一樣的，只需計算一種，
* 把每個1交換到每個0的位置即可，統(tǒng)計count0和count1，相乘即為結(jié)果
* 特例：00 和 11，結(jié)果為1（交換一次也還是本身，可以并入通用計算邏輯）
* 01 和 10，結(jié)果為1（因為題目說了，必須交換一次，不能包含本身的情況）
*/
public class elemeT1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
if ("01".equals(s) || "10".equals(s)) {
System.out.println(1);
}
long count_0 = 0, count_1 = 0;
for (char c : s.toCharArray()) {
if (c == '0') {
count_0++;
} else {
count_1++;
}
}
System.out.println(count_0 * count_1 + 1L);
scanner.close();
}
}
第二題
題目：小紅的驗證碼
小紅是一個程序員，他正在開發(fā)一個驗證碼功能。
為了正確識別機(jī)器人和真實(shí)用戶，小紅需要對驗證碼進(jìn)行特殊處理。
他想出來了如下加密法:圖像+數(shù)字識別法，在一張5x5圖片中放入一個數(shù)字，例如:
#222#
#2###
#232#
###2#
#272#
這張圖片機(jī)器人會識別數(shù)字 22222322272，但是正確的識別碼為 5。 給出所有的數(shù)字?jǐn)[放形態(tài)：
系統(tǒng)將會在?處隨機(jī)填入[0,9]的數(shù)字，然后給出m個圖片，為 pitcurei(1<=i<=m)，你需要按照1~m的順序輸出這 m 個數(shù)字以正確識別小紅的系統(tǒng)。
輸入描述
第一行一個整數(shù) m(1<m<1000)，表示圖片個數(shù)。接下來共 m*5行，每行5列，表示給定的圖片。輸入保證僅含 [0,9] 和 #。
輸出描述
一個整數(shù)，表示圖片所所表示的正確驗證碼。
樣例輸入一
1
#222#
#2###
#232#
###2#
#272#
樣例輸出一
5
樣例輸入二
2
#222#
#2###
#232#
###2#
#272#
##1##
##1##
##1##
##1##
##1##
樣例輸出二
51
答案
import java.util.*;
/**
* 本題思路：模擬，構(gòu)建所有情況的哈希表，方便之后快速查找
* 每次讀入5行，把其中所有數(shù)字替換為0
*/
public class elemeT2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
scanner.nextLine();
Map<List<String>, Integer> map = new HashMap<>();
map.put(Arrays.asList("#000#", "#0#0#", "#0#0#", "#0#0#", "#000#"), 0);
map.put(Arrays.asList("##0##", "##0##", "##0##", "##0##", "##0##"), 1);
map.put(Arrays.asList("#000#", "###0#", "#000#", "#0###", "#000#"), 2);
map.put(Arrays.asList("#000#", "###0#", "#000#", "###0#", "#000#"), 3);
map.put(Arrays.asList("#0#0#", "#0#0#", "#000#", "###0#", "###0#"), 4);
map.put(Arrays.asList("#000#", "#0###", "#000#", "###0#", "#000#"), 5);
map.put(Arrays.asList("#000#", "#0###", "#000#", "#0#0#", "#000#"), 6);
map.put(Arrays.asList("#000#", "###0#", "###0#", "###0#", "###0#"), 7);
map.put(Arrays.asList("#000#", "#0#0#", "#000#", "#0#0#", "#000#"), 8);
map.put(Arrays.asList("#000#", "#0#0#", "#000#", "###0#", "#000#"), 9);
StringBuilder ans = new StringBuilder();
for (int i = 0; i < n; i++) {
List<String> matrix = new ArrayList<>(5);
for (int j = 0; j < 5; j++) { // 處理每一行
StringBuilder stringBuilder = new StringBuilder(scanner.nextLine());
for (int k = 0; k < 5; k++) { // 處理每個數(shù)字
if (Character.isDigit(stringBuilder.charAt(k))) {
stringBuilder.setCharAt(k, '0');
}
}
matrix.add(stringBuilder.toString());
}
ans.append(map.get(matrix));
}
System.out.println(ans);
}
}
第三題
==可參考力扣208 421 1707==
題目：小紅玩游戲
小紅最近想到了一個好玩的游戲，這個游戲一共會進(jìn)行 輪，每一輪，小紅會從下方三種操作中選擇一種進(jìn)行：
在黑板上寫一個整數(shù)
；擦去黑板上的一個整數(shù)（此操作之前保證黑板上有這個整數(shù)）；詢問黑板上哪個數(shù)字與整數(shù)的異
或值最大（若黑板上此時沒有數(shù)字，則輸出
)。對于每一次詢問操作，你需要告訴他答案。
輸入描述
第一行輸入一個正整數(shù)代表操作的輪數(shù)。
此后幾行，每行先輸入一個整數(shù)
代表操作類型，編號同題干；隨后在同一行輸入一個整數(shù)
代表操作的參數(shù)。
除此之外，保證存在至少一次詢問操作。
輸出描述
對于每一次詢問操作，輸出一個整數(shù)，代表答案。
樣例輸入一
6
1 5
1 8
3 2
2 5
3 2
3 8
樣例輸出一
10
10
0
樣例輸入二
10
1 5
1 7
1 4
3 8
2 4
1 2
1 6
3 9
2 6
3 9
樣例輸出二
15
15
14
解題思路
這道題的關(guān)鍵在于高效地實(shí)現(xiàn)“最大異或值查詢”操作。我們可以使用 Trie（字典樹） 這一數(shù)據(jù)結(jié)構(gòu)來快速查詢集合中與某個數(shù)字的最大異或值。
- 使用 Trie 存儲數(shù)字的二進(jìn)制表示
- 由于
1 ≤ x ≤ 10^9，它的二進(jìn)制表示最多為 30 位（2^30 > 10^9）。 - 在 Trie 中，每個數(shù)字以 01二進(jìn)制形式 插入或刪除。
- 由于
- 插入數(shù)字
- 從 最高位（第 29 位）開始插入，保證樹的深度不超過 30。
- 刪除數(shù)字
- 在 Trie 中維護(hù)一個計數(shù)器（
count），僅當(dāng)count == 0時真正刪除該節(jié)點(diǎn)。
- 在 Trie 中維護(hù)一個計數(shù)器（
- 查詢最大異或值
- 在 Trie 中，從最高位開始，盡量選擇能夠使異或值最大的路徑（即選擇
1 - bit）。
- 在 Trie 中，從最高位開始，盡量選擇能夠使異或值最大的路徑（即選擇
答案
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class TrieNode {
Map<Integer, TrieNode> children = new HashMap<>();
int count = 0; // 記錄當(dāng)前數(shù)字在Trie中的個數(shù)
}
public class elemeT3 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
int op = scanner.nextInt(), num = scanner.nextInt();
if (op == 1) {
insert(num);
} else if (op == 2) {
remove(num);
} else if (op == 3) {
System.out.println(query(num));
}
}
scanner.close();
}
static TrieNode root = new TrieNode();
// 插入數(shù)字到Trie
public static void insert(int num) {
TrieNode node = root;
for (int i = 29; i >= 0; i--) { // 遍歷30位二進(jìn)制
int bit = (num >> i) & 1;
node.children.putIfAbsent(bit, new TrieNode());
node = node.children.get(bit);
node.count++;
}
}
// 從Trie中刪除數(shù)字
public static void remove(int num) {
TrieNode node = root;
for (int i = 29; i >= 0; i--) {
int bit = (num >> i) & 1;
node = node.children.get(bit);
node.count--;
if (node.count == 0) { // 當(dāng)計數(shù)為0時，刪除該路徑
node.children.remove(bit);
break;
}
}
}
// 查詢與 num 最大異或值
public static int query(int num) {
TrieNode node = root;
if (node.children.isEmpty()) { // Trie為空，返回-1
return -1;
}
int maxXor = 0;
for (int i = 29; i >= 0; i--) {
int bit = (num >> i) & 1;
int oppositeBit = 1 - bit; // 取相反的bit以獲得最大異或值
if (node.children.containsKey(oppositeBit) && node.children.get(oppositeBit).count > 0) {
maxXor |= (1 << i); // 該位為1，異或值增大
node = node.children.get(oppositeBit);
} else {
node = node.children.get(bit); // 只能走當(dāng)前bit方向
}
}
return maxXor;
}
}
科大訊飛公司氛圍 250人發(fā)布
查看9道真題和解析