3月7日饿了么后端暑期实习笔试~思路分享
关注我：二仙桥耐笔王 ， 强力1v1辅导暑期实习&春招笔试
第1题-小红的字符串
题目内容
小红了一个串
。她将进行恰好一次以下操 作:
选择下标，交换
和
。
小红想知道，不同的操作方案，最终能生成多少不同的字符串?
输入描述
一个仅由和
构成的字符串。字符串长度不小于
,不大于
。
输出描述
一个整数，代表最终的方案数。
样例1
输入
1100
输出
5
思维。统计字符串中x个'0'和y个'1'答案为x*y加上当cnt0>1或cnt1>1时额外的1
s = input().strip()
s0 = s.count('0')
s1 = s.count('1')
res = s0*s1
if s0>=2 or s1>=2:
res += 1
print(res)
第2题-小红的验证码
题目内容
小红是一个程序员，他正在开发一个验证码功能。为了正确识别机器人和真实用户，小红需要对验证码进行特殊处理。
他想出来了如下加密法:
图像+数字识别法，在一张图片中放入一个数字，例如：
这张图片机器人会识别数字 ，但是正确的识别码为
。 给出所有的数字摆放形态:
系统将会在?处随机填入的数字，然后给出
个图片，为
，你需要按照1~m的顺序输出这
个数字以正确识别小红的系统。
输入描述
第一行一个整数，表示图片个数。
接下来共行，每行
列，表示给定的图片。输入保证仅含
和 #。
输出描述
一个整数，表示图片所所表示的正确验证码。
样例1
输入
1
#222#
#2###
#232#
###2#
#272#
输出
5
样例2
输入
2
#222#
#2###
#232#
###2#
#272#
##1##
##1##
##1##
##1##
##1##
输出
51
模拟。直接按照9种不同的数字模块模拟即可
import sys
digitPatterns = [
[
"#...#",
"#.#.#",
"#.#.#",
"#.#.#",
"#...#"
],
[
"##.##",
"##.##",
"##.##",
"##.##",
"##.##"
],
[
"#...#",
"###.#",
"#...#",
"#.###",
"#...#"
],
[
"#...#",
"###.#",
"#...#",
"###.#",
"#...#"
],
[
"#.#.#",
"#.#.#",
"#...#",
"###.#",
"###.#"
],
[
"#...#",
"#.###",
"#...#",
"###.#",
"#...#"
],
[
"#...#",
"#.###",
"#...#",
"#.#.#",
"#...#"
],
[
"#...#",
"###.#",
"###.#",
"###.#",
"###.#"
],
[
"#...#",
"#.#.#",
"#...#",
"#.#.#",
"#...#"
],
[
"#...#",
"#.#.#",
"#...#",
"###.#",
"#...#"
]
]
m = sys.stdin.readline().strip('/n')
m = int(m)
inp = []
for _ in range(int(m)):
inp.append([sys.stdin.readline().strip('/n') for _ in range(5)])
for i in range(m):
for j in range(5):
st = ""
for k in range(5):
if inp[i][j][k] != "#":
st += "."
else:
st += "#"
inp[i][j] = st
ans = []
for i in range(m):
for j in range(10):
jud = True
for k in range(5):
if inp[i][k] != digitPatterns[j][k]:
jud = False
break
if jud:
ans.append(str(j))
break
print("".join(ans))
第3题-小红玩游戏
题目内容
小红最近想到了一个好玩的游戏，这个游戏一共会进行轮，每一轮，小红会从下方三种操作中选择一种进行:
在黑板上写一个整数; 擦去黑板上的一个整数
(此操作之前保证黑板上有这个整数); 询问黑板上哪个数字与整数
的异或值最大(若黑板上此时没有数字，则输出
)。 对于每一次询问操作，你需要告诉他答案。
输入描述
第一行输入一个正整数代表操作的轮数。
此后几行，每行先输入一个整数代表操作类型，编号同题干;随后在同一行输入一个整数
代表操作的参数。
除此之外，保证存在至少一次询问操作。
输出描述
对于每一次询问操作，输出一个整数，代表答案。
样例1
输入
10
1 5
1 7
1 4
3 8
2 4
1 2
1 6
3 9
2 6
3 9
输出
15
15
14
题解
题面描述
题目给定一个游戏，共进行 轮操作。每一轮操作中可以选择以下三种之一：
- 插入操作：在黑板上写入一个整数
；
- 删除操作：擦去黑板上一个整数
- 询问操作：查询黑板上哪个数字与给定整数
。
题目保证至少存在一次询问操作。
字典树。字典树模版题，三种不同的操作对应字典树的插入，删除，查找最大异或值
# 定义字典树节点类
class TrieNode:
def __init__(self):
self.child = [None, None] # 两个分支，分别代表 0 和 1
self.cnt = 0 # 经过该节点的数字个数
# 插入数字 x 到字典树中
def insert(root, x):
node = root
node.cnt += 1
# 固定使用 32 位（或 31 位，根据题目数字范围；这里用 32 位保证万无一失）
for i in range(31, -1, -1):
bit = (x >> i) & 1
if node.child[bit] is None:
node.child[bit] = TrieNode()
node = node.child[bit]
node.cnt += 1
# 删除数字 x 从字典树中（保证 x 存在）
def remove(root, x):
node = root
node.cnt -= 1
for i in range(31, -1, -1):
bit = (x >> i) & 1
node = node.child[bit]
node.cnt -= 1
# 查询给定 x 与字典树中数字异或值的最大值
def query(root, x):
# 如果黑板（字典树）为空，则返回 -1
if root.cnt == 0:
return -1
node = root
res = 0
for i in range(31, -1, -1):
bit = (x >> i) & 1
opp = 1 - bit # 优先选择相反的位
if node.child[opp] is not None and node.child[opp].cnt > 0:
res |= (1 << i)
node = node.child[opp]
else:
node = node.child[bit]
return res
if __name__ == '__main__':
# import sys
# input = sys.stdin.readline
n = int(input().strip())
root = TrieNode()
for _ in range(n):
parts = input().split()
op = int(parts[0])
x = int(parts[1])
if op == 1:
insert(root, x)
elif op == 2:
remove(root, x)
elif op == 3:
print(query(root, x))
查看14道真题和解析