腾讯4.26笔试

腾讯4.26笔试题目

代码是整理其他牛友说自己ac了的题，侵删。
第一题：模拟队列操作

数据结构基础之一一队列
队列有五种基本操作，插入队尾、取出队首、删除队首、队列大小、清空队列。
现在让你模拟一个队列的操作，具体格式参考输入。
输入描述:
第一行输入一个整数T，表示接下来有T组测试数据。
对于每组测试数据:
第一行输入一个整数Q，表示有Q次操作。
接下来Q行，每行输入一种队列操作方式，具体格式如下:
初始状态下队列为空。
插入队尾: PUSH X
取出队首: TOP//仅仅是看一下队首元素，不要把队首元素删除
删除队首: POP
队列大小: SIZE
清空队列: CLEAR
1<T<100
1<Q,X≤1000
保证操作为以上5种的任意一种。

输出描述

对于每组测试数据:
如果操作为“取出队首”，输出队首元素，如果无法取出，输出“-1”
如果操作为“删除队首”，如果无法删除，输出“-1”
如果操作为“队列大小”，输出队列大小
其他操作无需输出

示例输入

2
7
PUSH 1
PUSH 2
TOP
POP
TOP
POP
POP
5
PUSH 1
PUSH 2
SIZE
POP
SIZE

1
2
-1
2
1

代码

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for (int i = 0; i < T; i++) {
        Queue<Integer> queue = new LinkedList<Integer>();
        int Q = sc.nextInt();
        for (int j = 0; j < Q; j++) {
            String str = sc.next();
            if (str.equals("PUSH")) {
                int num = sc.nextInt();
                queue.offer(num);
            }else if (str.equals("TOP")) {
                if (queue.size() > 0) {
                    System.out.println(queue.peek());
                }else {
                    System.out.println(-1);
                }
            }else if (str.equals("POP")) {
                if (queue.size() > 0) {
                    queue.remove();
                }else {
                    System.out.println(-1);
                }
            }else if (str.equals("SIZE")) {
                System.out.println(queue.size());
            }else if(str.equals("CLEAR")) {
                queue.clear();
            }
        }
    }
    sc.close();
}

第二题:集合间的最短距离

小Q在平面上给定了2 *n个点，这些点n个属于A集合，n个属于B集合，现在让你在A集合和B集合中各选择一个点，求所有可能中两个点的最短距离为多少?
这里的距离指的是欧氏距离，对于点(x1, y1), (x2, y2)他们的欧式距离为:

输入描述：

第一行输入一个整数n,代表A集合和B集合内的点的数量为n。
接下来n行，每一行2个数x和y,代表A集合内的点的坐标
接下来n行，每一行2个数x和y,代表B集合内的点的坐标
1<n<100000
1 ≤ x,y≤10^9

输出描述:

对于每组数据，输出一个答案代表最短距离，结果保留3位小数。

//输入数据示例
2
4
0 0
0 1
1 0
1 1
2 2
2 3
3 2
3 3
4
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
//输出数据示例
1.414
0.000

第三题:集合间的最短距离

有n张卡牌，第i张牌正面为反面为，n张牌排成一行，一开始全部正面朝上，现在可以执行若干次操作，每次操作可以选择相邻的两张牌，先交换它们的顺序，再翻转它们，求最少的操作次数，能使得牌上的数字从左到右非降。
输入描述:
第一行输入一个正整数表示n(n≤18),第二行n个整数表示序列a,第三行n个整数表示序列b。
输出描述:
输出一个数字表示答案，无解输出-1

//输入示例
3
1 3 2
3 2 1
//输出示例
1

void swap(vector<int>&a, vector<int>& b, int i) {
    swap(a[i - 1], b[i]);
    swap(a[i], b[i-1]);
}
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            int min_i1 = 99999, min_i = 99999;
            if (i + 1 < n && b[i + 1] <= b[i] && b[i + 1] >= a[i - 1]) 
            {     
                    min_i1 = b[i + 1];
            }
            if (b[i] <= b[i - 1]) {

                min_i = b[i - 1];
            }
            else {
                cout << -1;
                return 0;
            }
            if (min_i1 < min_i) {
                swap(a, b, i + 1);
                cnt++;
            }
            else {
                swap(a, b, i); cnt++;
            }
        }
    }

    cout << cnt;
    return 0;
}

第四题：两个栈实现队列

用两个栈实现队列，支持队列的基本操作。
输入描述:
第一行输入一个整数N，表示对队列进行的操作总数。下面N行每行输入一个字符串S，表示操作的种类。
如果s为"add"，则后面还有一个整数x表示向队列尾部加入整数X。
如果S为"poll"，则表示弹出队列头部操作。
如果s为"peek"，则表示询问当前队列中头部元素是多少。
1 < N< 1000000, -1000000 < X < 1000000
数据保证没有不合法的操作。
输出描述:
对于每一个为"peek"的操作，输出一行表示当前队列中头部元素是多少。

//输入示例
6
add 1
add 2
add 3
peek
poll
peek
//输出示例
1
2

第五题：第k层祖先

给你一棵无限深度的满二叉树，节点的编号按层次依次编号，即第-层节点编号为1，第二层节点编号为2,3,
第三层节点编号为4,5, 6...以此类推。
接下来有Q次询问，每-一次询问让你找一 个编号为x的结点在深度为k的祖先节点的编号是多少?
输入描述:
输入第一行一个整数Q,代表有Q次询问
接下来Q行，每一行输入两个数x和k。
1<Q≤
1<x<
1<k<60
输出描述:
对于每一组测试数据，如果深度为K的祖先存在，输出
结点编号，不存在输出-1

//输入示例
4
10 1
10 2
10 3
10 4
//输出示例
1
2
5
-1

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int Q = sc.nextInt();
    for (int i = 0; i < Q; i++) {
        long x = sc.nextLong();
        int k = sc.nextInt();
        System.out.println(getFather(x,k));
    }
    sc.close();
}

//找父节点
public static long getFather(long x,int k){
    int nowDeep = getDeep(x);
    if (k >= nowDeep) {
        return -1;
    }
    //一层层往上找父节点，总共需要计算nowDeep - k次
    for (int i = 0; i < nowDeep - k; i++) {
        if (x % 2 == 0) {
            x = x >> 1;
        }else {
            x = (x - 1) >> 1;
        }
    }
    return x;
}

//计算当前节点x的所在层数
public static int getDeep(long x){
    int deep = 0;
    long i = 1;
    while(i <= x){
        i <<= 1;
        deep++;
    }
    return deep;
}