【笔试复盘】3月22日美团暑期实习研发岗笔试三道题
关注我：二仙桥耐笔王 ， 强力1v1辅导暑期实习&春招笔试
第一题-镜像字符串
题目内容
小美有一个长度为的字符串
，她想知道这个字符串有多少个长度大于
的子串是可镜像的。
可镜像的意思是:一个字符串是回文串，且其中每个字符都有垂直对称轴。
[回文串]一个字符串被称作回文串，当且仅当这个字符串从左往右读和从右往左读是相同的。
有垂直对称轴的大写字母:'','
','
', '
', '
', '
', '
','
', '
', '
', '
'。
输入描述
输入一个长度为的字符串
，字符串中仅包含大写字母。
输出描述
输出一个整数，表示字符串中长度大于
的可镜像的子串的数量
样例1
输入
AHHAMTT
输出
3
说明
一共个长度大于
的可镜像的子串:"
","
","
"
题解
题目分析
给定一个长度为的字符串
，要求计算其中有多少个长度大于
的子串是可镜像的。所谓可镜像子串，满足以下两个条件：
- 回文串：从左到右和从右到左的顺序相同。
- 垂直对称轴的字符：每个字符必须是有垂直对称轴的大写字母，具体包括'A', 'H', 'I', 'M', 'O', 'T', 'U', 'V', 'W', 'X', 'Y'。
解题思路
我们可以将问题拆解为以下几个步骤：
- 检查字符是否符合镜像要求：我们可以通过预定义一个集合来快速判断某个字符是否属于镜像字符集合。
- 判断回文：判断一个子串是否是回文串。
- 枚举所有子串：遍历所有长度大于1的子串，逐一判断它们是否满足上述两个条件。如果满足条件，则计数。
代码实现
def check(c):
# 判断字符是否为垂直对称字符
return c in "AHIMOTUVWXY"
def is_palindrome(s):
# 判断字符串是否为回文串
return s == s[::-1]
def count_mirror_substrings(s):
n = len(s)
count = 0
# 枚举所有长度大于1的子串
for i in range(n):
for j in range(i+1, n):
sub = s[i:j+1]
# 如果是回文且所有字符都为垂直对称字符
if is_palindrome(sub) and all(check(c) for c in sub):
count += 1
return count
# 输入并输出结果
s = input().strip()
print(count_mirror_substrings(s))
第二题-小美的中位数
题目内容
众所周知，一个长度为，
为奇数的数组的中位数是其排序后下标为
的数字。
但小美发现，有些长为奇数n的数组即使不排序，其下标为的数字依然是其数组中位数，他将满足这样性质的数组成为“好数组"。
现在小美有一个长度为的排列
，他想知道
中有多少个连续的区间组成的数组都是"好数组"。
(即有多少对,同时
是奇数,满足
是一个好数组。)
输入描述
每个测试文件内都包含多组测试数据。
第一行一个正整数，表示测试数据的组数。
接下来对于每组测试数据，输入包含两行。
第一行两个整数，表示排列
的长度。
第二行个整数
，表示排列
。
(保证输入是一个排列。)
(保证所有测试数据中的总和不超过
)
输出描述
输出包含 行，每行一个正整数，表示合法的
对数。
样例1
输入
1
5
3 2 1 4 5
输出
7
说明
好数组的区间有:
,
,
,
,
,
,
这
个。
题解
问题分析
本题要求我们找到一个排列 p 中的所有“好数组”区间的个数。具体来说，给定一个排列 p 和多个查询，每个查询包含一个长度为奇数的区间 [l, r]，并要求判断区间内的中位数是否满足“好数组”的条件：该区间的中位数恰好是区间的第 (r - l + 1) // 2 + 1 的位置上的数字，并且此中位数在该区间内不需要进行排序后也符合中位数的定义。
“好数组”的定义
“好数组”要求数组的中位数即为该区间的第 (n + 1) / 2 个元素（即中间元素）。例如，若数组的长度为 5，那么第 3 个元素就是中位数。
解题思路
-
中位数的定义： 对于一个长度为奇数的子数组，数组的中位数是该数组排序后位于中间位置的元素。例如，对于长度为 5 的子数组
p[l..r]，它的中位数就是p[(l+r)//2]。 -
“好数组”区间的判断： 对于每个子区间，我们需要检查其是否是“好数组”。根据题目要求，找到所有长度为奇数的子数组，并且要判断这个子数组的中位数是否符合要求。
-
解法思路： 我们从每一个元素出发，尝试扩大窗口，检查窗口内的中位数是否符合“好数组”的要求。具体步骤如下：
- 对每一个可能的子数组，检查其是否为好数组。
- 具体做法是对于每一个中位数，判断其是否满足条件，并用双指针的方式，计算所有符合条件的区间。
代码实现
def solve():
t = int(input())
for _ in range(t):
n = int(input())
p = list(map(int, input().split()))
result = 0
for i in range(n):
d = 0
total = 0
for k in range(1, min(i, n -1 - i) + 1):
left = i - k
right = i + k
total += 1 if p[left] > p[i] else -1
total += 1 if p[right] > p[i] else -1
if total == 0:
d += 1
result += d + 1
print(result)
# 输入调用
solve()
第三题-小美的青蛙跳跃
题目内容
小美有一个一维的坐标系，上面一共有个点，依次为
，她有一只遥控青蛙，初始时位于
。现在，她在纸上书写了一个指令集:
- 指令
:指挥青蛙向左移动一个单位，如果当前位于
，则原地不动。
- 指令
:指挥青蛙向右移动一个单位，如果当前位于
，则原地不动。
- 指令
:未知，随机变成
对于指令的全部可能取值，小美想知道青蛙最终有概率停在哪些位置。如果该点可能成为终点，输出
，否则输出
输入描述
第一行输入两个整数分别表示坐标系长度和青娃的初始位置。
第二行输入一个长度不超过且仅由
和
构成的字符串
，表示移动的指令集。
输出描述
在一行上输出 个数字
代表
每一个点是否可能成为青蛙的终点，数字之间不必使用空格隔开。
样例1
输入
3 2
RL?
输出
101
说明
青蛙会先向右一格到达，随后向左一格回到
；由于第三个指令是
，小红有可能指挥青蛙向左到达1，也有可能向右到达
。
样例2
输入
5 2
?????
输出
11111
题解
解题思路
考虑到指令"?"可以是L或R，如果有多个"?"指令，我们需要考虑这些指令所有可能的组合。直接枚举所有可能性会导致指数级复杂度，这对于长度达10^6的指令序列是不可行的。
我发现可以用一种更高效的方法：跟踪青蛙可能到达的位置范围。具体来说，维护两个范围：
- 外部范围(
left到right)：表示青蛙一定可以到达的区域边界 - 内部范围(
inner_left到inner_right)：表示一个特殊区域，在这个区域内的位置按照特定模式（交替的0和1）可达
当遇到不同指令时：
- L指令：整体向左移动
- R指令：整体向右移动
- ?指令：结合L和R的效果，扩展可能位置的范围
算法复杂度
- 时间复杂度：O(|S|)，其中|S|是指令字符串的长度。我们只需遍历一次指令串。
- 空间复杂度：O(1)，只使用了常数级额外空间。
代码实现
class Move:
def __init__(self, idx=None):
if idx is not None:
# 初始化单一位置
self.left = self.right = idx
self.inner_left = self.inner_right = -1 # -1表示没有内部范围
else:
self.left = self.right = 0
self.inner_left = self.inner_right = -1
# 处理L指令：向左移动
def move_left(self):
res = Move()
# 更新外部范围
res.left = max(self.left - 1, 0)
res.right = max(self.right - 1, 0)
# 更新内部范围
if self.inner_left != -1:
if self.inner_left - 1 == 0:
# 处理内部左边界
res.inner_left = self.inner_left + 1
res.inner_right = self.inner_right - 1
if res.inner_left > res.inner_right:
res.inner_left = res.inner_right = -1
else:
# 整体左移
res.inner_left = self.inner_left - 1
res.inner_right = self.inner_right - 1
return res
# 处理R指令：向右移动
def move_right(self):
res = Move()
# 更新外部范围
res.left = min(self.left + 1, n - 1)
res.right = min(self.right + 1, n - 1)
# 更新内部范围
if self.inner_left != -1:
if self.inner_right + 1 == n - 1:
# 处理内部右边界
res.inner_left = self.inner_left + 1
res.inner_right = self.inner_right - 1
if res.inner_left > res.inner_right:
res.inner_left = res.inner_right = -1
else:
# 整体右移
res.inner_left = self.inner_left + 1
res.inner_right = self.inner_right + 1
return res
# 处理?指令：同时考虑左移和右移
def move_random(self):
res = Move()
# 更新外部范围（扩大范围）
res.left = max(self.left - 1, 0)
res.right = min(self.right + 1, n - 1)
# 更新内部范围
if self.inner_left != -1:
# 左边界处理
if self.left + 1 == self.inner_left and self.left != 0:
res.inner_left = self.inner_left - 1
else:
res.inner_left = self.inner_left + 1
# 右边界处理
if self.right - 1 == self.inner_right and self.right != n - 1:
res.inner_right = self.inner_right + 1
else:
res.inner_right = self.inner_right - 1
# 如果内部范围无效，则清除
if res.inner_left > res.inner_right:
res.inner_left = res.inner_right = -1
elif self.left == self.right and self.left > 0 and self.left + 1 < n:
# 创建新的内部范围
res.inner_left = res.inner_right = self.left
return res
# 读取输入
n, k = map(int, input().split())
s = input().strip()
# 初始化，青蛙在位置k
f = Move(k - 1) # 转为0-indexed
# 处理每条指令
for c in s:
if c == 'L':
f = f.move_left()
elif c == 'R':
f = f.move_right()
else: # c == '?'
f = f.move_random()
# 生成结果
result = ""
for i in range(n):
if f.inner_left <= i <= f.inner_right:
# 内部范围：交替输出0和1
result += str((i - f.inner_left) % 2)
elif f.left <= i <= f.right:
# 外部范围：输出1
result += "1"
else:
# 其他位置：输出0
result += "0"
print(result)
投递美团等公司6个岗位 >
查看3道真题和解析