首页天道酬勤腾讯会员6元一个月(算法的时间复杂度是指什么)

腾讯会员6元一个月(算法的时间复杂度是指什么)

admin 12-04 06:29 181次浏览

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

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

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

[编程题一]压缩算法

输入描述:

输入第一行包含一个字符串s,代表压缩后的字符串。

S的长度=1000;

S仅包含大写字母、[、]、|;

解压后的字符串长度不超过100000;

压缩递归层数不超过10层;

输出描述:

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

输入例子1:

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

输出例子1:

hgbcacabcacaf

例子说明1:

HG[3 | B[2 | CA]]F-HG[3 | BCACA]F-HGBCACABCACABCACAF

详细解答

//JAVA版本

导入Java。io。*;

导入Java。乌提尔。*;

公共类主要的

公共静态void main(String[]参数){ 0

扫描仪sc=新扫描仪(系统。in);

Main Main=new Main();

字符串行=sc。NextLine();

StringBuilder sb=new StringBuilder(行);

解码(某人);

系统。出去。(某人。ToString());

}

私有无效解码(StringBuilder字符串){ 0

int I=0;

int start=-1,mid=-1,end=-1;

(同时。length()){ 0

if(字符串。charat(I)='[')start=I;//找到线中第一个']'的最后一个'['

if(字符串。charat(I)=|)mid=I;//找到线中第一个']'对应的'['之间的'|'

if(字符串。charat(I)=']'){ end=I;打破;}//遇到第一个']'就直接退出循环

我;

}

if(start==-1)返回;

int num=整数。parseint(字符串。子串(开始1,中间));//要复制的数量

字符串cur=字符串。子串(mid 1,end);//要复制的内容

StringBuilder sb=new StringBuilder();

for(int j=0;jnumj){ 0

附加(cur);

}

替换(开始,结束1,sb。tostring());

解码(字符串);

}

}

//C(C)版本

#包含输入输出流

#包含字符串

使用命名空间标准;

int main(){ 0

字符串s;

cin的;

int I=0;

while(I . s . length()){ 0

if(s[I]==']'){ 0

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 <len; si++){ s2+=s1; } s = s.replace(j, i-j+1, s2); i=j; } i++; } cout << s <<endl; }

【编程题二】逛街

输入描述:

输入第一行将包含一个数字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<Integer> sl = new Stack<>(); //从前向后遍历,相当于每个楼往右边能看到几个 for(int i=0; i<num; i++){ res[i] += sl.size()+1; //加上自己 //维护栈,为一个楼做准备 while(!sl.isEmpty() && sl.peek()<=build[i]) sl.pop(); sl.push(build[i]); //当前楼一定能被下一个楼看见 } Stack<Integer> 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平方)

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

计算资源计费 边缘计算容器组 UEC-ContainersUGUI实现ScrollView无限滚动效果UCloud AIoT防疫一体机入选工信部“2021年新型信息消费示范项目”tomcat8中startup可以启动但tomcat8w无法启动怎么解决Java0基础_day11-抽象类与接口雷士灯具管理系统
红黑树 avl(二叉树的中序列) linkedin 查看过的人(账号申诉)
相关内容