腾讯软件后台开发0426笔试-超详细题目+C++实现
总体感受
成绩还算满意，100+60+0+100+100，两道数据结构的题都比较基础，欢迎指正和参考🤣
题目1：模拟队列
我老老实实用的链表实现，花了我三十分钟，我当场裂开……
输入样例：
第一行输入样例数T，之后每个样例，先输入操作数Q，然后进行"PUSH", "TOP", "POP", "SIZE","CLEAR"五种操作。
输出样例：
"TOP"输出队头元素，队伍空返回-1；"POP"失效时输出-1。
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
struct node{
int val;
node* next;
node(int x):val(x),next(nullptr) {}
};
class myQueue{
public:
myQueue(){
dummyNode=new node(0);
length=0;
}
~myQueue(){
delete dummyNode;
dummyNode=nullptr;
length=0;
}
void push(int x){
node* lastNode=dummyNode;
while(lastNode->next){
lastNode=lastNode->next;
}
node* newNode=new node(x);
lastNode->next=newNode;
length++;
}
void top(){
if(length==0){
printf("%d\n",-1);
}
else{
printf("%d\n",dummyNode->next->val);
}
}
void pop(){
if(length==0){
printf("%d\n",-1);
}
else{
node* head=dummyNode->next;
dummyNode->next=head->next;
delete head;
length--;
}
}
void size(){
printf("%d\n",length);
}
void clear(){
delete dummyNode->next;
dummyNode->next=nullptr;
length=0;
}
private:
node* dummyNode;
int length;
};
int main(){
int T;
scanf("%d",&T);
for(int i=0;i<T;i++){
myQueue q;
int Q;
scanf("%d", &Q);
for(int j=0;j<Q;j++){
string s;
//s.resize(4);
//scanf("%s",&s[0]);
cin>>s;
//cout<<s<<endl;
if(s=="PUSH"){
int i;
scanf("%d",&i);
q.push(i);
}
else if(s=="TOP"){
q.top();
}
else if(s=="POP"){
q.pop();
}
else if(s=="SIZE"){
q.size();
}
else if(s=="CLEAR"){
q.clear();
}
}
}
return 0;
} 题目2：求两个点集合的最短距离
给定两个相同规模的点集合（大小为n），计算集合间的最低距离。这里的距离是欧式距离，然后暴力枚举的，通过60%。希望AC的朋友指点下本弱鸡，之后会更新AC答案的，感谢~ 输入样例：
第一行输入集合规模n，然后输入集合A和B的点坐标，每行是点的横坐标和纵坐标，先输入A再输入B
例如:
4
0 1
1 1
1 0
1 1
2 2
2 3
3 2
3 3
输出样例：两个集合间的最短距离
例如：上样例中，集合A的[1,1]和集合B的[2,2]距离最短，距离是1.414(保留三位小数)
#include <stdio.h>
#include <vector>
#include <cmath>
using namespace std;
vector<int> ax;
vector<int> ay;
vector<int> bx;
vector<int> by;
inline double calDist(int a, int b){
return sqrt(pow(ax[a]-bx[b],2)+pow(ay[a]-by[b],2));
}
int main(){
int N;
scanf("%d",&N);
for(int i=0;i<N;i++){
int n;
scanf("%d", &n);
ax.assign(n,-1);
ay.assign(n,-1);
bx.assign(n,-1);
by.assign(n,-1);
for(int j=0;j<n;j++){
scanf("%d %d", &ax[j], &ay[j]);
}
for(int j=0;j<n;j++){
scanf("%d %d", &bx[j], &by[j]);
}
double dist=calDist(0,0);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
double tmp=calDist(i,j);
if(tmp<dist) dist=tmp;
}
}
printf("%.3f\n", dist);
}
} 4月28日更新：
在ACWING上找到原题，并参考了一位大佬的思路（分治+二分），他的讲解十分清晰，链接是：https://www.acwing.com/solution/acwing/content/826/
自己重写了一遍代码，如下：
#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
#define INF 1e8
struct point{
double x,y;
int f; // 集合
} P[N], T[N];
bool comp1(point a, point b){ // 根据x优先排序
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
bool comp2(point a, point b){ // 根据y优先排序
if(a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
double dist(point a,point b){
if(a.f==b.f) return INF; // 同种类，距离设为INF
double x2=(a.x-b.x)*(a.x-b.x);
double y2=(a.y-b.y)*(a.y-b.y);
return sqrt(x2+y2);
}
double minDist(int l,int r){
if(l==r) return INF;
if(l+1==r) return dist(P[l],P[r]);
int m=(l+r)>>1;
double ans=min(minDist(l,m),minDist(m+1,r)); // 分治左右平面的最短距离
// 寻找中间距离
int cnt=0;
for(int i=l;i<=r;i++){
if(abs(P[m].x-P[i].x)<=ans) T[++cnt]=P[i]; // 排除离平面分界线过远的点
}
sort(T+1,T+1+cnt,comp2);
for(int i=1;i<=cnt;i++){
for(int j=i+1;j<=cnt;j++){
if(T[j].y-T[i].y>=ans) break; // 根据y坐标剪枝
ans=min(ans,dist(T[i],T[j]));
}
}
return ans;
}
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int i;
for(i=1;i<=n;i++){
cin>>P[i].x>>P[i].y;
P[i].f=0;
}
for(i=n+1;i<=n<<1;i++){
cin>>P[i].x>>P[i].y;
P[i].f=1;
}
sort(P+1,P+1+(n<<1),comp1);
printf("%0.3lf\n", minDist(1,n<<1));
}
} 题目3：翻转卡片
n张卡片排成一行，每张卡片的正面和背面均有数字，一开始所有卡片正面朝上。有一种操作是将相邻卡片交换位置，并且两张卡片翻面。求这种操作的最少次数，使得卡片所显示的、排成一行的数字能够实现非严格递增排序。如果不存在这个最少次数，则返回-1。我总感觉像是冒泡排序，但死活没想出来，希望AC的朋友指点下本弱鸡，之后会更新AC答案的，感谢~ 输入样例：
第一行是卡片数（n<=18）
第二行是卡片正面数字的数组
第三行是卡片背面数字的数组
例如：
3
1 3 2
3 2 1
输出样例：
1 （操作的最少次数，不能实现则为-1）
题目4：两个栈模拟队列
《剑指offer》里的第九题：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/，大体思路是两个栈分别扮演队列的队头和队尾，入队操作在队尾栈里，出队和检查队头在队头栈中，中途要维护队尾栈向队头栈的元素转移。
输入样例：
第一行是操作数N
之后有N行操作，有“add”，“peek”和“poll”三种操作
输出样例：
“peek”操作需输出队头元素
#include <stdio.h>
#include <iostream>
#include <stack>
using namespace std;
//int add_pos=0;
void add(stack<int>& stack1, stack<int>& stack2, int i){
stack1.push(i);
}
void peek(stack<int>& stack1, stack<int>& stack2){
if(stack2.empty()){
if(stack1.empty()) return;
while(!stack1.empty()){
int tmp=stack1.top();
stack1.pop();
stack2.push(tmp);
}
}
printf("%d\n", stack2.top());
}
void poll(stack<int>& stack1, stack<int>& stack2){
if(stack2.empty()){
if(stack1.empty()) return;
while(!stack1.empty()){
int tmp=stack1.top();
stack1.pop();
stack2.push(tmp);
}
}
stack2.pop();
}
int main(){
stack<int> stack1,stack2;
int N;
scanf("%d", &N);
for(int i=0;i<N;i++){
string s;
cin>>s;
if(s=="add"){
int i;
scanf("%d", &i);
add(stack1,stack2,i);
}
else if(s=="peek"){
peek(stack1,stack2);
}
else if(s=="poll"){
poll(stack1,stack2);
}
}
return 0;
} 题目5：满二叉树的祖先节点
有一个无穷高的满二叉树，层次遍历从小到大编号，根结点从1开始，第二行是“2 3”，第三行是“4 5 6 7”……对于编号为n的结点，求其高度为k的祖先节点，若不存在则返回-1. 思路：满二叉树的层级编号是一个很经典的问题，编号为n的节点的父结点编号是n>>1，祖父节点编号是n>>2……以此类推。另外，树高为k的节点编号范围是[2^(k-1), 2^k)，所以编号为n的节点的树高为⌊log2(n)⌋+1，进而当k>=⌊log2(n)⌋+1时，不存在该祖先节点。
输入样例：
第一行是检索数Q
下面Q行的检索中，每一行包含节点编号i和祖先节点高度k
例如：
4
10 1
10 2
10 3
10 4
输出样例：
每行检索对应的祖先节点编号
例如：
1
2
5
-1
#include <stdio.h>
using namespace std;
int calHeight(long long x){
int height=1;
long long tmp=1;
while(1){
if(x>=tmp && x<(tmp<<1)) break;
height++;
tmp=tmp<<1;
}
return height;
}
int main(){
int Q;
scanf("%d",&Q);
for(int i=0;i<Q;i++){
long long x;
int k;
scanf("%lld %d", &x, &k);
int height=calHeight(x);
if(k>=height) printf("%d\n", -1);
else{
long long ret=x>>(height-k);
printf("%lld\n", ret);
}
}
} 另外，弱鸡的我求教下各位C++的格式输入/输出到底怎样规范操作？我经常将scanf和cin混用，也经常碰到一些输入/输出样例处理的bug，各位收藏过整理这些输入/输出的网站吗？谢谢
