拼多多笔试_09.03

第一题(100%):可能大家想复杂了,这题纯贪心就可以做出来,为了获得字典序,肯定是将字符串中最前面的字符往前推进,能推进多少就推进多少,如果能够顺带着将后面的的字符推进那就更好了,于是我创建了一个visited数组来标明可不可行,当后续字符想要往前推进的时候两个情况,一个是k还有,一个是visited为true。
第二题(100%):这题纯模拟就好了,根据输入,判断啥时候出界,可以用map或者set标明是否之前到达过,如果到达过说明不可能跳出去。
第三题(100%):这题比较坑的一点就是他要的是最大字典序,我说我思路咋没有问题提交只有8%, 后面把顺序改了改就ac了,贴个代码,这是唯一拿去本地调试了的....
#include<iostream>
#include<vector>

using namespace std;


bool check(vector<int>& counta, vector<int>& countb, vector<int>& change){
    int bsize = countb.size();
    vector<int> copya(counta), copyc(change);
 //   cout << bsize << endl;
    for(int i = 0; i < bsize; i++){
        if(countb[i] != 0){
  //          cout << i << " " <<  countb[i] << " " << counta[i] << " " << copya[26] << endl;
            if(copya[i] + copya[26] >= countb[i]){
                if(copya[i] >= countb[i])
                    copya[i] -= countb[i];
                else{
                    int dis = countb[i] - copya[i];
                    copyc[i] += dis;
                    copya[26] -= dis;
                    copya[i] = 0;
                }
            }else
                return false;
        }

    }
    counta = copya;
    change = copyc;

    return true;
}



int main(){
    string s, t;
    cin >> s >> t;

    vector<int> counta(27, 0);
    vector<int> countb(26, 0);
    vector<int> chindex;
    int ssize = s.size(), tsize = t.size();

    if(ssize < tsize){
        cout << s << endl;
        return 0;
    }

    for(int i = 0; i < ssize; i++){
        if(s[i] >= 'a' && s[i] <= 'z')
            counta[s[i] - 'a']++;
        else{
            counta[26]++;
            chindex.push_back(i);
        }
    }

    for(int i = 0; i < tsize; i++)
        countb[t[i] - 'a']++;

    vector<int> change(26, 0);
    while(check(counta, countb, change)){

    }

    for(int i = 0; i <= 25; i++){
        while(change[i]){
            int index = chindex.back();
            chindex.pop_back();
            s[index] = i + 'a';
            change[i]--;
        }
    }

    while(!chindex.empty()){
        int index = chindex.back();
        chindex.pop_back();
        s[index] = 'z';
    }

    cout << s << endl;

    return 0;
}
第四题(0):时间不够用,只不过就是菜,也没有骗到分,大佬们可以在评论区说一下第四题思路,我感觉可能这题可能有公式或者需要进行分组 再dp。


#拼多多笔试##秋招##笔试#
全部评论
老哥能贴个第一题吗 感谢
1 回复 分享
发布于 2022-09-03 18:32 四川
想请问一下怎么报名pdd...
点赞 回复 分享
发布于 2022-09-03 18:50 安徽
第三题多余的#要用z填充嘛?
1 回复 分享
发布于 2022-09-03 18:08 上海
是的 为了获得他所谓的字典序🤣
点赞 回复 分享
发布于 2022-09-03 18:10 湖北
nmd,一三题测试用例过了硬是想不出错在什么细节的地方,第一题0,第三题16无语了
点赞 回复 分享
发布于 2022-09-04 09:34 上海
hi~同学,秋招遇“寒气”,牛客送温暖啦!23届秋招笔面经有奖征集中,参与就得牛客会员7天免费体验,最高赢300元京东卡!戳我去看>>>https://www.nowcoder.com/link/zhengjipinglun
点赞 回复 分享
发布于 2022-09-04 15:47 北京

相关推荐

点赞 评论 收藏
分享
object3:开始给部分🌸孝子上人生第一课了
点赞 评论 收藏
分享
评论
6
11
分享
牛客网
牛客企业服务