点击上方蓝字设为星标
下面开始今天的学习～
这是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个ressb.append(temp);while(number-->0)sb.append(res);res=sb.toString();}//4.如果是字母的话 临时字符串+chelse 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
