首页 > 美团笔试20201101
头像
zhouqiaor
编辑于 2020-11-01 21:31
+ 关注

美团笔试20201101

1. 字符串解密

题目描述

对原字符串S增加前缀、后缀字符串进行加密得到加密字符串T,前缀、后缀字符串都包含MT子字符串,并且前缀必须以T结尾,后缀必须以M开始。

现输入T,求最长的原字符串S。

输入说明:第1行为加密字符串T的长度;第2行为加密字符串T。

解题思路

前后指针法

  1. 前指针i从头向后遍历,如果当前字符为T并且指针前的字符串T[:i]包含M,则T[:i]为前缀,i+1为原字符串S的初始位置;

  2. 后指针从尾向前遍历,同理可得后缀和原字符串S的结束位置;

时间复杂度:O(N)

空间复杂度:O(1)
# 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)

空间复杂度: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个节点的树数据结构,小美、小团分别在两个位置,每个回合可以选择移动或不动,小美最快需要几个回合才能追到小团。

解题思路

题目理解:题目没有指明是否为二叉树,两人在节点中双向移动,可把树数据作为图数据?

转化数据结构?

分三种情况:

  1. 小团在小美节点的子树上,小美向下追,小团被堵在死胡同里;

  2. 小团在小美节点的母树上,小团向其它子树逃,小美在后追;

  3. 小团和小美分别在不同子树上。

# 未完成
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)



全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐