首页 > 试题广场 >

美团骑手包裹区间分组

[编程题]美团骑手包裹区间分组
  • 热度指数：1245 时间限制：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的划分是错误的，因为划分的片段数较少。
算法知识视频讲解
添加回答
pmad头像 pmad
典型的滑动窗口，先判断当前字符的最后一个位置在哪，在不断的更新另一个指针使得开始指针与结尾指针满中间没有的元素在后面不会出现。 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        String s=scanner.nextLine();
        int i=0,j=0,len=s.length();
        while(j<len){
            char c=s.charAt(j);
            int tail=s.lastIndexOf(c);
            int pre=j;
            i=j+1;
            j=tail;
            while(i<j){
                char inner=s.charAt(i);
                j=Math.max(j,s.lastIndexOf(inner));
                i++;
            }
            j++;
            System.out.print(j-pre+" ");
        }
    }
}


发表于 2020-03-08 21:46:16 回复(3)
小白白pang头像 小白白pang 
//c++版
#include<iostream>
(720)#include<algorithm>
#include<string>
using namespace std;
int main(){
	string s;
	cin >> s;//getline(cin,s);while(cin.peek()!='\n'){cin>>s};
    if(s.size()==1){
        cout<<1;
        return 0;
    }
    for(int i=0;i<s.size();++i){
        int pos=s.find_last_of(s[i]);
        int j=i;
        int k=0;
        for( k=i;k<pos;++k){
            if(s.find_last_of(s[k])>pos)
                pos=s.find_last_of(s[k]);
        }
        cout<<k+1-j<<' ';
        i=k;
        
    }
	return 0;
}

发表于 2020-04-01 12:25:40 回复(3)
吃**的蜗牛头像 吃**的蜗牛 
import java.util.*;

public class Main{
    public static void main(String args []){
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        int n = s.length();
        int max_i = s.lastIndexOf(s.charAt(0));
        int ans = 1;
        for(int i = 1; i < n; i++){
            char c = s.charAt(i);
            int index = s.lastIndexOf(c);
            if(i <= max_i){
               ans++;
               if(index>max_i) max_i=index;
            }else{
               System.out.print(ans+" ");
               ans = 1;
               max_i = index;
            }
        }
        System.out.print(ans+" ");
        System.out.println();
    }
}

发表于 2020-08-12 16:27:42 回复(0)
C/C++
尚未必将头像 尚未必将
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    string str;
    while(getline(cin, str))
    {
        for(int i = 0; i < str.size(); i++)
        {
            // 找到第一个字符最后出现的位置
            int pos = str.find_last_of(str[i]);
            // 在[i,pos]区间中找其他字符最后出现的位置
            // 如果其他字符pos位置更大就更新区间
            // 直到找到最大区间位置
            for(int j = i+1; j < pos; j++)
            {
                int tmp = str.find_last_of(str[j]);
                if(tmp > pos) pos = tmp;
            }
            // 输出区间长度
            cout << pos - i + 1 << " ";
            // 更新下一个开始位置
            i = pos;
        }
    }
    return 0;
}
编辑于 2024-03-12 10:55:10 回复(0)
Python
折纸Sun头像 折纸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)
C++
牛客133685368号头像 牛客133685368号
贪婪算法 
#include <bits/stdc++.h>
using namespace std;
void partitionLabels(string s) {
    unordered_map < char, int > last; // 记录每个字母的最后位置
    for (int i = 0; i < s.size(); i++) {
        last[s[i]] = i;
    }
    int start = 0; // 当前片段的起始位置
    int end = 0; // 当前片段的结束位置
    for (int i = 0; i < s.size(); i++) {
        end = max(end,
                  last[s[i]]); // 更新结束位置为当前字母的最后位置和原来结束位置的较大值
        if (i == end) { // 如果当前位置等于结束位置，说明可以切分出一个新片段
            cout << (end - start + 1) << " "; // 将新片段的长度加入结果
            start = i + 1; // 更新起始位置为下一个位置
        }
    }
}
int main() {
    string s;
    cin >> s;
    partitionLabels(s);
    return 0;
}


发表于 2023-03-03 20:39:36 回复(0)
Java
牛客604106812号头像 牛客604106812号 


import java.util.*;

/**
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        List<Integer> result = new ArrayList();
        for (int cut = 0; cut< str.length() ; cut++) {
            char tmp = str.charAt(cut);
            int begin = str.substring(0,cut).indexOf(tmp);
            if(begin == -1){
                result.add(cut);
            }else{
                result.removeIf(x->x>=begin);
                result.add(cut);
            }
        }
        int start = 0;
        for(int i=0;i<result.size();i++){
            System.out.print(str.substring(start,result.get(i)+1).length());
            System.out.print(" ");
            start = result.get(i)+1;
        }
    }

}
编辑于 2020-11-03 17:24:33 回复(0)
只故头像 只故
利用滑动窗口技术，O(n)的时间复杂度。 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    cin>>str;
    unordered_map<char,int>mp;
    for(auto ch:str)
    {
        if(mp.count(ch)>0) mp[ch]++;
        else mp[ch]=1;
    }
    unordered_map<char,int>mpt;
    int cnt=0,match=0;
    vector<int> vec;
    int last=0;
    for(int i=0;i<str.size();i++)
    {
        if(mpt.count(str[i])>0)
        {
            mpt[str[i]]++;
            if(mpt[str[i]]==mp[str[i]]) match++;
            if(match==cnt)
            {
                vec.push_back(i-last+1);
                last=i+1;
                cnt=0;
                match=0;
            }
        }
        else
        {
            mpt[str[i]]=1;
            cnt++;
            if(mpt[str[i]]==mp[str[i]]) match++;
            if(match==cnt)
            {
                vec.push_back(i-last+1);
                last=i+1;
                cnt=0;
                match=0;
            }
        }
    }
    for(int i:vec)
        cout<<i<<" ";
    return 0;
    
}


发表于 2020-04-27 14:47:18 回复(0)
林佳潇头像 林佳潇
贪心的去分行了，如果当前能分割就立马分割，记录下每个字母最远的位置 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string str;
    cin >> str;
    vector<int>pos(26);
    for (int i = 0; i < str.size(); i++)
        pos[str[i] - 'A']=max(pos[str[i] - 'A'],i);
    int max_ = 0,last=-1;
    for (int i=0; i < str.size(); i++)
    {
        max_ = max(max_, pos[str[i] - 'A']);
        if (i >= max_)
        {
            cout << i - last << " ";
            last = i;
        }
    }
    return 0;
}


发表于 2020-04-17 12:43:50 回复(0)
hashSet头像 hashSet
有点复杂得解法。。先过滤一遍  找到最初和最后；
找到最后，然后最初在里面的最后如果在先前的最后后面，更新最后；
一直更新到区间不再增长，就是一段了 
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        char[] chars = s.toCharArray();
        int length = chars.length;
        int[] lastIndexArray = new int[26];
        int[] firstIndexArray = new int[26];
        Arrays.fill(firstIndexArray, -1);
        for (int i = 0; i < length; i++) {
            lastIndexArray[chars[i] - 65] = i;
            if (firstIndexArray[chars[i] - 65] == -1) {
                firstIndexArray[chars[i] - 65] = i;
            }
        }
        int previousSegmentIndex = -1;
        for (int i = 0; i < length; i++) {
            Set<Character> charSet = new HashSet<>(32, 1);
            // calculate last index of specific char
            int lastIndex = lastIndexArray[chars[i] - 65];
            int lastSize = -1;
            // find the between chars
            while (charSet.size() > lastSize) {
                lastSize = charSet.size();
                for (int j = 0; j < 26; j++) {
                    if (lastIndex > firstIndexArray[j]) {
                        charSet.add((char) (j + 65));
                        if (lastIndex < lastIndexArray[j]) {
                            lastIndex = lastIndexArray[j];
                            break;
                        }
                    }
                }
            }
            System.out.print(lastIndex - previousSegmentIndex+ " ");
            previousSegmentIndex = lastIndex;
            i = previousSegmentIndex;
        }

    }
}

发表于 2020-04-10 15:41:53 回复(0)
字节研发工程师头像 字节研发工程师
不断更新右边界即可 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int[] hash=new int[26];
        for (int i = 0; i <s.length() ; i++) {
            hash[s.charAt(i)-'A']=i;
        }
        int left=0,right=hash[s.charAt(0)-'A'];
        while (left<s.length() && right<s.length()){
            int i=0;
            while (i<right){
                right=Math.max(right,hash[s.charAt(i)-'A']);
                i++;
            }
            System.out.print(right-left+1+" ");
            left=right+1;
            if (i+1<s.length())
            right=hash[s.charAt(i+1)-'A'];
        }
    }
}


发表于 2020-04-08 17:00:20 回复(0)
Cantwell头像 Cantwell 
package meitaun;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Package {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        Scanner sc = new Scanner(System.in);
        String pkg = sc.nextLine();
        for (int i = 0; i < pkg.length(); i++) {
            int pre = i;
            int tail = pkg.lastIndexOf(pkg.charAt(i));
            while (i < tail) {
                i++;
                tail = Math.max(tail, pkg.lastIndexOf(pkg.charAt(i)));
            }
            list.add(tail - pre + 1);
        }
        for (int val : list) {
            System.out.print(val + " ");
        }
    }
}

发表于 2020-04-08 11:41:50 回复(0)
LYcreate头像 LYcreate
时间复杂度O(n)-O(nlogn)
空间复杂度O(n) 
import java.util.*;

public class Main {

    static List<Integer> solution(String s){
        HashMap<Character,int[]> map=new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))){
                map.get(s.charAt(i))[1]=i;
            }else{
                map.put(s.charAt(i),new int[]{i,i});
            }
        }
        ArrayList<int[]> list=new ArrayList<>();
        for (Character key:map.keySet()){
           int[] tmp=map.get(key);
           list.add(tmp);
        }
        list.sort(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        ArrayList<Integer> res=new ArrayList<>();
        int k=0;
        res.add(list.get(0)[1]-list.get(0)[0]+1);
        for (int i = 1; i < list.size(); i++) {
            int[] prev=list.get(i-1);
            int[] cur=list.get(i);
            if (cur[0]<prev[1]){
                cur[0]=prev[0];
                if (cur[1]<prev[1]){
                    cur[1]=prev[1];
                }
                res.set(k,cur[1]-cur[0]+1);
            }else{
                res.add(cur[1]-cur[0]+1);
                k++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        String s=in.nextLine();
        List<Integer> res=solution(s);
        for (int i = 0; i <res.size() ; i++) {
            System.out.print(res.get(i)+" ");
        }
        System.out.println();
    }
}


发表于 2020-04-02 11:32:47 回复(0)
Java
悟Kong头像 悟Kong 
package substring;
import java.util.Scanner;
public class solution {
	public static void main(String[] args){
		Scanner s=new Scanner(System.in);
		String str=s.next();
		s.close();
		int start=0;
		int i=1;
		while(i<=str.length()){
			String temp=str.substring(start,i);
			int j=0;
			for(;j<temp.length();j++){
				if(str.indexOf(temp.charAt(j),i)>0){
					break;
				}
			}
			if(j==temp.length()){
				start=i;
				System.out.print(temp.length()+" ");
			}
			i++;
		}
		return;
	}
}

发表于 2020-03-28 11:22:27 回复(0)
弱鸡单排头像 弱鸡单排
贪心、区间合并问题：
复杂度：O(n) 
#include<bits/stdc++.h>

using namespace std;

struct node
{
    int start = INT_MAX,ed = INT_MIN;
    bool operator < (const node &x) const
    {
        return start<x.start;
    }
}pos[30];
int ans[30];

int main()
{
    string s;
    cin>>s;
    int n = s.size();
    for(int i = 0;i<n;i++)
    {
        pos[s[i]-'A'].start = min(pos[s[i]-'A'].start,i);
        pos[s[i]-'A'].ed = max(pos[s[i]-'A'].ed,i);
    }
    sort(pos,pos+30);
    int l = 0,r = 0;
    int cnt = 0;
    int len = 0;
    for(int i = 0;i<30;i++)
    {
        if(pos[i].start>r)
        {
            cnt++;
            ans[len++] = r-l+1;
            l = pos[i].start;
            r = pos[i].ed;
        }
        else
        {
            r = max(r,pos[i].ed);
        }
        if(pos[i].start==INT_MAX)
            break;
    }
    for(int i = 0;i<len;i++)
        printf("%d ",ans[i]);
}


发表于 2020-03-12 16:48:01 回复(3)
陌离20180404224926头像 陌离20180404224926
滑动窗口 
#include <bits/stdc++.h>
using namespace std;
vector<int> test(string s){
    vector<int> freq(26,0);//记录每个字母出现的频率
    for(int i = 0; i < s.size(); i++){
        freq[s[i] - 'A']++;
    }
    int l = 0, r = -1;
    int n = s.size();
    vector<int> res;
    while(l < n){
        if(r+1 < n && freq[s[r+1] - 'A'] != 0){
            freq[s[++r] - 'A']--;
        }
        if(freq[s[r] - 'A'] == 0){
            int count = 0;
            for(int i= l; i <= r; i++){
                if(freq[s[i] - 'A'] != 0){
                    break;
                }else{
                    count++;
                }
            }
            if(count == r-l+1){ //符合
                res.push_back(r-l+1);
                l = r+1;
            }
        }
    }
    return res;
}
int main()
{  
    string s;
    getline(cin,s);
    vector<int> v = test(s);
    for(int i = 0; i < v.size(); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
    return 0;
}


发表于 2020-03-12 15:04:00 回复(0)
vector<>头像 vector<>
#include<iostream>
#include<string>
using namespace std;
int main() {
    string str;
    cin >> str;
    int last = -1;
    int index = 0;
    int pos[1000] = { 0 };
    for (int i = 0; i < str.length(); i++) {
        for (int j = i; j<str.length(); j++) {
            if (str[j] == str[i])
            {
                if(j>last)last = j; 
            }
        }
        if (i == last) {
            last = 0;
            pos[index] = i;
            index++;
        }
    }
    cout << pos[0]+1<<" ";
    for (int i = 0; i+1< index; i++) {    
        cout << pos[i + 1] - pos[i]<<" ";
    }
}
发表于 2020-03-10 22:20:30 回复(0)
提交观点

问题信息

C++工程师 美团 2020 Java工程师
上传者：小小
难度：
17条回答 4793浏览

热门推荐

通过挑战的用户

相关试题

美团骑手包裹区间分组

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号