VIVO提前批笔试

VIVO提前批

笔试

题目1：打家劫舍改版（评论区提醒为 种花问题）

给定长度为N的长方形园林，该园林中有些地方已经种上了植物。现需要在空余的地方种上植物，要求植物不能相邻。问：最多还可以再种几棵植物？

例：
园林目前的种植状态为：1 0 0 0 0
结果：2

使用回溯法就可以通过，每次递归前判断左右是否为1即可。

题目2：扔鸡蛋问题

手里有K个鸡蛋，面前有一栋高度为N的楼。已知存在某一高度，当在该高度之上扔鸡蛋时，鸡蛋会碎掉，低于该高度时，鸡蛋不会碎掉。问：至少需要扔几个鸡蛋，才能得到高度的确切值？
经典动态规划问题，LeetCode上有原题，Hard难度。

题目3：合并K个有序的链表

输入的K个链表都是有序的情况下，直接使用小顶堆就可以了（我用的C++，声明priority_queue时半天没想起来加vector<ListNode*>）。这道题看好多大佬直接用数组排序做的，题目原意应该是让自己写ListNode结构体，从输入数据中构造多个链表，再送入ListNode mergeLists(ListNode[] lists)中做合并吧。LeetCode Hard难度。

总结

总体来说，第一道和第三道不是很难，第二道动态规划的确属于hard级别。不过由于自己之前一直没用过牛客的系统，输入输出思考了20分钟，只AC了一道，看来还是要多练习使用牛客的系统，比较可惜吧。
后面和牛客的大佬们一起加油吧！