首页 > 腾讯软件后台开发0426笔试-超详细题目+C++实现
头像
KeviNCode
编辑于 2020-04-28 16:50
+ 关注

腾讯软件后台开发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,各位收藏过整理这些输入/输出的网站吗?谢谢

全部评论

(7) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐