20210313美团笔试总结
总结：
- 听同学说，只要提交了有AC百分之多少，就会有相应的分数，下次一定要及时提交，然后再优化使其达到AC100%；
- 对于输入输出的操作还不太熟悉，这也难怪，之前都是使用LeetCode，突然转换到类似牛客的这种方式，不太习惯
- 总共5道编程题，其实不用太赶，第一次过于谨慎，过于紧张了
1数组对称输出
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int main(){
int m,n;
cin>>m>>n;
vector<vector<int>> nums(m,vector<int>(n));
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
cin>>nums[i][j];//对于cin，会跳过换行、回车、Tab，也用换行、回车、Tab来区分输入
for(int i=0;i<m;++i){
for(int j=0;j<n;++j)
cout<<nums[i][j]<<" ";
cout<<endl;
}
return 0;
}
2打印字符串中的数字，并排序
发现stoi会自动将前导0去掉；AC49%，可能是大数问题，没有考虑long的情况；
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int main(){
string str;
cin>>str;
vector<int> nums;
string tmpnum;
for(auto i=0;i<str.length();++i){
while(str[i]>='0'&&str[i]<='9'){
tmpnum+=str[i];
i++;
}
while(!tmpnum.empty()){
if(tmpnum[0]=='0')
tmpnum.erase(0,1);
else
{
break;
}
}
if(!tmpnum.empty()) nums.push_back(stoi(tmpnum));
tmpnum.clear();
}
sort(nums.begin(),nums.end());
for(auto i:nums)
cout<<i<<endl;
return 0;
}
3数组里连续k个数，ai、ai+1、…ai+k-1,的众数
暴力方法：每次将k个数传到一个新的数组里面，然后利用sort排序从大到小，这样找出的众数一定是最小的，（这里可以利用sort从大到小排序，而不是sort然后reverse），找众数的过程可以采用摩尔投票；
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
//找出数组里面连续k个数的众数，如果存在多个众数，输出最小的那个
//暴力方法：每次将k个数传入一个新的数组里面，sort然后reverse，然后摩尔投票得出众数;
//如果直接使用摩尔排序的话，最后得到的众数可以不是最小的
bool MyFunction(int& a,int& b){
return a>b;
}
int ReturnMode(vector<int>& nums,int begin,int k){
vector<int> NUMS;
for(int i=begin;i<begin+k;++i)
NUMS.push_back(nums[i]);
sort(NUMS.begin(),NUMS.end(),MyFunction);
//摩尔投票
int Candidate=NUMS[0],count=0;
for(int tmp:NUMS){
if(Candidate==tmp){
count++;
continue;
}
if(count==0){
Candidate=tmp;
count++;
continue;
}
count--;
}
return Candidate;
}
int main(){
int n,k;
cin>>n>>k;
vector<int > nums(n);
for(int i=0;i<n;++i)
cin>>nums[i];
for(int j=0;j<n-k+1;++j)
cout<<ReturnMode(nums,j,k)<<endl;
return 0;
}
摩尔思路来自LeetCode169、LeetCode229：
如果需要找出数组里面多个众数，例如：
想要找出两个众数，那么每个众数需要出现n/(2+1)次
想要找出k个众数，那么每个众数需要出现n/(k+1)次
具体实现的时候，定义两个待选candidate1、candidate2，以及选票数count1、count2；
分为两个阶段：投票阶段、计数阶段；
为什么投完票还要重新计数？
因为可能选出了两个数，其中一个不满足出现n/3次，
例如 1,2,1,1,1,3 ；摩尔投票选出了1和3，但是3只出现了1次，不满足，因此满足条件的众数是1；
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
//摩尔投票:分为投票阶段和计数阶段
//想要找出两个众数，那么每个众数需要出现n/(2+1)次
//想要找出k个众数，那么每个众数需要出现n/(k+1)次
vector<int> Ans;
//投票阶段
int cand1=nums[0],cand2=nums[0],count1=0,count2=0;
for(auto tmpNum:nums){
if(cand1==tmpNum){
count1++;
continue;
}
if(cand2==tmpNum){
count2++;
continue;
}
if(count1==0)
{
cand1=tmpNum;
count1++;
continue;
}
if(count2==0)
{
cand2=tmpNum;
count2++;
continue;
}
count1--;
count2--;
}
//计数阶段
count1=0,count2=0;
for(auto tmpNum:nums){
if(cand1==tmpNum){
count1++;
continue;
}
if(cand2==tmpNum){
count2++;
}
}
if(count1>nums.size()/3) Ans.push_back(cand1);
if(count2>nums.size()/3) Ans.push_back(cand2);
return Ans;
}
};
4待续
5待续
刷题总结类 文章被收录于专栏
这里记录一些刷题时候的总结思考
投递美团等公司10个岗位 >