腾讯笔试题目2020-09-06原始代码

01.腾讯笔试常考

以秋招5题为例

以前刷的时候，大概经验是“动态规划”必考，模拟会考
贪心似乎也是。

数据结构（只学学校教的是不够的）

1）单调栈
2）单调队列
3）并查集

1）（AC）链表的公共部分

降序

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int val;
    node * next;
    node(int num): val(num)
    {
        next=NULL;
    }
};



int main()
{
    int n,m;
    while(~scanf("%d",&n))
    {

        int One=n;

        int tag=0;
        //遍历用 
        node * rootOne=new node(-1);

        //建表使用 
        node * prev=rootOne;
        node * p=NULL;

        while(n--)
        {
            int temp;
            scanf("%d",&temp);
            if(0==tag)
            {
                rootOne->val=temp;
                tag=1;

            }
            else
            {
                p=new node(temp);
                prev->next=p;

                prev=prev->next;
                p=NULL;
            }

        }


        int m;
        scanf("%d",&m);

        int two=m;

        tag=0;
        //遍历用 
        node * rootTwo=new node(-1);

        //建表使用 
        node * prev2=rootTwo;
        node * p2=NULL;

        while(m--)
        {
            int temp;
            scanf("%d",&temp);
            if(0==tag)
            {
                rootTwo->val=temp;
                tag=1;
            }
            else
            {
                p2=new node(temp);
                prev2->next=p2;

                prev2=prev2->next;
                p2=NULL;
            }

        }

//        while(NULL!=rootTwo)
//        {
//            printf("%d\n",rootTwo->val);
//            rootTwo=rootTwo->next;
//        }

        while(NULL!=rootOne&&(NULL!=rootTwo))
        {
            if(rootOne->val==rootTwo->val)
            {
                printf("%d ",rootOne->val);
                rootOne=rootOne->next;
                rootTwo=rootTwo->next;
                continue; 
            }

            if(rootOne->val>rootTwo->val)
            {
                rootOne=rootOne->next;
                continue; 
            }

            if(rootOne->val<rootTwo->val)
            {
                rootTwo=rootTwo->next;
                continue; 
            }
        }


    }

    return  0;    
}

2）（AC）组别通知吧。。。哈希

#include<bits/stdc++.h>
using namespace std;

//本想用并查集，但是还是_hash好写 


const int one=100000+5;
const int two=505;

//有哪些数字i表示数字，_hash[1]表示这个数字在多少个组中。 
int _hash[one][2];


//编号为i的组是否被计算进来，0表示没有，1表示有 
bool group[two];

int solve[two][105];


int have(int hang,int num)
{
    for(int i=0;solve[hang][i]!=0x3f3f3f3f;++i)
    {
        if(num==solve[hang][i])
        {
            return 1;//表示有 
        }
    }

    return 0; 
}

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(_hash,0,sizeof(_hash));
        //本组没有被遍历完 
        memset(group,0,sizeof(group));
        memset(solve,0x3f,sizeof(solve));



        int tag=0;//还没有找到0
        int zu=-1;//首先在第几组中找到了0；

        for(int i=0;i<m;++i)
        {
            int num;
            scanf("%d",&num);
            for(int j=0;j<num;++j)
            {
                scanf("%d",&solve[i][j]);

                if((0==tag)&&(0==solve[i][j]))
                {
                    zu=i;
                    tag=1;
                }
                //加一组 
                _hash[ solve[i][j] ][1]++;
            } 

        }



        if(0==tag)
        {
            printf("0\n");
            continue;
        }


        vector<int> vect;
        vect.push_back(0);

        //标记这个组,并且对应数字的组别减少 
        group[zu]=1;
        _hash[0][1]--;


        for(int i=0;solve[zu][i]!=0x3f3f3f3f;++i)
        {
            _hash[solve[zu][i]][1]--;
            vect.push_back(solve[zu][i]);
        }


        //最终答案 
        int sum=0;

        //当还没有空 
        while(vect.size())
        {
            int len=vect.size();

            if(_hash[ vect[len-1] ][1]<=0)
            {
                if(0==_hash[ vect[len-1] ][0]) 
                {
                    //表示第一次被筛 
                    ++sum;
                    _hash[ vect[len-1] ][0]=1; 
                }

                vect.pop_back();


                if(0==vect.size())
                {
                    break;
                }

                continue;
            }


            for(int i=0;i<m;++i)
            {
                //还没有被访问 
                if(false==group[i])
                {
                    //如果有 
                    if(1==have(i,vect[len-1]))
                    {
                        group[i]=true; 
                        _hash[ vect[len-1] ][1]--;


                        for(int jj=0;solve[i][jj]!=0x3f3f3f3f;++jj) 
                        {
                            _hash[solve[i][jj]][1]--;
                            vect.push_back(solve[i][jj]);
                        }
                    }
                }
            }
        }


        printf("%d\n",sum); 
    }


    return 0;
 } 

3）字符串次数（最后几分钟，想出来了）

#include<bits/stdc++.h>
using namespace std;

int main()
{

    int n,k;
    while(~scanf("%d%d",&n,&k))
    {
        vector<pair<string,int> > solve(n);

        int num=n;

        while(n--)
        {
            pair<string,int> temp;
            cin>>temp.first;
            temp.second=1;
            solve[n]=temp;
        }

        sort(solve.begin(),solve.end());

        //合并 
        for(int i=num-1;i>=1;i--)
        {
            if(solve[i].first==solve[i-1].first)
            {
                solve[i-1].second=solve[i-1].second+1;
                solve.erase(solve.begin()+i);
            }

            sort(solve.begin(),solve.end());
        }


        //上面处理好了，fisrt表示出现次数，sort给我们排序好了 
        //没写完，统计就好了
        int len=solve.size();



        //前面还需要处理------ 
        //输出最多的k个 
        for(int i =len-1; i>len-1-k; --i) 
        {
            cout<<solve[i].second<< " " <<solve[i].first<< endl;
        }

        //输出最少的k个 
        for(int i = 0;i < k; ++i) 
        {
            cout<<solve[i].second<< " " <<solve[i].first<< endl;
        }

    }


    return 0;
}

4）（Ac）中位数（最水）

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+3;

int solve[maxn];
int temp[maxn];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {

        if(n<2)
        {
            printf("0\n");
        }

        for(int i=0;i<n;++i)
        {
            scanf("%d",&solve[i]);
            temp[i]=solve[i];
        }
        sort(solve,solve+n);

        int leftNum=solve[n/2-1];
        int rightNum=solve[n/2];

        for(int i=0;i<n;++i)
        {
            if(temp[i]<=leftNum)
            {
                printf("%d\n",rightNum);
            }
            else if(temp[i]>=rightNum)
            {
                printf("%d\n",leftNum);
            }
        }
    }

    return 0;
 } 

5）红黑棋（动态规划/贪心，我还没有时间去做）

三、秋招笔试的教训

腾讯的笔试给我教训

1）一定要先想好再写出来，不要边想边写！！！
比如，第2题，我最终能AC也是因为这个

第4题最终没来得及AC也是因为这个

2）set好像不熟练，体现在字典序哪里，大概是pair放到set中不会find

string的substr还有find啥不熟练