百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 技术文章 > 正文

腾讯2020校园招聘(后台)算法编程题合集

haoteby 2025-02-26 12:14 14 浏览

腾讯2020校园招聘算法题,“压缩字符串”和“逛街”

总体来说,腾讯2020年的校园招聘职位相对较多,5道题目中主要考察了学生的算法基础与正则表达式的运用。

我这边抽出了前2道题跟大家分享,第一道题和昨晚字节跳动的题目类似,都可以使用正则表达式来做。第二道题用分治的方式也非常简单

[编程题一]压缩算法

输入描述:

输入第一行包含一个字符串s,代表压缩后的字符串。
S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;

输出描述:

输出一个字符串,代表解压后的字符串。

输入例子1:

HG[3|B[2|CA]]F

输出例子1:

HGBCACABCACABCACAF

例子说明1:

HG[3|B[2|CA]]F?>HG[3|BCACA]F?>HGBCACABCACABCACAF

详细解答

//JAVA版本
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Main main = new Main();
        String line = sc.nextLine();
        StringBuilder sb = new StringBuilder(line);
        main.decode(sb);
        System.out.println(sb.toString());
    }
     
    private void decode(StringBuilder string){
        int i=0;
        int start=-1, mid=-1, end=-1;
        while(i
#include 
 
using namespace std;
 
int main(){
    string s;
    cin >> s;
    int i = 0;
    while(i < s.length()){
        if(s[i] == ']'){
            int j =i; 
            int k = 0;
            while(s[j] != '['){
                if(s[j] == '|')
                    k = j;
                j--;
            }
            int len = stoi(s.substr(j+1, k-j-1));
            string s1 = s.substr(k+1, i-k-1);
            string s2;
            for(int si =0; si 


【编程题二】逛街

输入描述:

输入第一行将包含一个数字n,代表楼的栋数,
接下来的一行将包含n个数字wi(1<=i<=n),代表每一栋楼的高度。
1<=n<=100000;
<=wi<=100000;?

输出描述:

输出一行,包含空格分割的n个数字vi,分别代表小Q在第i栋楼时能看到的楼的数量。

输入例子1:

6
5 3 8 3 2 5

输出例子1:

3 3 5 4 4 4

例子说明1:

当小Q处于位置3时,他可以向前看到位置2,1处的楼,
向后看到位置4,6处的楼,加上第3栋楼,那小Q一共能够看到5栋楼(2,1,3,4,6)。
当小Q处于位置4时,他可以向前看到位置3处的楼,向后看到位置5,6处的楼,
加上第4栋楼,共可看到4栋楼(3,4,5,6)。

详细源码:

//JAVA 使用栈实现,非常简单
//用栈两个方向分别遍历一次,最后相加,时间复杂度为O(n);
import java.util.Stack;
import java.util.Scanner;
public class Main{
    public void street(int num, int[] build){
        int[] res = new int[num];
        Stack sl = new Stack<>();
        //从前向后遍历,相当于每个楼往右边能看到几个
        for(int i=0; i sr = new Stack<>();
        //从后向前遍历,相当于每个楼往左边能看到几个
        for(int i=num-1; i>=0; i--){
            res[i] += sr.size();
            //维护栈,为一个楼做准备
            while(!sr.isEmpty() && sr.peek()<=build[i]) sr.pop();
            sr.push(build[i]); //当前楼一定能被下一个楼看见
        }
        for(int a : res) System.out.printf("%d ",a);
    }
    public static void main(String[] args){
        Main m = new Main();
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] build = new int[num];
        int i = 0;
        while(sc.hasNextInt()) build[i++] = sc.nextInt();
        m.street(num,build);
    }
}

//Python详细注释版本,代码中保留了调试过程中的一些输出,大家代码如果读起来有困难可以跟着调试
// # -*- coding:utf-8 -*-
// 单调栈进攻!!
import sys
n = int(sys.stdin.readline().strip())
l = list(map(int, sys.stdin.readline().strip().split()))
def handle(house):
    // 设置栈,储存往回看能看到的楼的高度
    //设置结果,储存每栋楼往回看能看到几个
    stack , res = [house[0]] , [0]*n
    // 然后对这个栈
   // 进行循环,每检查一栋楼都是酸这栋楼往回看能看到几栋
    for i in range(1,n):
        res[i] = len(stack)
        //print(i,'th now res is ',res)
        //只要这栋楼比stack里面的最后一个比,如果最后一个大或者等于就把stack[-1]删掉,一直比
       // 直到没问题。
        if stack[-1] <= house[i]:
            while stack and stack[-1] <= house[i]:
                //print('stack last one is ',stack[-1],' smaller than ',i,'th house')
                //print("now stack pop this one ",stack[-1])
                stack.pop(-1)
                // print('stack is now ',stack)
            stack.append(house[i])
            //print('stack append new house ',house[i],' and stack is now ',stack)
            continue
        // 小于等于的话就直接加进去,保证单调性
        //print('stack last one bigger than ',i,' th house so append')
        stack.append(house[i])
        //print('stack is now ',stack)
    // print('res is ',res)
    return res
resA = handle(l)
resB = handle(l[::-1])[::-1]
print(  " ".join(list(map(str, [resA[i] + resB[i] + 1 for i in range(n)]))))

总结

腾讯的校招算法题还是相对较简单,只要认真学习了数据结构与算法的朋友应该都能轻松过关。无非是解决问题的方式优劣性。比如使用递归的时候要尽量使其不重复计算。能用递归的就尝试用动态规划试试。

至于有朋友说时间复杂度和空间复杂度的问题,我这边直接给大家科普一下这两者,方便大家以后自己计算。

下面是一段计算从1到n的3次方和。

假设:我们将计算执行一次的时间分割为一个时间单元,所有的申明不计算时间单元。

结论:图片中第一行和第四行各占1个时间单元,第三行每执行一次占用4个时间单元(两次乘法,一一次加法,一次赋值),那么执行N次所用的时间单元是4N。

第二行在初始化i算一个时间单元,判断i<=N使用N+1个时间单元和i自增N次运算隐含N时间单元,那么总共就是2N+2.

最后我们如果忽略方法的调用和返回值,那么总共消耗时间单元是6N+4;所以我们说这个方法的时间复杂度为O(N)。

其实上面的说明主要为了大家理解时间复杂度如何来的,在平时我们根本不用这样去详细计算。我们总是会去估计一个每一个模块的最大时间复杂度,然后计算。

比如For循环的时间复杂度最多是迭代次数乘以For内部的复杂度。一般是O(N),嵌套For一般是O(N平方)

好了,希望我的这个说明能帮助大家理解时间复杂度怎么来的,如果有不懂的欢迎探讨。

相关推荐

Python的RSA操作(私钥与公钥)(python rsa 公钥解密)

RSA是1977年由罗纳德·李维斯特(RonRivest)、阿迪·萨莫尔(AdiShamir)和伦纳德·阿德曼(LeonardAdleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA...

RSA在日益互联的世界网络中安全性能如何?

KeyFactor公司(美国一家领先的安全数字身份管理解决方案提供商及网络安全行业权威机构)研究表明,许多物联网设备制造商正在生成不安全的RSA密钥,182个RSA证书里就有一个可能会被破解,由于不正...

让频谱分析更高效,澄清RSA使用中的一些误解

从事射频应用的研究人员、工程师和技术人员通常都能充分理解频谱分析仪的用途和优点,无论是传统的扫频分析仪(TSA)还是更现代的矢量信号分析仪(VSA)。他们熟练掌握这些重要射频仪器的关键规范和工作...

微软公告:Win10/Win11将不再支持短于2048位的RSA密钥证书

IT之家3月16日消息,微软近日发布公告,表示即将放弃短于2048位的RSA密钥证书。在公告中微软并未明确弃用时间,对于用户来说,这其实有利于构建更安全的上网环境。IT之家翻译微软公告...

目前已知的最强加密算法RSA(rsa加密算法的优点)

前面有人让我讲解一下RSA算法,今天我就用我所学的知识讲解一下,首先我们先了解一下RSARSA是一种非对称加密算法,1977年由罗纳德·李维斯特(RonRivest)、阿迪·萨莫尔(AdiSha...

韩国 CryptoLab 将在 2025年 RSA 大会发布加密人脸识别解决方案

据美通社4月23日报道,韩国同态加密网络安全企业CryptoLab宣布,将于4月24日在2025年RSA大会上,首次发布加密人脸识别(EFR)方案,为生物识别安全难题提供创新解法。当前,人脸识...

应对变化!盘点RSA2015十大热门产品

4月20日-24日,全球知名信息安全峰会RSAConference2015在美国旧金山召开。作为IT安全领域的权威科技大会,RSA大会不仅会邀请各地区著名安全专家出席与分享,更吸引汇集了全球众多顶...

RSA 2015主题:变化挑战当今的安全理念

1“变化”成为RSA2015主题4月20日-24日,全球知名信息安全峰会RSAConference2015在美国旧金山召开。作为IT安全领域的权威科技大会,RSA大会不仅会邀请各地区著名安全专家出...

非对称加密——一文看懂RSA(非对称加密详解)

非对称加密----RSA的使用"非对称加密也叫公钥密码:使用公钥加密,使用私钥解密"在对称密码中,由于加密和解密的密钥是相同的,因此必须向接收者配送密钥。用于解密的密钥必须被配送给...

RSA算法详解(rsa算法图解)

什么是RSA前面文章我们讲了AES算法,AES算法是一种是对称加密算法,本文我们来介绍一个十分常用的非对称加密算法RSA。非对称加密算法也叫公钥密码算法,通过生成的公私钥来对明文密文进行加密解密。R...

升级SSH后ssh-rsa失效?一文带你轻松解决!

背景今天刚给Linux桌面系统完成升级,结果SSH连接突然“罢工”了,还弹出了这个报错信息:...

历史回顾RSA大会:25年,十个瞬间(rsa conference)

国家安全局、Clipper芯片、苹果对决FBI、禁止ShowGirl——RSA大会都经历过。RSA需要你RSA这个词代表一家密码及安全厂商,也代表着世界上最大的网络安全展会,它今年在旧...

RSA 加密技术详解(rsa的加密原理是什么)

RSA的安全性基于数学难题的理论安全:RSA的安全性主要基于大质数分解和离散对数问题这两个数学难题。在RSA加密算法中,公钥包含一个大整数N,它是两个大质数p和q的乘积。攻击者如果想要破解RSA加密,...

「游戏开发」请别再说Unity不如Unreal:Unity室内场景 + 光照练习 3

关注“indienova”,挖掘独立游戏的更多乐趣引言上两节慢吞吞的补了很多技术实现的细节,感觉要是把用到的所有技术细节都过一遍可能还需要若干篇文章。所以决定先把整体的流程这篇好玩的写了,以后再慢慢补...

再做一个Android!Google发布第二代VR眼镜Cardboard

在去年的GoogleI/O上,Google向所有与会者发放了一款名为Cardboard的纸盒版虚拟现实眼镜,相比OculusRift等颇为酷炫的VR头盔,第一代Cardboard着实糙得很。不过,...