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