拼多多笔试_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。