#腾讯笔试# 软件开发岗位 4月26笔试部分题解

100， 0， 0， 100， 100
第一题：实现队列操作，输入“PUSH”时，将数插入队尾；输入“TOP”时，输出队首；输入“POP”时，弹出队首；输入“SIZE”，输出队列长度；输入“CLEAR”，清空队列
一开始用队列超时了，就换成了数组AC了

#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    int t,n,x;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int a[1005],len = 0,top = 0;
        while(n--){
            string s;
            cin >> s;
            if(s == "PUSH"){
                cin >>x;
                a[len++] = x;
            }
            else if(s == "TOP") {
                if(len == 0) {
                    printf("-1\n");
                    top = 0;
                }
                else printf("%d\n",a[top]);
            }
            else if(s == "POP"){
                if(len == 0) {
                    printf("-1\n");
                    top = 0;
                }
                else top++;
            }
            else if(s == "SIZE") printf("%d\n",len-top);
            else if(s == "CLEAR") {
                len = 0;
                top = 0;
            }
            if(len == top){
                len = 0;
                top = 0;
            }
        }
    }
    return 0;
}

第二题：输入n，A集合中有n个点的坐标；B集合中有n个坐标，求A集合中某个点和B集合中的某个点之间的最小距离，即sqrt ( (x1-x2)^2+(y1-y2)^2 )最小

没整出来....

第三题：题都没来及看

第四题：跟第一题类似，只是没有了清空队列，和求队列的长度，直接用队列A的

#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    int n,x;
    scanf("%d",&n);
    queue<int> q;
    while(n--)
    {
        string s;
        cin >> s;
        if(s == "add")
        {
            cin >>x;
            q.push(x);
        }
        else if(s == "peek")
        {
            if(q.empty()) printf("\n");
            else printf("%d\n",q.front());
        }
        else if(s == "poll")
        {
            if(!q.empty()) q.pop();
        }
    }
    return 0;
}

第五题：求二叉树中x个节点的k深度的祖父节点（二叉树中第一层为1，第二层为2,3第三层为4,5,6,7....以此类推）
AC，除以2就行了，不会超时，因为辣个K的取值其实就提示我们了，2的60次方差不多就是10的18次方，然后总的时间复杂度下来，也就10^4 * 60

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
 
 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        while (q > 0) {
            long x = in.nextLong();
            int k = in.nextInt();
            if(x == 1) {
                System.out.println(-1);
            }else {
                int deep = 0;
                for (double i = 1; i < 65; i++) {
                    if (x < Math.pow(2, i)) {
                        deep = (int)i;
                        break;
                    }
                }
                if(k >= deep) {
                    System.out.println(-1);
                }else {
                    int len = deep-k;
                    while (len > 0) {
                        x = x>>1;
                        len--;
                    }
                    System.out.println(x);
                }
            }
            q--;
        }
    }
}

#腾讯笔试##腾讯##笔试题目#

全部评论

推荐最新楼层

霓虹灯亮

西南财经大学 C++

第二题感觉排序好像可以，把a和b的两个集合合在一起，然后分维度排序。然后找中间的那个两个点，不晓得对不对。

点赞回复分享

发布于 2020-04-26 22:50

Dyswan

广东外语外贸大学 C++

第三题应该是状态压缩动态规划，我距离函数没调好才过40%... dp[j][state]=min{ state二进制下第i位为1 |dp[i][state^(1<<j)]}

点赞回复分享

发布于 2020-04-26 22:50

Dyswan

广东外语外贸大学 C++

第五题做法可以到O(log(n)) ``` #include<bits/stdc++.h> using namespace std; int main(){ long long n,m,T; cin>>T; while(T--){ cin>>n>>m; ll dep=0,tmp=n; while(tmp){ tmp>>=1; dep++; } if(m>=dep){ cout<<"-1\n"; }else{ cout<<(n>>(dep-m))<<"\n"; } } return 0; } ```

点赞回复分享

发布于 2020-04-26 22:53

StupidLee

中南大学 Java

搓逼的第五题做法 #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> using namespace std; typedef long long ll; const int maxn = 100000 + 5; ll a[maxn]; int main(){ //cout<<log2(100000000000000000)<<endl; int t,k; ll x; scanf("%d",&t); while(t--){ scanf("%lld%d",&x,&k); int cnt = log2(x); if(k > cnt){ printf("-1\n"); } else{ int t = 0; while(x > (ll)0){ if(x % (ll)2 == 0){ //cout<<x / (ll)2<<endl; a[t ++] = x / (ll)2; //cout<<a[t - 1]<<endl; x /= (ll)2; } else{ a[t ++] = (x - (ll)1) / (ll)2; x = (x - (ll)1) / (ll)2; } } printf("%lld\n",a[t - k - 1]); } } return 0; }

点赞回复分享

发布于 2020-04-26 22:55

有空视奸我不去多做几道笔试题

腾讯_PCG视频平台技术部_研发工程师

第五题解法 100% public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); List<Long> res = new ArrayList<>(); for (int i = 0; i < n; i++) { Long x = sc.nextLong(); int level = sc.nextInt(); if(level == 1){ res.add(1L); continue; } if(Math.pow(2,level) > x){ res.add(-1L); continue; } while(!((x < Math.pow(2,level)) && x >= Math.pow(2,level -1))){ x = x>>1; } res.add(x); } for (int i = 0; i < res.size(); i++) { System.out.println(res.get(i)); } } }

点赞回复分享

发布于 2020-04-26 22:58

OneSeek

山东农业大学 Java

第四题不是说用栈模拟队列吗

点赞回复分享

发布于 2020-04-26 23:02

FrozenHeart

门头沟学院 C++

100 60 100 100 100 第一题 int main() { int t; cin >> t; for (int i = 0; i < t; i++) { int n; cin >> n; cin.ignore(20, '\n&(392)#39;); string line; queue<int>temp; for (int j = 0; j < n; j++) { getline(cin, line); if (line.find("PUSH") != -1) { int num = stoi(line.substr(5, line.length())); temp.push(num); } else if (line.find("TOP") != -1) { if (temp.empty()) { cout << -1 << endl; } else { cout << temp.front() << endl; } } else if (line.find("POP") != -1) { if (temp.empty()) { cout << -1 << endl; } else { temp.pop(); } } else if (line.find("SIZE") != -1) { cout << temp.size() << endl; } else if (line.find("CLEAR") != -1) { while (!temp.empty()) { temp.pop(); } } } } return 0; }

点赞回复分享

发布于 2020-04-26 23:16