腾讯C++后台笔试复盘
假设本套题难度从简单到难1->5星
非科班人员,难度是个人臆断,巨佬轻拍
尽量回忆题目,复盘当时想法
一、链表的公共部分(2星)
1)[题目描述]
两个链表都是"降序"(突破点),用“双指针”遍历 请根据n和m建链表,输出公共的节点 //n和m的大小最大好像是这么大把,我是看着开不了那么大数组才建的链。 //不然,我就用数组模拟了 1<=n<=10000000 1<=m<=10000000 比如样例 输入: 6 6 5 4 3 2 1 5 6 5 3 2 1 输出: 6 5 3 2 1
2)考点+解法
考点:链表+模拟
解法:建链表+遍历
3)代码
#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)) { //1.建节点数为n的链表 //tag用来标记最开始的root节点有没有被处理 int tag=0; node * rootOne=new node(-1); //建表使用,prev表示前一个节点,p表示当前节点 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; } } //2.建节点数为m的链表 int m; scanf("%d",&m); //tag用来标记最开始的root节点有没有被处理 tag=0; node * rootTwo=new node(-1); //建表使用,prev2表示前一个节点,p2表示当前节点 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!=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; }
4)复盘后反省
1.代码简洁性:上面建链表可以抽象为一个函数,代码写的不够简洁。
2.变量命名:长度为m的链表的建立,变量命名需要改为更加容易区分的。
二、大概意思是“能获得消息的人数”(4星)
1)[题目描述]
1<=n<=100000个人 m<=500个团队(团队编号从0-(m-1)) 每个团队一些人<=100 告诉消息给0,和0一个组的也会知道 然后这个组的人,由于可能同时在其他组。 消息会通过他们传递,问最终,n个人中有多少个人知道消息。
2)考点+解法
考点:
第一眼看觉得是“裸”的“并查集”
然后感觉DFS也行
但是,自己懒。。最后用哈希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]; //遍历第hang组中是否有数字num,有则返回1 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; }
4)复盘后反省
1.变量命名:考试的时候,注意规避了命名为hash,但是_hash“下划线命名”其实考试的时候前面那个下划线,干扰过自己,以后还是改为“驼峰命名法”吧
2.先算法再编码:一定要先想好算法再编码,“磨刀不误砍柴工”
3.关于一题多解:自己想到过用“并查集”/DFS/哈希来做,考试的时候犹豫过用哪种解法。
虽然最终选择的哈希,但老实说,选择哪种解法耗费了很多时间,归根到底,还是要强化自己数据结构的熟练程度。
4.吐槽...这题代码真心写得太丑了...
三、字符串个数(3星)
1)[题目描述]
查找k个高频率和k个最低频率的字符串以及出现的次数 数据量n最大1e5, 总的字符串长度和<=100000
2)考点+解法
考点:字典序排序+模拟
解法:用pair+vector+排序+合并
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(); //输出 } return 0; }
四、中位数(1星)
1)[题目描述]
首先输入n(n保证是“偶数”),然后给你n个数字 如果删除一个元素,求其余的n-1个数的中位数 样例: 输入: 4 2 3 1 4 输出: 3 2 3 2 //解释: 删掉2,那么剩下1,3,4中位数是3 删掉3,那么剩下1,2,4中位数是2 删掉1,那么剩下2,3,4中位数是3 删掉4,那么剩下1,2,3中位数是2
2)考点+解法
考点:排序+思维
解法:排序+准备左边和右边两个“哨兵”
3)代码
#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)) { //代码健壮性,但是其实笔试题,知道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; }
4)复盘后总结
1.原来笔试的题目,难度并一定按照1->5的顺序排布的..
五、红黑棋(5星)
1)[题目描述]
红色和黑色两种棋子,编号都是1-n 需要将最终结果排序为,红色整体升序,黑色整体升序 比如R1 B1 B2 R2 R3 B3是可以的 输入n,然后 第1行输入2*n个颜色,R红***黑色 第2行输入2*n个数字编号 样例 输入: 3 RBBRRB 1 1 3 3 2 2 输出: 4 //解释 原始的:R1 B1 B3 R3 R2 B2 第1步:R1 B1 B3 R3 [B2] [R2] 第2步:R1 B1 B3 [B2] [R3] R2 第3步:R1 B1 [B2] [B3] R3 R2 第4步:R1 B1 B2 B3 [R2] [R3] 完成
2)考点+解法
考点:大概是“动态规划”?还是“贪心”
对这题感觉朦胧的
第一眼,想到的是先用“双指针”弄好一种颜色的顺序,大概是想的“贪心”
但是不敢确定,算法的正确性,转向写前面的
全部评论
(4) 回帖