腾讯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平方）
好了，希望我的这个说明能帮助大家理解时间复杂度怎么来的，如果有不懂的欢迎探讨。