首页 > 8.29 美团笔试 算法(1, 1, 0.91, 1)
头像
lih627
编辑于 2020-08-29 18:19
+ 关注

8.29 美团笔试 算法(1, 1, 0.91, 1)

过了三道,有一道不知为什么

另外求内推,好多公司还没有投,秋招算法太难了。。。

下面是题解:

第一题 100%:
因此在某些明文的传输中会使用一种加密策略,小团如果需要传输一个字符串 S,
则他会为这个字符串添加一个头部字符串和一个尾部字符串。头部字符串满足至少包含一个 “MT” 子序列,且以 T 结尾。
尾部字符串需要满足至少包含一个 “MT” 子序列,且以 M 开头。例如 AAAMT 和 MAAAT 都是一个合法的头部字符串,
而 MTAAA 就不是合法的头部字符串。很显然这样的头尾字符串并不一定是唯一的,因此我们还有一个约束,就是 S 是满足头尾字符串合法的情况下的最长的字符串。 
代码
def solve(n, s):
    l, r = 0, n - 1
    while s[l] != 'M':
        l += 1
    l += 1
    while s[l] != 'T':
        l += 1
    l += 1
    while s[r] != 'T':
        r -= 1
    r -= 1
    while s[r] != 'M':
        r -= 1
    r -= 1
    print(s[l: r + 1])


if __name__ == '__main__':
    n = int(input())
    s = input()
    solve(n, s)

第二题 100:

一个分配工作的直接暴力就可以:
代码如下
def solve(n, nums):
    visited = [False] * (n + 1)
    ret = [0] * n
    for idx, cnums in enumerate(nums):
        for k in cnums:
            if not visited[k]:
                ret[idx] = k
                visited[k] = True
                break
    for _ in ret:
        print(_, end=' ')


if __name__ == '__main__':
    n = int(input())
    nums = [0] * n
    for i in range(n):
        nums[i] = list(map(int, input().split()))
    solve(n, nums)

第三题 91
大意是给定n个节点 n-1条边, 是一棵树,有两个人分别在第x和第y个节点,问x追上y的最长时间是多少

思路是:
计算x道所有节点的时间dx, y道所有节点的时间dy
如果`dx[k] >= dy[k]` 那么y可以先跑到k等着被x追上,取满足这个情况的最大的dx
def solve(n, x, y, graph):
    dx = [None] * (n + 1)
    dy = [None] * (n + 1)
    if x == y:
        print(0)
        return
    que = deque()
    que.append([x, 0])
    while que:
        node, cur = que.popleft()
        dx[node] = cur
        for _node in graph[node]:
            if dx[_node] is None:
                que.append([_node, cur + 1])
    que = deque()
    que.append([y, 0])
    while que:
        node, cur = que.popleft()
        dy[node] = cur
        for _node in graph[node]:
            if dy[_node] is None:
                que.append([_node, cur + 1])
    ret = 0
    for xx, yy in zip(dx[1:], dy[1:]):
        if xx >= yy:
            ret = max(ret, xx)
    print(ret)


if __name__ == '__main__':
    n, x, y = map(int, input().split())
    graph = defaultdict(list)
    for i in range(n - 1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    solve(n, x, y, graph)

第四题 100:

小团从某不知名论坛上突然得到了一个测试默契度的游戏,想和小美玩一次来检验两人的默契程度。
游戏规则十分简单,首先有给出一个长度为 n 的序列,最大值不超过 m。  小团和小美各自选择一个 [1,m] 之间的整数,
设小美选择的是 l,小团选择的是 r,我们认为两个人是默契的需要满足以下条件:  1. l 小于等于 r。  2. 对于序列中的元素 x,如果 0<x<l, 或 r<x<m+1,  则 x 按其顺序保留下来,要求保留下来的子序列单调不下降。  小团为了表现出与小美最大的默契,因此事先做了功课,他想知道能够使得两人默契的二元组 <l,r> 一共有多少种。  我们称一个序列 A 为单调不下降的,当且仅当对于任意的 i>j, 满足 A_i>=A_j。  输入第一行包含两个正整数 m 和 n,表示序列元素的最大值和序列的长度。(1<=n,m<=100000)  输入第二行包含 n 个正整数,表示该序列  5 5 4 1 4 1 2  10。
思路:
我们枚举 r
在给定r的情况下找最大的l(二分)
如果l满足, 那么小于l的也满足
def isvalid(nums):
    for idx, val in enumerate(nums):
        if idx == 0:
            continue
        if val < nums[idx - 1]:
            return False
    return True

def solve(m, n, nums):
    ret = 0
    r = m
    while r > 0:
        tmp1 = []
        for k in nums:
            if k > r:
               tmp1.append(k)
        if not isvalid(tmp1):
            break
        ll, rr = 1, r
        c = 0
        while ll <= rr:
            mid = (ll + rr) // 2
            tmp2 = []
            for k in nums:
                if k < mid&nbs***bsp;k > r:
                    tmp2.append(k)
            if isvalid(tmp2):
                c = mid
                ll = mid + 1
            else:
                rr = mid - 1
        r -= 1
        ret += c
    print(ret)



if __name__=='__main__':
    m, n = map(int, input().split())
    nums = list(map(int, input().split()))
    solve(m, n, nums)


全部评论

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

相关热帖

近期热帖

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

近期精华帖

热门推荐