8月16日字节笔试

前言

不能用IDEA,全部在牛客的平台里面写,第二题的输入大概卡了20分钟。

第一题

给定一颗树的先序遍历顺序和中序遍历顺序,求出这棵树有多少个叶子节点。保证每个节点的数字都不相同。

比较经典的问题,可以根据这两个顺序构造出一棵树,然后求一棵树的叶子节点还不简单吗?

但是!其实根本就没有必要构造这么一棵树,只需要传递一下数组,出口条件是数组的长度小于等于2,此时必有一个叶子节点。

第二题

第二题卡了我很久很久,最后关头的代码写错了….0%。

题目是这样的,给定一个字符串,该字符串是由数字和字母组成的,而需要保证这个字符串里面没有0010这个值,那么最少删除几个字符呢?

这题当时考虑了很多的情况,首先0010,可以删除的地方有三个,分别是:

  • 前面两个零中的任意一个(因为完全等价)
  • 删除1
  • 删除最后那个0

但是不论你删除的是哪个,都有可能删除后,让原来本来没有的字符串,转变成有的,下面是例子:

  • 0000010,如果你删除前面的任意的0,都不会导致没有0010,但是如果你删除1,则只需要一次。
  • 001010,如果你删除左边的那个1,那么剩下的又可以组成一个新的0010,显然这个我们应该删除最左边的0
  • 001000000,如果你删除1后面的那个0,那么后面的那些0又可以组成新的0010,显然这里我们应该删除1。

当时我就一直在考虑这些问题,也就是如何判断给定一个字符串,如何删除呢?

个人觉得这道题是不是应该需要一些编码相关的知识,最后的结论应该是只需要判断整个字符串中出现了多少次0010就可以,也就是通过编码学知识,我可以证明一定能够删除这三个位置中的一个,保证不出现新的。

第三题

某视频网站上有N个视频,每个视频长为L_i秒。产品经理找到你,希望你帮忙再其中插入M个广告。

一个视频里的两个广告必须间隔一段时间,间隔时间可以为0(我:那你说xx呢!)

考虑到用户体验,他希望这个时间间隔尽可能长,为方便实现,间隔时间是一个整数。

请你计算一下,这个最大的间隔可以是多少秒呢?如果不能插入M条广告,那么输出0

这题目我当时读的时候就理解不能,既然你时间广告的间隔时间可以是0,你想往里面插多少条广告都可以,怎么可能最后输出0呢?

继续,题目接着给出了范例,三个视频,时长分别是90秒,100秒和120秒,需要插入9个广告,那么时间间隔可以是45秒。每个视频只需要在第0秒,第45秒和第90秒插入三个广告就可以了。

我当时做的时候忽略了这句话:为方便实现,间隔时间是一个整数,所以觉得这题无解…,如果考虑这个条件,所以其实就是一个简单的二分法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void main(String[] args) {
int[] ad = {90, 100, 134};
int m = 10;
int n = ad.length;
int right = ad[n - 1];
int left = 0;
while (left < right) {
int mid = 1 + left + (right - left) / 2;
int sum = 0;

for (int i = 0; i < n; ++i) {
sum += ad[i] / mid + 1;
}

if (sum >= m) {
left = mid;
} else {
right = mid - 1;
}
}
System.out.println(left);
}

时间最大的间隔肯定是所有视频中最大的那个,如果广告时间间隔大于了最大的视频,那么所有的视频只能插入一个(上面代码没有体现这个,你可以当做特例条件来判断),然后假设最长的是120秒,那么之后就只需要先判断60秒,如果60秒可以,接着加,如果不可以,那就减。

其实就是一个很简单的二分应用,不过把它包装成了题目这样的,确实没往二分这方面考虑,菜了菜了。

第四题

给定一个数组,然后给定一个M,你可以从数组中任意取数字,然后把它们求和记做sum,求出sum % M的最大值。

说实话没什么好的思路,就只能DFS暴力做了,通过了50%。

总结

确实自己最近算法题没刷,有点手生了。然后字节这些题目出的是很优秀的,不仅测试了参加笔试的人的算法能力,也考察了对实际问题进行建模的问题。事后想想其实这几题还是挺简单的,没写出来只能说明自己还需要多刷题吧。

最后提个意见,笔试能不能就不要在牛客这种所谓的“在线IDE”(说它ide都给它面子了)上写代码了呢,调试功能基本是废的,代码提示完全用不了,中间还一度断网。反正如果下次还有牛客的在线笔试,直接虚拟机。