内容简介:这是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原题:
原题中主要有几种可能:
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。
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
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
The Zen of CSS Design
Dave Shea、Molly E. Holzschlag / Peachpit Press / 2005-2-27 / USD 44.99
Proving once and for all that standards-compliant design does not equal dull design, this inspiring tome uses examples from the landmark CSS Zen Garden site as the foundation for discussions on how to......一起来看看 《The Zen of CSS Design》 这本书的介绍吧!