美团9-6:编程题

题目1

已知一套试卷包含多个 x-dp 算法，即x类型的 dp(保证x不为空且不含’d’和’p’两个字符)。例如 sosdp，adp,其拼接起来为 sosdpadp，构成了一套完整的试卷。
现在便可以得到该试卷中存在若干类型的 dp 算法，你需要知道有多少种本质不同的 dp 算法，即有多少种不同。类型的算法。保证s可以被唯一地分割为一个或多个形如x+ dp 的段。

思路

这道题的思路比较简单，我们遍历这个字符串，当遇到d时就判断前方是否有字符如果有就判重，重复了就跳过这个dp继续遍历如果没有重复就让答案++。最后返回答案即可。
其中的细节是我们在遇到d时就可以直接判断了因为题目说了x里是不会有d和p的所以遇到d了就是遇到dp了。其次是如何判重，我们定义一个哈希集合，让遇到dp时判断前方的字符串是否存在于这个哈希集合里如果存在就跳过，不存在就插入进去。最后返回哈希集合的size即可。

代码

#include <iostream>
#include <unordered_set>
using namespace std;int main()
{string s;cin >> s;unordered_set<string> us;int left = 0;int right = 0;//遍历字符串while(right < s.size()){//题目要求前面的x里不能有d和p所以我们只要找到d就等于找到dp了if(right > 0 && s[right] == 'd'){//判断dp前面是否有字母if(right - left < 1){//直接跳过dpleft = right+2;right++;continue;}//判断us里是否有这个字符串if(us.count(s.substr(left,right-left))){//直接跳过dp,不插入usleft = right+2;right++;continue;}//将这个字符串插入usus.insert(s.substr(left,right-left));//更新left和rightleft = right+2;right++;}//更新rightright++;}cout << us.size() << endl;return 0;
}

题目2

小美有一个长度为n的数组 a。你可以将a任意重排。定义一个长度为 n 的数组 b,其中 b;=MEX(a1,a2,···,a;)。你需要最大化数组b中的元素之和。
你需要输出最大的元素和，以及一个可能的a的重排方案。
MEX：整数数组的 MEX 定义为没有出现在数组中的最小非负整数。例如MEX(1,2,3}=0、MEX{0,2,5}=1。

思路

对于这道题思路其实也是比较简单的，b的每个位置的值是数组a以每个位置结尾的MEX值。如果我们想要得到最大元素和我们应该把数组a里小的元素排在最前面，这是为什么呢？因为MEX值是最小非负整数所以如果数值小的元素在数组的中间或者后面就会导致前面的所有mex值都变小了例如MEX{5,9,6,2,1} = 1，特别是如果数组a中有元素是连在一起的结果却被分开了也就导致MEX值会变小。所有我们可以先对数组a进行排序然后从头开始一个一个的查找MEX值，查找MEX值也很简单，定义整数变量mex = 0然后从头开始遍历到当前位置如果数组a里有值等于mex就让mex++。这样就可以得到当前位置的mex值了。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main()
{int n;cin >> n;vector<int> a(n);for(int i = 0; i < n; i++){cin >> a[i];}// 排序数组sort(a.begin(), a.end());vector<int> b(n);int mex = 0;  // 当前 MEX 值long long total = 0;for(int i = 0; i < n; i++){// 计算 MEX(a[0], a[1], ..., a[i])int mex = 0;for(int j = 0; j <= i; j++){if(a[j] == mex){mex++;}}b[i] = mex;total += b[i];}cout << total << endl;for(int i = 0; i < n; i++){cout << a[i] << " ";}cout << endl;return 0;
}