美团415笔试题目简述

简述题目：

一、n组数据。给定字符串S、T，可对S进行任意字符修改，或删除末位字符。求操作多少次可以使得S为T的前缀。

样例：aba 变 abb前缀，改或删最后一个字符都可，1次操作。abcd变efg，只能全删，4次操作。

思路：能改则不删，只有S大于T才用删。分为S小于T直接求前len(S)个不同字符数，S大于T求前len(T)不同字符数加上len(S)-len(T)

二、一种糖果a个，另一种b个。分给n个人（a+b>n每人至少一个），每人的糖果只能全部为一种。求怎么分可以让每个人都尽可能多，即分得最少的人的糖果数也尽可能多，输出这个数量。

样例：5 2 3 -5个人分 2+3 每人一个输出1

4 7 10 a(3+4) b(5+5) 输出3

4 4 15 a(4)b(5+5+5) 输出4

思路：可无限再分状态下，x = a/(a+b)*n人得到a，y = b/(a+b)*n人得到b，理想平均。由于人不可再分，得到a和得到b的人数必定有一个舍一个进。即 x下取整人得a，y上取整人得b，或x上取整人得b，y下取整得a。有了xy，直接用a//x，b//y得到 a糖果的最少分配和b糖果的最少分配。两者取最小得到一种分配情况下的最小值，两种情况求大者得到最终答案。注意对全部分a和全部分b作特判，不然会除0异常。

三、n个城市摆成一行，互相之间没有路。可使用 (L x) / (R x) 操作为x城市添加与左边/右边城市的一条双向路。可使用Q x操作查询城市x两边能到达最远的城市。共T次操作。

样例：3 5 (3个城市5次操作)

Q 2 P(初始状态查2，输出2 2 只能在原地)

L 2 (向左连接2 和 1)

Q 2 P(输出1 2)

R 2 (向右连接2和3)

Q 2 P(输出1 3)

思路：想到建图，这里题目已经规定了点是按顺序排列的，因此有数组的属性，可以看作特殊的图。

而且是一个双向链表。

维护一张双向链表，并且从给定节点向两端遍历即可。我用的dfs

class Node:
    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right
def ldfs(node):
    if not node.left:
        return 0
    return ldfs(node.left) + 1
def rdfs(node):
    if not node.right:
        return 0
    return rdfs(node.right) + 1
ar = [None] * (n + 2)

    if oper == "Q":
        l = ldfs(ar[x])
        r = rdfs(ar[x])
        print(x-l, " ", x+r)
    if oper == "L":
        if x <=1:
            continue
        ar[x].left = ar[x - 1]
        ar[x-1].right = ar[x]
    if oper == "R":
        if x>=n:
            continue
        ar[x].right = ar[x + 1]
        ar[x+1].left = ar[x]

四、n个套娃，每个套娃有属性体积a、容积b、单位价值c。

如果套娃内部是空的，则满价值，如果有其他套娃占位，只计算空的部分的价值。

比如单位价值2的容积5的套娃原价2*5，被体积3的填了，则价值改为2*2

套娃可以互相套也可以不套完，求一种方式使得所有套娃总价值最低。

样例：3

5 4 3

4 2 2

3 2 1

第二个放第一个里第一个没有价值，后两个2*2+2*1 输出6

思路：动态规划吧，我不太行。想着骗分，就按照容积为键排了个序，由小到大尝试往里放。暴力过了18%

欢迎补充。

五、n个自然数(>=0)集合，可以将一个数增加到任意值。求任意操作后，集合中没有出现的最小自然数，最大可能为多少。