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.对于递归、动态规划问题我一直保持着敬畏的态度，特为是最后一个一题，我是用递归解决的，但是其属于动态规划的内容，对于何时我递归何时用动态规划，我心里打鼓，真诚的希望与大家一起交流。
