笔试题1

吐槽

下午做了某公司的笔试题，10道单选，30道多选和2道编程题。选择题就不说了，记录一下编程题，虽然只能凭着记忆拼凑。

考试的过程也是出了个小插曲，不知道为何笔记本连上了家里的wifi后一直没有网络，然后我就用手机开热点，一开始挺正常的，后面在做编程题的时候一直断网。

因为是在牛客网进行考试的，需要开启摄像头和共享屏幕，结果一直断网导致我一直提交不了，依靠网络开启的浏览器摄像头和屏幕共享也受到影响中断了，还提示可能会影响成绩。

后面实在忍受不了了，把台式主机的网线拔了插在笔记本上，网络才稳定下来。虽然也告知了hr出现了这个情况，但他们可能也会怀疑是否作弊了吧，哎，大不了后面再做一次题。

还有另一个吐槽的点，平时力扣刷习惯了，到了牛客这个考试系统，还要自己处理输入，把字符串转化为各种数据类型，也给我添加了许多麻烦。比如答案提交之后发现样例通过了70%，我以为是哪里考虑不周改来改去，后面发现是处理输入有问题。

说了这么多该回到正题了。

最大运货量

题意大概是，有一堆货物，重量分别为t1、t2、t3...，有不同载重的货车，每种货车也是有限的数量，求所有的货车最多能载走多少重量的货，一辆货车只能装一个货物。 样例大概是：

5 2 3 1 4 2 // 表示有5个货物，数字代表的是各自的重量
6:1,5:1,1:4,3:2 // 代表的是有载重6的货车1量，载重5的货车1辆，载重1的货车4辆和载重3的货车2辆

输出：15 // 其中有一个重量为2的货物运不了

一开始没看到一辆货车只能装一个货物这个条件，以为这是一道dp的题目，就直接跳过了先去做第二道题。后面回来的时候发现可以用贪心来解决。

就是优先装大的货物，并且优先用大载重的车来装。这样子能保证大载重的车能装下较重的货物，保证运货量的最大化。

具体做法就是，给货物重量从大到小排序，给货车的载重量也从大到小排序。然后按顺序遍历给货物分配车，车也是按从大到小分配出去，直到货车数量消耗完。

如果一辆货车能装多个货物，那就不能用贪心了，就是一个背包问题了，这个最近没刷基本忘光了。

多次区间操作后的数组

题意大概是，给你一个数组arr长度为n，里面初始元素都是0。再给你一个二维数组，里面元素为[start,end,inc]，代表对arr数组从下标start到下标end（包含）之间所有的数字都加上inc，最后返回被多次修改之后的arr数组。

虽然看到这道题我大概知道思路，可以用模拟也可以用差分数组，为了简单起见我直接用了模拟法，就是直接双重循环，然后去改arr里面的值，然后测试用例通过了70%。

到这里我还以为，是其他的样例超时了，就改用差分数组把时间复杂度降低到O(n)，结果还是只通过了70%样例，离谱！

然后仔细查看题目和代码后才发现，我在处理接受输入的时候，没有考虑到inc是负数的情况，导致inc全都是正数，后面修改了下处理输入的方式，就全部样例通过了。

后面也没有重新去试一下模拟法能否通过了，我感觉应该是可以的，当然如果时间卡的紧应该就过不了。

写在最后

因为没有地方来测验重新写的代码的正确性，这里就不贴代码了，就记录下是什么类型的题目和思路。

最后在时间限制之内做完这两道题目，还剩下20分钟。最大的成长是，处理字符串的能力增强了！就是把一行一行输入的字符串（有些还是个二维数组），转化成实际的数据类型。