腾讯2020校园招聘

1. 压缩算法

小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

输出
HGBCACABCACABCACAF

说明
HG[3|B[2|CA]]F−>HG[3|BCACA]F−>HGBCACABCACABCACAF

let s = readline().trim();
let decode = (s) => {
  // x, y, z会找到最内层的一组方括号 [|]
  let [i, x, y, z] = [0, -1, -1, -1];
  while (i < s.length) {
    if (s[i] === '[') {
      x = i;
    }
    else if(s[i] === '|') {
      y = i;
    }
    else if (s[i] === ']'){
      z = i;
      break;
    }
    i++
  }
  if (x !== -1 && y !== -1 && z !== -1) {
    let times = s.slice(x+1, y);
    let sub = s.slice(y+1, z);
    let decode_s = s.slice(0, x) + sub.repeat(times) + s.slice(z+1);
    return decode(decode_s);
  }else{
    return s;
  }
}
print(decode(s));

2. 逛街

小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栋楼。

let n = parseInt(readline());
let w = readline().split(' ').map(Number);
let left = []; //从左往右看能看到的楼数 借助单调递增栈
let right = [];//从右往左看能看到的楼数 借助单调递减栈
let total = [];
// 单调递减栈
let stack = [];
for(let i = n-1; i>=0; i--) { // 从右往左遍历
  right[i] = stack.length;
  while(stack.length && stack[0] <= w[i]) { //栈顶的元素如果小于当前遍历的数，就把栈顶元素弹出
    stack.shift();
  }
  stack.unshift(w[i]);
}
// 单调递增栈
stack = [];
for(let i=0; i<n; i++) { // 从左往右遍历
  left[i] = stack.length;
  total[i] = left[i] + right[i] + 1; // +1是加的自身的一栋楼
  while(stack.length && stack[stack.length - 1]<=w[i]) { //栈顶的元素如果小于当前遍历的数，就把栈顶元素弹出
    stack.pop();
  }
  stack.push(w[i]);
}
print(total.join(' '));