2021届秋招字节跳动研发第二场笔试 8.16

第一题：知道先序遍历、中序遍历，求叶子节点数量
 思路：DFS（深度遍历算法），叶子节点也就是只有根节点，无左右孩子节点
 步骤：判断是否有左右孩子，若无，返回一个叶子节点。否则，返回右孩子的叶子结点+右孩子的叶子节点数。相应代码如下：

/**
     * 知道先序遍历、中序遍历，求叶子节点数量
     * @param a 先序遍历数组
     * @param i 起始节点索引
     * @param j 末尾节点索引+1
     * @param b 中序遍历数组
     * @param k 起始节点索引
     * @param l 末尾节点索引+1
     */
    public static int numLeafNode(int[] a, int i, int j, int[] b, int k, int l) {
        // 思路：1.先序遍历第一个值为其根节点
        // 2.则左孩子的先序遍历数组是什么呢？同理，右孩子的先序表里数组是什么呢？
        // 3.如果我们知道了问题2的答案，很明显我们可以递归循环下来，知道其无孩子节点，结束（对应的先序遍历为空）

        // 结束条件，当先序遍历只有一个值时，代表其无左右孩子节点
        if (j-i==0) {
            return 0;
        } else if (j-i==1) {
            // 当前即为叶子节点返回值为1
            return 1;
        } else {
            // 根节点
            int data = a[i];
            // 中序遍历中找到其根节点的索引位置，就知道了其先序遍历左右孩子节点的先序遍历数组
            int index = k;
            for (; index < l; index++) {
                if (b[index] == data) {
                    break;
                }
            }
            // 左孩子的叶子节点数+右孩子的叶子节点数
            int left = numLeafNode(a, i+1, i+1+index-k, b, k, index);
            int right = numLeafNode(a, i+1+index-k, j, b, index+1, l);
            return left+right;
        }
    }

第二题：给出一个字符串，其中不能出现0010，通过删除字符的方式让整个字符串不出现0010，求最少删除字符个数。

/**
     * 给出一个字符串，其中不能出现0010，通过删除字符的方式让整个字符串不出现0010，求最少删除字符个数。
     * @param str
     * @return
     */
    public static int numDelete0010(String str) {
        int result = 0;
        while (str.contains("0010")) {
            int index = str.indexOf("0010");
            int length = str.length();
            if (length==index+4) {
                str = str.substring(0, index);
            } else {
                str = str.substring(0, index) + str.substring(index+4, length);
            }
            result++;
        }
        return result;
    }

第三题：利用二分法
 思路：当间隔大于所有视频长度的最大值时，只能插入n个广告。所以说当m<n这种情况，不需要考虑；当m=n时，最大间隔就是所有视频中的最大时长的间隔（max）；当m>n时，间隔在其之间；所以插入广告间隔在[0,max]范围内，随着间隔的递增，插入广告的数量不断减少，属于单调函数。满足二分法的思路。

Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            // 输入视频数量
            int n = sc.nextInt();
            // 输入广告数量
            int m = sc.nextInt();
            int right = 0;
            // 输入每个视频的长度
            int[] data = new int[n];
            for (int i = 0; i < n; i++) {
               data[i] = sc.nextInt();
                if (data[i] > right) {
                    right = data[i];
                }
            }

            // 思路，当间隔大于所有视频长度的最大值时，只能插入n个广告。所以说当m<n这种情况，不需要考虑
            // 当m=n时，最大间隔就是所有视频中的最大时长的间隔
            // 当m>n时，间隔在其之间。
            int left = 0;
            //用二分法
            while (left<right) {
                // 求中间点
                int mid = (left + right)/2;
                // 求为中间值时，能放的广告最大数
                int sum = 0;
                for (int i = 0; i < n; i++) {
                    sum = sum + data[i]/mid +1;
                }
                if (sum>=m) {
                    left = mid;
                } else {
                    right = mid;
                }
            }
            // 总结一般单调函数都能有二分法来爆破破解
        }

第四题：属于01背包问题的逻辑，我这里使用尾递归实现的。
 思路：对背包中的物品进行逐一判断，当判断了最后一件物品输出相应的值。否则进行判断下一件物品，分两种情况：1、添加这种物品；2、不添加这种物品。求这两种情况的最大值。

/**
     * 在数组中选k个数的和，使得与m的模最大
     * @param data 待选数组
     * @param k 已选个数
     * @param m 模值
     * @param total 所选的数字值之和
     * @return 采用01背包问题解决思路，从数组中第一个数进行判读是否选择，直到最后一个数为止
     */
    public static int knapsack01(int[] data, int k, int m, int total) {

        int n = data.length;
        // 已经对数组中的所有数据进行判断了
        if (k==n) {
            // 必须继续添加一个参数作为最终结果的记录（尾递归，用空间换时间）
            return total%m;
        } else {
            // 选当前索引的数组，也就是total值增加
            int first = knapsack01(data, k+1, m, total+data[k]);
            // 不选当前索引的数组，total值不变
            int second = knapsack01(data, k+1, m, total);
            return Math.max(first, second);
        }
    }

总结：
 1.有不对的地方希望各位指出，交流。
 2.对于递归、动态规划问题我一直保持着敬畏的态度，特为是最后一个一题，我是用递归解决的，但是其属于动态规划的内容，对于何时我递归何时用动态规划，我心里打鼓，真诚的希望与大家一起交流。