2025.3.7 饿了么笔试（个人整理，仅供参考）
笔试时间：2025年3月7日 春招实习
第一题
题目：小红的字符串
小红拿到了一个01串s。
她将进行恰好一次以下操 作:选择下标i,j(i≠j)，交换si和sj。
小红想知道，不同的操作方案，最终能生成多少不 同的字符串？
输入描述
一个仅由'0'和"1'构成的字符串。字符串长度不小于2，不大于200000。
输出描述
一个整数，代表最终的方案数。
样例输入
1100
样例输出
5
说明：
共有以下5种不同字符串:
交换第一个和第二个字符，形成1100
交换第二个和第三个字符，形成1010
交换第二个和第四个字符，形成1001
交换第一个和第三个字符，形成0110
交换第一个和第四个字符，形成0101
答案
import java.util.Scanner;
/**
* 本题思路：所有的交换分为两种：相同数字的交换 和 不同的数字交换
* 1.相同数字的交换：只有1种结果，即为输入的字符串本身
* 2.不同的数字交换：只有不同的数字交换才能产生新结果，1和0交换 与 0和1交换 是一样的，只需计算一种，
* 把每个1交换到每个0的位置即可，统计count0和count1，相乘即为结果
* 特例：00 和 11，结果为1（交换一次也还是本身，可以并入通用计算逻辑）
* 01 和 10，结果为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();
}
}
第二题
题目：小红的验证码
小红是一个程序员，他正在开发一个验证码功能。
为了正确识别机器人和真实用户，小红需要对验证码进行特殊处理。
他想出来了如下加密法:图像+数字识别法，在一张5x5图片中放入一个数字，例如:
#222#
#2###
#232#
###2#
#272#
这张图片机器人会识别数字 22222322272，但是正确的识别码为 5。 给出所有的数字摆放形态：
系统将会在?处随机填入[0,9]的数字，然后给出m个图片，为 pitcurei(1<=i<=m)，你需要按照1~m的顺序输出这 m 个数字以正确识别小红的系统。
输入描述
第一行一个整数 m(1<m<1000)，表示图片个数。接下来共 m*5行，每行5列，表示给定的图片。输入保证仅含 [0,9] 和 #。
输出描述
一个整数，表示图片所所表示的正确验证码。
样例输入一
1
#222#
#2###
#232#
###2#
#272#
样例输出一
5
样例输入二
2
#222#
#2###
#232#
###2#
#272#
##1##
##1##
##1##
##1##
##1##
样例输出二
51
答案
import java.util.*;
/**
* 本题思路：模拟，构建所有情况的哈希表，方便之后快速查找
* 每次读入5行，把其中所有数字替换为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++) { // 处理每个数字
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==
题目：小红玩游戏
小红最近想到了一个好玩的游戏，这个游戏一共会进行 轮，每一轮，小红会从下方三种操作中选择一种进行：
在黑板上写一个整数
；擦去黑板上的一个整数（此操作之前保证黑板上有这个整数）；询问黑板上哪个数字与整数的异
或值最大（若黑板上此时没有数字，则输出
)。对于每一次询问操作，你需要告诉他答案。
输入描述
第一行输入一个正整数代表操作的轮数。
此后几行，每行先输入一个整数
代表操作类型，编号同题干；随后在同一行输入一个整数
代表操作的参数。
除此之外，保证存在至少一次询问操作。
输出描述
对于每一次询问操作，输出一个整数，代表答案。
样例输入一
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
解题思路
这道题的关键在于高效地实现“最大异或值查询”操作。我们可以使用 Trie（字典树） 这一数据结构来快速查询集合中与某个数字的最大异或值。
- 使用 Trie 存储数字的二进制表示
- 由于
1 ≤ x ≤ 10^9，它的二进制表示最多为 30 位（2^30 > 10^9）。 - 在 Trie 中，每个数字以 01二进制形式 插入或删除。
- 由于
- 插入数字
- 从 最高位（第 29 位）开始插入，保证树的深度不超过 30。
- 删除数字
- 在 Trie 中维护一个计数器（
count），仅当count == 0时真正删除该节点。
- 在 Trie 中维护一个计数器（
- 查询最大异或值
- 在 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; // 记录当前数字在Trie中的个数
}
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();
// 插入数字到Trie
public static void insert(int num) {
TrieNode node = root;
for (int i = 29; i >= 0; i--) { // 遍历30位二进制
int bit = (num >> i) & 1;
node.children.putIfAbsent(bit, new TrieNode());
node = node.children.get(bit);
node.count++;
}
}
// 从Trie中删除数字
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) { // 当计数为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); // 只能走当前bit方向
}
}
return maxXor;
}
}
投递饿了么等公司9个岗位 >
查看3道真题和解析