20210313美团笔试总结

总结：

听同学说，只要提交了有AC百分之多少，就会有相应的分数，下次一定要及时提交，然后再优化使其达到AC100%；
对于输入输出的操作还不太熟悉，这也难怪，之前都是使用LeetCode，突然转换到类似牛客的这种方式，不太习惯
总共5道编程题，其实不用太赶，第一次过于谨慎，过于紧张了
一共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;
    }
};