陈浪平的博客
0%

8月16日字节笔试

发表于 更新于 分类于 Disqus：
本文字数： 1.9k 阅读时长 ≈ 2 分钟

前言

不能用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都给它面子了）上写代码了呢，调试功能基本是废的，代码提示完全用不了，中间还一度断网。反正如果下次还有牛客的在线笔试，直接虚拟机。