【校招题解】网易2018春招笔试编程题参考代码-牛客网-牛客企业版-牛客企业服务

作者：NotDeep
来源：牛客网

练习地址：

https://www.nowcoder.com/test/9763997/summary

牛牛的闹钟

分析

对于每一个闹钟，计算x分钟后的时间，和上课时间进行比较，如果不超过上课时间，把闹钟时间和保存的答案进行比较，取最晚。

时间复杂度

O(n)

参考代码

迷路的牛牛

分析

统计一共向左和向右转了多少次，计算最后的方向相对于初始方向的差异，模拟即可。

时间复杂度

O(n)

参考代码

安置路灯

分析

贪心。
对于一个需要照亮的位置的右边一格放置一个路灯就好了。

时间复杂度

O(n)

参考代码

被3整除

分析

手算一下会发现规律。
三个数为一组,第一个数不能被3整除,另外两个可以被3整除。
于是把区间端点都移到某组的开端,记录移动过程中满足的数, 之后就可以通过(b - a) / 3 * 2快速计算。

时间复杂度

O(1)

参考代码

数对

分析

对于一个b, n范围内的数模b的序列应该是:
0,1,2,...,b-1, 0, 1, 2,..., b-1,...0,1,2,..n%b
前面部分是个循环节,所以可以通过(n / b) * max(0, b - k)计算。
后面部分是max(0, n % b - k + 1),
于是我们枚举合法的b计算就可以了。
k = 0的情况特判处理。

时间复杂度

O(n)

参考代码

矩形重叠

分析

分别枚举所有的横纵坐标,挨着判断每个矩形是否符合条件，计数维护最大即可。

时间复杂度

O(n^3)

参考代码

牛牛的背包问题

分析

容量太大,没办法dp。
看到物品数量是30,直接爆搜也不行。。
于是对半分成两部分枚举之后,二分计算贡献。
当然用个map来做个map版本的背包也是兹磁的吧？

时间复杂度

O(2^(n/2) * log(2^(n/2)))

参考代码

牛牛找工作

分析

实际上对于每个难度的工作，只有报酬最高的那一种是可能成为答案的，剩下的都可以无视。
由于只有N项工作和M个小伙伴，最多只会出现N+M种难度(能力值)，所以可以把难度和能力值映射到不超过N+M个数上(std通过排序+map来完成)。
对这些难度(能力值)分别求出最高的报酬，再按i从小到大的顺序维护难度(能力值)不超过i的最大报酬。最后输出每个小伙伴对应的能力值以下的最高报酬即可。

时间复杂度

O((N+M)*log(N+M))

参考代码