腾讯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) 回帖