美团笔试20201101
1. 字符串解密
题目描述
对原字符串S增加前缀、后缀字符串进行加密得到加密字符串T，前缀、后缀字符串都包含M和T子字符串，并且前缀必须以T结尾，后缀必须以M开始。
现输入T，求最长的原字符串S。
输入说明：第1行为加密字符串T的长度；第2行为加密字符串T。
解题思路
前后指针法
-
前指针i从头向后遍历，如果当前字符为T并且指针前的字符串T[:i]包含M，则T[:i]为前缀，i+1为原字符串S的初始位置；
-
后指针从尾向前遍历，同理可得后缀和原字符串S的结束位置；
时间复杂度：O(N)
# Accept 100% import sys N = int(sys.stdin.readline().strip()) # 加密后字符串长度 T = sys.stdin.readline().strip() # 加密后字符串T start = None end = None for i in range(N): if T[i] == 'T' and 'M' in T[:i] start = i + 1 break for i in range(N-1, 0, -1): if T[i] == 'M' and 'T' in T[i+1:] end = i break print(T[start:end])
2. 顺序志愿
题目描述
有编号为0-N的N个人填报N个顺序志愿，编号靠前的优先选择。
输入说明：第1行输入N；第2~N+1行依次输入N个人的顺序志愿，空格分隔。
解题思路
遍历每个人的顺序志愿，从编号1开始，如果本志愿还没人选择，则把本志愿安排给此人，否则判断下一志愿。
时间复杂度：O(N)
# Accept 100%
import sys
N = int(sys.stdin.readline().strip())
Selected = set()
ans = []
for i in range(N):
T = list(map(int, sys.stdin.readline().strip().split(' ')))
for t in T:
if t not in Selected:
ans.append(t)
Selected.add(t)
break
print(' '.join(map(str, ans)))
3. 小美树上追小团
题目描述
已知N个节点的树数据结构，小美、小团分别在两个位置，每个回合可以选择移动或不动，小美最快需要几个回合才能追到小团。
解题思路
题目理解：题目没有指明是否为二叉树，两人在节点中双向移动，可把树数据作为图数据？
转化数据结构？
分三种情况：
-
小团在小美节点的子树上，小美向下追，小团被堵在死胡同里；
-
小团在小美节点的母树上，小团向其它子树逃，小美在后追；
-
小团和小美分别在不同子树上。
# 未完成
import sys
from collections import defaultdict
N, a, b = map(int, sys.stdin.readline().strip().split(' '))
T = defaultdict(set)
for i in range(N):
m, n = map(int, sys.stdin.readline().strip().split(' '))
T[m].add(n)
T[n].add(m)
...
... 4. 区间排除，非严格升序
题目描述
给定长度为N的数组，元素大小在区间[0, M]内。现用区间[l, r] (l <= r)剔除数组中的元素，使其非严格升序。求区间[l, r]有多少种情况。
解题思路
暴力遍历求解。
# Accept 64%
import sys
M, N = map(int, sys.stdin.readline().strip().split(' '))
L = list(map(int, sys.stdin.readline().strip().split(' ')))
ans = 0
# All = []
for i in range(1, M+1):
for j in range(i, M+1):
Y = [0]
Can = True
for k in range(len(L)):
if L[k] not in set(range(i, j+1)):
if L[k] >= Y[-1]:
Y.append(L[k])
else:
Can = False
break
if Can:
ans += 1
# All.append([i, j])
print(ans) 5. 旅行商问题
题目描述
给定M组数据：每组数据为无向非全连接图，例如第一组数据有N个地点，已知地点之间是否连接及距离，求每组数据中遍历所有地点的最短距离。 示例输入： 1 5 1 2 1 1 3 4 3 4 2 3 5 3
解题思路
旅行商问题
import sys
M = int(sys.stdin.readline().strip())
for i in range(M):
ans = 0
N = int(sys.stdin.readline().strip())
for j in range(N-1):
A, B, L = map(int, sys.stdin.readline().strip().split(' '))
#...
#未完成
#...
print(ans) 
查看21道真题和解析