2020秋招腾讯后台笔试题(一)

栏目: IT技术 · 发布时间: 4年前

内容简介:这是2020届腾讯秋招的笔试题,其实就是19年九月份的题目,总共五道题,这篇文章写说两道题,都是有关于栈的应用的

点击上方 蓝字 设为星标

下面开始今天的学习~

这是2020届腾讯秋招的笔试题,其实就是19年九月份的题目,总共五道题,这篇文章写说两道题,都是有关于栈的应用的

01

压缩算法

小Q想要给他的朋友发送一个神秘字符串,但是他发现字符串的过于长了,于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩,对于字符串中连续的m个相同字符串S将会压缩为[m|S](m为一个整数且1<=m<=100),例如字符串ABCABCABC将会被压缩为[3|ABC],现在小Q的同学收到了小Q发送过来的字符串,你能帮助他进行解压缩么? 

输入描述:

输入第一行包含一个字符串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

解题思路

LeetCode 原型:Leetcode-394 字符串解码

https://leetcode-cn.com/problems/decode-string/

本题难点在于括号内嵌套括号,需要 从内向外 生成与拼接字符串,这与栈的 先入后出 特性对应。

先看Leetcode原题:

2020秋招腾讯后台笔试题(一)

原题中主要有几种可能:

1.当 c 为数字时,将数字字符转化为数字 multi,用于后续倍数计算;

2.当 c 为字母时,在 res 尾部添加 c,这里需要对数字进行处理进位;

3.当 c 为 [ 时,将当前 multi 和 res 入栈,并分别置空置 00:

记录此 [ 前的临时结果 res 至栈,用于发现对应 ] 后的拼接操作;

记录此 [ 前的倍数 multi 至栈,用于发现对应 ] 后,获取 multi × [...] 字符串。

进入到新 [ 后,res 和 multi 重新记录。

4.当 c 为 ] 时,stack 出栈,拼接字符串 res = last_res + cur_multi * res,其中:

last_res是上个 [ 到当前 [ 的字符串,例如 "3[a2[c]]" 中的 a;

cur_multi是当前 [ 到 ] 内字符串的重复倍数,例如 "3[a2[c]]" 中的 2。

2020秋招腾讯后台笔试题(一)

import java.util.*;
class Solution {
    public String decodeString(String s) {
        Deque<String> stack_res=new LinkedList<>();
        Deque<Integer> stack_multi=new LinkedList<>();
        int multi=0;//记录数字
        String res="";//记录临时字符串
        for(Character ch:s.toCharArray()){
            //1.第一中可能,是数字,数字的话就继续往上加
            if(ch>='0' && ch<='9'){
               multi=multi*10+ch-'0'; 
            }
            //2.[的情况下要把临时字符串压入栈中,把数字也压入到栈中,清除两个变量
            else if(ch=='['){
                stack_res.addLast(res);
                stack_multi.addLast(multi);
                multi=0;
                res="";
            }
            //3.]的情况下 说明括号的结束 出栈组合变量起来
            else if(ch==']'){
                StringBuffer sb=new StringBuffer();
                int number=stack_multi.removeLast();
                String temp=stack_res.removeLast();
                //A3[C]会变成ACCC 所以先加之前的A 再加后面number个res
                sb.append(temp);
                while(number-->0)
                    sb.append(res);
                res=sb.toString();
            }
            //4.如果是字母的话 临时字符串+ch
            else 
                res=res+String.valueOf(ch);

        }
        return res;
    }
}

回到腾讯这个题目

那腾讯这个题目其实是有五种可能的字符串

包含 []字母数字|

其实也是和上一个题目一样,但是多了一个

所以看下样例发现 这个题目的 | 充当的是Leetcode 原题中的 [ 符号

我们进行处理即可

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String args[])throws IOException{
        BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
        String ss[]=r.readLine().split(" ");
        String str1=ss[0];
//处理[这个字符 把它扔掉 其他情况下不变
        StringBuffer sbs=new StringBuffer();
        for(Character temp:str1.toCharArray())
            if(temp!='[')
                sbs.append(String.valueOf(temp));
        String str=sbs.toString();

        int multi=0;
        String res="";
        Deque<String> stack_res=new LinkedList<>();
        Deque<Integer> stack_multi=new LinkedList<>();
//声明两个栈 开始遍历对应的字符根据情况去判断
        for(Character s:str.toCharArray()){
            if(s=='|'){
                stack_multi.addLast(multi);
                stack_res.addLast(res);
                multi=0;
                res="";
            }
            else if(s==']'){
                StringBuffer sb=new StringBuffer();
                String tempString=stack_res.removeLast();
                int tempnumber=stack_multi.removeLast();
                sb.append(tempString);
                for(int i=0;i<tempnumber;i++)
                    sb.append(res);
                res=sb.toString();
            }
            else if(s>='0' && s<='9'){
               multi=multi*10+s-'0';
            }

            else{
                res=res+String.valueOf(s);

            }
        }
        System.out.println(res);
    }
}

02

逛街

小Q在周末的时候和他的小伙伴来到大城市逛街,一条步行街上有很多高楼,共有n座高楼排成一行。

小Q从第一栋一直走到了最后一栋,小Q从来都没有见到这么多的楼,所以他想知道他在每栋楼的位置处能看到多少栋楼呢?(当前面的楼的高度大于等于后面的楼时,后面的楼将被挡住) 

输入描述:

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

1<=n<=100000;

1<=wi<=100000; 

输出描述:

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

示例1

输入

6 5 3 8 3 2 5

输出

3 3 5 4 4 4

说明

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

解题思路

这个题目的话主要是使用的数据结构就 单调栈

我先给大家举个例子 我们目前只考虑从当前楼顶往右看到多少楼(当前脚下的楼不算)

例子1:

1 3 2 6 5 7

站在1这个地方 你可以看到3 、6、7  2 被3遮住了 5被6遮住了

站在3 这个地方 你可以看到2、6、7 5被6遮住了

站在2这个地方 你可以看到6、7  5被6遮住了

站在6这个地方 你可以看到5、7

站在5这个地方 你可以看到6

有没有发现什么规律?

规律就是你当前这个站着的楼顶,没有影响你的视野,反而是你往右看的时候第一座房子会影响你的视野

以1为例 3局限了他的视野 下一个看到的房子必须比3高才行

以2位列 6局限了他的失业 下一个看到的房子必须比6高才行

以1为例子

遍历到3       空栈->[3]

遍历到2       保持递增栈 不变

遍历到6       [3]->[3,6]

遍历到5       保持递增栈 不变

遍历到7        [3,6]->[3,6,7]

栈中有三个元素 所以站在1往右看的话可以看到三个楼顶

往左看也是同理可得

要是不熟悉单调栈的可以看看这个题目:

题目连接: https://www.acwing.com/problem/content/832/

C++实现

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
vector<int> a, b;
stack<int> st1, st2;

int main() {
    int n, x[100001];
    cin >> n;
    int ans = 0;
    for (int i = 0; i < n; i++) cin >> x[i];

    for (int i = 0, j = n - 1; i < n, j >= 0; i++, j--) {
        a.push_back(st1.size());
        b.push_back(st2.size());

        while (!st1.empty() && st1.top() <= x[i]) st1.pop();
        while (!st2.empty() && st2.top() <= x[j]) st2.pop();
        st1.push(x[i]);
        st2.push(x[j]);
    }
    reverse(b.begin(), b.end());
    for (int i = 0; i < n; i++) cout << b[i] + a[i] + 1<< " ";
    return 0;
}

03

结尾

第一道题就是考察对 栈的认识 ,当然这道题还是需要比较了解栈的

第二道题就是对 单调栈 的认识

经常会有人把单调队列和单调栈给弄混了  

滑动窗口 使用单调队列即可

查看数组左边和右边的情况 使用单调栈

笔试题好像就是很多Leetcode pro

2020秋招腾讯后台笔试题(一)


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

HTML5秘籍

HTML5秘籍

Matthew MacDonald / 李松峰、朱巍 / 人民邮电出版社 / 2012-8 / 79.00元

《HTML5秘籍》共包括四个部分,共12章。第一部分介绍了html5的发展历程,利用html5重新构造网页,以及html5的语义元素。第二部分介绍了html5对传统web表单的翻新、html5中的音频与视频、canvas绘图技术、css3等内容。第三部分介绍了数据存储、离线应用、与web服务器通信,以及html5与javascript技术的强大结合等内容。第四部分为附录,简单介绍了css和java......一起来看看 《HTML5秘籍》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

MD5 加密
MD5 加密

MD5 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换