小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));
小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(' '));
本文作者:前端小毛
本文链接:
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!