首页 > 试题广场 >

美团骑手包裹区间分组

[编程题]美团骑手包裹区间分组

热度指数：1252 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

2110年美团外卖火星第3000号配送站点有26名骑手，分别以大写字母A-Z命名，因此可以称呼这些骑手为黄家骑士特工A，黄家骑士特工B…黄家骑士特工Z，某美团黑珍珠餐厅的外卖流水线上会顺序产出一组包裹，美团配送调度引擎已经将包裹分配到骑手，并在包裹上粘贴好骑手名称，如RETTEBTAE代表一组流水线包裹共9个，同时分配给了名字为A B E R T的5名骑手。请在不打乱流水线产出顺序的情况下，把这组包裹划分为尽可能多的片段，同一个骑手只会出现在其中的一个片段，返回一个表示每个包裹片段的长度的列表。

输入描述:

输入数据只有一行，为一个字符串(不包含引号)，长度不超过1000，只包含大写字母'A'到'Z'，字符之间无空格。

输出描述:

输出每个分割成片段的包裹组的长度，每个长度之间通过空格隔开

示例1

输入

MPMPCPMCMDEFEGDEHINHKLIN

输出

9 7 8

说明

划分结果为MPMPCPMCM,DEFEGDE,HINHKLIN。

每个骑手最多出现在一个片段中。

像MPMPCPMCMDEFEGDE,HINHKLIN的划分是错误的，因为划分的片段数较少。

算法知识视频讲解

Python

折纸Sun

words=input()
new=[]#记录不重复字符
start=[]#记录字符第一次出现的位置
end=[]#记录字符最后一次出现的位置
count=0
for i in range(len(words)):
    word=words[i]
    if word not in new:
        new.append(word)
        start.append(i)
        end.append(i)
        count+=1
    else:
        for j in range(len(new)):
            if word==new[j]:
                end[j]=i
#print(words,new,start,end)
i=0
out=[]
while i<len(new):
    s,e=start[i],end[i]
    tmp=words[s:e+1]
    for j in range(i,len(new)):
        if new[j] in tmp:
            e_new=end[j]
            e=max(e,e_new)
            tmp=words[s:e+1]
            i=j
    i+=1
    out.append(tmp)
for i in range(len(out)):
    print(len(out[i]),end=' ')

发表于 2023-03-12 16:03:21 回复(0)