字节跳动2021后端笔试第二场08.16

1. 统计二叉树中的叶子节点数

给出二叉树中的前序和中序遍历，求出二叉树中有多少个叶子节点。

输入：
3       // 节点数
2 1 3   // 前序序列
3 1 2   // 中序序列
输出：
1       // 叶子节点数

答题过程中采用的方法是重建+遍历统计，最终只过了90%，说是数组越界，但buildTree经过在Leetcode和牛客网都测试了一遍，都能通过，想不明白。

// 二叉树节点
class TreeNode{
    int val;
    TreeNode left, right;
}

public class One {

    private static int ct = 0;

    private static TreeNode buildTree(int[] preOrder, int prest, int preed, int[] inOrder, int inst, int ined) {

        if(prest > preed){    // 没有子树
            return null;
        }

        TreeNode root = new TreeNode();
        root.val = preOrder[prest];

        int mid;
        for(mid = inst; mid <= ined && root.val != inOrder[mid]; mid++);

        int len = mid - inst;
        root.left = buildTree(preOrder, prest+1, prest+len, inOrder, inst, mid-1);
        root.right = buildTree(preOrder, prest+len+1, preed, inOrder, mid+1,ined);

        return root;

    }

    private static void traceAll(TreeNode root) {
        if(root == null){
            return;
        }

        traceAll(root.left);
        traceAll(root.right);

        if(root.left == null && root.right == null){
            ct++;
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();   // 二叉树的节点数
        int[] preOrder = new int[n];    // 前序序列
        int[] inOrder = new int[n];     // 中序序列
        for(int i = 0; i < n; i++){
            preOrder[i] = scan.nextInt();
        }
        for(int i = 0; i < n; i++){
            inOrder[i] = scan.nextInt();
        }

        TreeNode root = buildTree(preOrder, 0, n-1, inOrder, 0, n-1);

        ct = 0;
        traceAll(root);

        System.out.println(ct);
    }
}

其实，统计叶子节点数，在buildTree的时候就可以统计，可以节省一次遍历：


public class One {

    private static int ct = 0;
    
    private static TreeNode buildTree(int[] preOrder, int prest, int preed, int[] inOrder, int inst, int ined) {

        if(prest > preed){    // 没有子树
            return null;
        }

        if(prest == preed && inst == ined){   // 叶子节点
            ct++;
        }

        TreeNode root = new TreeNode();
        root.val = preOrder[prest];

        int mid;
        for(mid = inst; mid <= ined && root.val != inOrder[mid]; mid++);

        int len = mid - inst;
        root.left = buildTree(preOrder, prest+1, prest+len, inOrder, inst, mid-1);
        root.right = buildTree(preOrder, prest+len+1, preed, inOrder, mid+1,ined);

        return root;

    }


    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();   // 二叉树的节点数
        int[] preOrder = new int[n];    // 前序序列
        int[] inOrder = new int[n];     // 中序序列
        for(int i = 0; i < n; i++){
            preOrder[i] = scan.nextInt();
        }
        for(int i = 0; i < n; i++){
            inOrder[i] = scan.nextInt();
        }
        ct = 0;
        TreeNode root = buildTree(preOrder, 0, n-1, inOrder, 0, n-1);
        System.out.println(ct);

    }
}

2. 有效字符

一个由0-9，A-F组成的字符串，里面不能出现0010，问至少删除多少个字符，能满足要求。

输入：
2           // 测试用例数
0100
0010ABCDEF
输出：
0
1

没想到什么很好的解决方法，最后骗分的代码竟然AC了，纯属瞎猫碰上死耗子：


public class Two {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = Integer.valueOf(scan.nextLine());

        while(t-- > 0){
            String s = scan.nextLine();
            int len = s.length();
            int ct = 0;

            for(int i = 0; i < len - 3; i++){
                if(s.charAt(i) == '0' && s.charAt(i+1) == '0' && s.charAt(i+2) == '1' && s.charAt(i+3) == '0'){
                    ct++;
                    i += 2;
                }
            }

            System.out.println(ct);
        }
    }
}

看到讨论区里的解释是只要找有几个“0010”即可，仔细想想确实是，比如00100010至少删去两个字符，0010010至少删去两个字符，001010至少删去一个字符：

public class Two {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = Integer.valueOf(scan.nextLine());

        while(t-- > 0){
            String s = scan.nextLine();
            int len = s.length();
            int ct = 0;

            for(int i = 0; i < len - 3; i++){
                if(s.charAt(i) == '0' && s.charAt(i+1) == '0' && s.charAt(i+2) == '1' && s.charAt(i+3) == '0'){
                    ct++;
                }
            }

            System.out.println(ct);
        }
    }
}

这类题目应该通过例子，找出规律。

3. 插入广告

给n段视频，每段视频长度为L_i。现在需要向视频中插入广告，为了用户体验，插入的间隔越大越好。插入间隔可以为0，现有m段广告，问最大的插入间隔是多少。如果无法插入，则***

输入：
n m
L_1 L_2 ... L_n
输入：
最大间隔

是在想不出怎么会有无法插入的情况，大不了间隔为0，一直放广告，随便一段视频都能插入完啊。还有中间广播提示广告可以无限插入，这道题根本get不到点，直接放弃了。

评论区讨论是用二分法解决的，突然恍然大悟：如果间隔为x，那么视频i最多能插入L_i / x段视频。这点笔试中想到了，但是没有联系到二分法，所以感觉没有思路。这道题nlogn是可以通过的，广告的最小间隔是0，最大间隔是max{L_i}。那么这道题就可以转化为二分法求最大的大于指定数。


public class Three {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();
        int[] lens = new int[n];
        int left = 0, right = 0;
        for(int i = 0; i < n; i++){
            lens[i] = scan.nextInt();
            right = Math.max(right, lens[i]);
        }
        
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            
            int ct = count(lens, mid);
            
            if(ct < m){
                right = mid - 1;
            }
            else{
                left = mid;
            }
        }

        System.out.println(left);
    }

    private static int count(int[] lens, int mid) {
        
        int ct = 0;
        for(int m : lens){
            ct += m / mid + 1;
        }
        
        return ct;
    }
}

这道题目，可能需要使用long类型，不过解决问题的思路有了，才是最关键的。

4. 最大的sum % m

长度为n的整数数组，从数组中选取0-n个数，选取的数的和记为sum，求最大的sum%m。

1 2	2 <= m <= 1e9+7 n <= 35

这道题看起来是0-1背包，但m的数量级太大，直接劝退。后来考虑递归遍历所有情况，时间复杂度2^n，也会超时，最终通过40%。看评论区，暴力dfs居然过了60%，为什么我的只过了40%，难道是因为用的是java吗。

看评论区，通过将数组分为两组，思路以后再写。