微软2022暑期实习笔试
1.求完成任务的最小天数
描述;给出一个一维任务数组A，数组内容是任务的紧急程度，另有一个整数M。一天可以完成多个任务，每个任务必须按顺序完成，一天内完成的任意两个任务的之间紧急程度差值不能大于M,求完成所有任务的最小天数。
例如：A=[1,12,10,4,5,2] M=2，答案是4
int solution(vector<int>&nums,int M){
int ans = 1;
int Max=nums[0], Min=nums[0];//维护当前一天里已完成任务的最大最小紧急程度
for (int i = 1; i < nums.size(); i++){
if(nums[i]<Max-M||nums[i]>Min+M)//该任务不符合加入当前天的要求
{
++ans;
Max = nums[i];
Min = nums[i];
}
else{//符合条件 但是要更新区间值
Max = max(Max, nums[i]);
Min = min(Min, nums[i]);
}
}
return ans;
} 2.给出两个长度相同的字符串，求两个字符串中相“匹配”的字符子串个数，“匹配”是指两个子串在原字符串中起点相同，且两个字符子串长度一致，各字符出现次数一致（同一字符串内部字符不同排序构成的字符串）
例如：s="dBacaAA" ,t="caBdaaA",答案是5
其中 "dBac"与"caBd"匹配（子串起始位置：0）
"dBaca"与"caBda"匹配（子串起始位置：0）
"Ba"和"aB"匹配（子串起始位置：2）
"a"与"a"匹配（子串起始位置：4）
"A"与"A"匹配（子串起始位置：6）
3.给出一个一维数组，数组内容是坐标，代表点在横轴上的位置，给出一整数M,求一最大点集，集合内任意点之间横轴距离差都是M的倍数。（特别标注需考虑运行效率）
数组元素的范围是（-1000000000,1000000000），点的个数范围是（1,1000000000）
题解：用map，定义一个map<int,vector<int>>的map
int solution(vector<int> &A, int M) {
// write your code in C++14 (g++ 6.2.0)
sort(A.begin(), A.end());
map<int, vector<int>> mp;
int ans=1;
for (int i = 0; i < A.size(); i++){
auto it = mp.begin();
for (; it != mp.end(); it++){
if ((A[i] - it->first)%M == 0){
it->second.push_back(A[i]);
ans = max(ans, (int)it->second.size());
break;
}
}
if (it == mp.end())
{
mp[A[i]].push_back(A[i]);
}
}
return ans;
} int solution(vector<int> &A, int M) {
map<int, vector<int>> mp;
int ans=1;
for (int i = 0; i < A.size(); i++){
mp[(A[i]%M)+M].push_back(A[i]);
ans = max(ans, (int)mp[(A[i] + M) % M].size());
}
return ans;
} 
拼多多集团-PDD工作强度 277人发布
