标签搜索

目 录CONTENT

文章目录

美团--美团骑手包裹区间分组.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 3 阅读 / 2,114 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

美团--美团骑手包裹区间分组

@[toc]

一、题目描述

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

  •  输入描述:
输入数据只有一行,为一个字符串(不包含引号),长度不超过1000,只包含
大写字母'A'到'Z',字符之间无空格。
  •  输出描述:
输出每个分割成片段的包裹组的长度,每个长度之间通过空格隔开


输入例子1:
MPMPCPMCMDEFEGDEHINHKLIN

输出例子1:
9 7 8

例子说明1:
划分结果为MPMPCPMCM,DEFEGDE,HINHKLIN。

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

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

二、分析

  •  这个问题有点像求每个连续区间的长度,而每个连续区间都是由小区间的覆盖连接组合起来的每个字母第一次和最后一次出现的位置构成一个个小区间
  •  所以我们可以先记录每个字母最后一次出现的位置:
	for (int i = 0; i < 26; i++)
    {
        int t = S.find_last_of((char)( i + 'A'));
        letterRight[i] = t;
    }
  •  现在我们只需要遍历一个个小区间即可
  •  现在需要注意的问题是我们知道了每个字符的最后一次出现的位置,但是在一个字符第一次出现的位置和最后一次出现的位置之间还可能出现其他字符
  •  那么我们需要判断在一个字符区间中间出现的字符最后一次出现的位置是否超过本次区间的最后一次出现的位置
	int left, right;
    left = start;
    right = letterRight[S[left] - 'A'];
    for (int i = left+1; i <= right; i++)
    {
        if (letterRight[S[i]-'A'] > right) 
        	right = letterRight[S[i] - 'A'];
    }
    return right - left+1;

三、代码

#include <iostream>
#include <vector>
using namespace std;

int divide(string S, int start, int end,int letterRight[26])
{
	//代表该字符所表示的区间左边界
    int left = start;
    //代表该字符所表示区间的右边界
    int right = letterRight[S[left] - 'A'];
    //遍历该字符所表示的整个区间
    for (int i = left + 1; i <= right; i++)
    {
    	//如果出现该区间中间的字符所表示的区间的右边界超过right
    	//那么我们就需要更新right继续判断,从而获得整个区间的长度
        if (letterRight[S[i] - 'A'] > right) 
        	right = letterRight[S[i] - 'A'];
    }
    return right - left+1;

}
 
vector<int> partitionLabels(string S) 
{
	//保存每个字符最后一次出现的位置
    int letterRight[26];
	
	//保存每个区间的长度
    vector<int> result;
 
 	//统计每个字符最后一次出现的位置
    for (int i = 0; i < 26; i++)
    {
        int t = S.find_last_of((char)( i + 'A'));
        letterRight[i] = t;
    }

	//字符所表示区间的开始
    int start = 0; 
	//字符所表示区间的结束
	int end = S.size(); 
	//表示该小区间最终的长度
	int tmp;
    while (start < end)
    {
    	//得到满足题意:同一个字符只存在一个区间;的区间长度
    	//并保存到result当中
        tmp = divide(S, start, end, letterRight);
        result.push_back(tmp);

		//注意注意⚠️,一旦从前往后遍历找到一个区间,一定要更新start的值
		//不一定再从下一个位置继续判断,因为可能下一个字符的位置在区间的中间,
		//那么该字符肯定已经被计算到区间长度当中,不用多次计算
        start += tmp;
    }
    return result;
}
int main()
{
    string str;
    getline(cin, str);
    vector<int> result = partitionLabels(str);
    //打印结果
    for (int i = 0; i < result.size(); i++)
    {
        cout<<result[i]<<" ";
    }
    return 0;
} 
0

评论区