2020届校招：腾讯技术类第一次笔试题整理

1、字符串解压缩

某种压缩算法，对于字符串中连续的 m 个相同字符串 S 将会压缩为 [m | S] （m 为一个整数且 1<= m <= 100），例如字符串 ABCABCABC 将会被压缩为 [3|ABC] ，现在需要对压缩后的字符串解压缩。

输入:
HG[3|B[2|CA]]F
输出：
HGBCACABCACABCACAF
说明：
HG[3|B[2|CA]]F -> HG[3|BCACA]F -> HGBCACABCACABCACAF

import java.util.Scanner;
import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();

        Stack<String> stack = new Stack<String>();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < str.length(); i++) {
            char tmp = str.charAt(i);

            if (tmp == '[') {
                //遇 '['，则入栈
                stack.push(tmp + "");
            } else if (tmp == ']') {
                //遇 ']'，则出栈
                String now = "";
                String left = "[";

                //从栈中取出'['和']'之间的字符，拼接成字符串
                while (!left.equals(stack.peek())) {
                    now = stack.pop() + now;
                }

                //'['出栈
                stack.pop();
                //将重复的字符还原
                String re = build(now);

                if (stack.empty()) {
                    //添加到最终结果
                    sb.append(re);
                } else {
                    stack.push(re);
                }
            } else {
                if (stack.empty()) {
                    sb.append(tmp);
                } else {
                    stack.push(tmp + "");
                }
            }
        }

        System.out.println(sb.toString());
    }

    private static String build(String str) {
        String[] arr = str.split("\\|");
        int num = Integer.valueOf(arr[0]);
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < num; i++) {
            sb.append(arr[1]);
        }

        return sb.toString();
    }
}

2、逆序对个数

Q有一个数列有2^n个数，老板一共问Q m 次，每次给出一个整数 q_i（1 <= i <= m），要求Q把这些数每 2^q_i 分为一组，然后每组进行反转，求每次操作后整个序列中的逆序对个数。

例如：
对于序列 1 3 4 2，逆序对有 （4，2），（3，2），总数量为 2.
反转之后为 2 4 3 1，逆序对有 （2，1），（4，3），（4，1），（3，1），总数量为 4.
    
输入描述：
第一行一个数 n（0 <= n <= 20）;
第二行 2^n 个数，表示初始的序列（1 <= 初始序列 <= 10^9）

输入：
2
2 1 4 3
4
1 2 0 2
输出：
0
6
6
0

说明：
初始序列： 2 1 4 3
2^q_1 = 2   -> 第一次： 1 2 3 4  -> 逆序对数为 0
2^q_2 = 4   -> 第一次： 4 3 2 1  -> 逆序对数为 6
2^q_3 = 1   -> 第一次： 4 3 2 1  -> 逆序对数为 6
2^q_4 = 4   -> 第一次： 1 2 3 4  -> 逆序对数为 0

3、覆盖河道

一段河道长L，可看作是 [0,1] 的一条数轴，此时有 n 个提供视野的道具，第 i 个道具能够覆盖的范围是 [x_i, y_i]，问至少用几个道具即可覆盖河道。

输入描述：
输入包括 n+1 行
第一行包括两个正数 n 和 L，（1 <= n <= 10^5, 1 <= L <= 10^9）
接下来的 n 行，每行两个正整数 x_i, y_i,（0 <= x_i <= y_i <= 10^9，表示第 i 个道具覆盖的区间）

输出描述：
一个整数，表示最少需要的道具数量，如果无解，则输出 -1；

输入：
4 6
3 6
2 4
0 2
4 7
    
输出：
3

4、楼数

一条街上有 n 栋楼，Q想知道在每栋楼的位置能看到多少栋楼（当前面的楼高度大于等于后面的楼时，后面的楼被挡住。）

输入描述：
第一行包含一个数字 n，代表楼的栋数，接下来的一行包含 n 个数字 w_i（1 <= i <= n），
代表每一栋楼的高度。
1 <= n <= 100000;
1 <= w_i <= 100000;

输出描述：
输出一行，包含空格分隔的 n 个数字 v_i，分别代表 Q 在第i栋楼时能看到的楼的数量。

输入：
6
5 3 8 3 2 5

输出：
3 3 5 4 4 4
    
说明：
当 Q 处于位置 3 时，他可以向前看到位置 2， 1 处的楼，向后看到位置 4，6 处的楼，
加上第3栋楼，共可以看到5栋楼。处于 4 位置时，向前可看到 位置 3 的楼，向后可看到
位置 5，6 处的楼，加上第 4 栋楼，共可看到 4 栋楼。