首页 > 试题广场 >

美团骑手包裹区间分组

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

热度指数：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的划分是错误的，因为划分的片段数较少。

算法知识视频讲解

Java

牛客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)

Java

悟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)