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