0822笔试回忆

题目描述：

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

输入

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

输出

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

样例输入

MPMPCPMCMDEFEGDEHINHKLIN

样例输出

9 7 8

代码：

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

int divide(string S, int start, int end,int letterRight[26])
{
    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;
 
}
 
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)
    {
        tmp = divide(S, start, end, letterRight);
        result.push_back(tmp);
        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;
} 

题目描述：

给定一组个字符串，为每个字符串找出能够唯一识别该字符串的最小前缀。

输入

输入n串唯一的字符串，n为2到100之间，字符串用“,”隔开，字符串长度不超过100。

输出

可以唯一区分字符串的最小前缀，用“,”隔开。

样例输入

meituanapp,meituanwaimai,dianpingliren,dianpingjiehun

样例输出

meituana,meituanw,dianpingl,dianpingj

代码

#include<stdio.h>
#include <iostream>
#include<string.h>
#include <string>
#define N 2501

using namespace std;
int trie[N][105]; 
int trie_flag[N]; 
int tot=0;
void insert(char *s){
    int i,id,len,root=0; 
    len=strlen(s);
    for(i=0;i<len;i++)
    {   
        id=s[i]-'a';
        if(!trie[root][id]) trie[root][id]=++tot;
        trie_flag[trie[root][id]]++;
        root=trie[root][id];
   }
}
void search(char *s){
    //printf("%s ",s);
    int i,len,id,root=0;
    len=strlen(s);
    for(i=0;i<len;i++)
    {    
        printf("%c",s[i]);
        id=s[i]-'a';
        if(trie_flag[trie[root][id]]==1)break;
           root=trie[root][id];
    }
}
int main()
{   
    char s[105][105];
    int n=0; 
    memset(trie,0,sizeof(trie));
    memset(trie_flag,0,sizeof(trie_flag));
    string str;
    getline(cin, str);
    int j = 0;
    for (int k=0; k<str.size(); k++){
        if (str[k] != ','){
            s[n][j++] = str[k];
        }else{
            j = 0;
            insert(s[n++]);
        }
    }
    insert(s[n++]);
    int i=0;
    while(n--) {
        search(s[i++]); 
        if(n != 0)cout<<","; 
    } 
    return 0;   
}