3/18美团后端java实习笔试复盘

内容接我上个动态，这里说说第三、四两题

后端依旧是两张卷子，4+1一共五道编程题，美团的题是ACM形式的，不告诉你测试用例，只知道自己正确率。楼主这波是崩了，看着不难的题就A了一道，A的还是不太会的一道题。。。来分享一波笔试题目顺便给自己复盘一下。楼主算法训练地太少了！没打过ACM，**到今天才刷了30道。只能说还是太懒了。希望大家别笑话我

后端依旧是两张卷子，4+1一共五道编程题，美团的题是ACM形式的，不告诉你测试用例，只知道自己正确率。

3、最长彩带

用1到9的数字表示不同颜色，给一个数组表示一条彩带，你可以把它剪成一条包含颜色数不大于color的另一条小彩带，问这个小彩带最长是多长。

唯一A的一题，用的还是之前根本没用过的哈希map。用int max记录最长彩带长度。从左往右遍历数组，如果遇到新颜色就把它加入哈希表中key是颜色，value是出现次数；如果是已经有的颜色，就把它作为key，对应的value++。加入新元素时max++；这样的话，哈希表的size就是已记录的彩带中颜色的种类。如果颜色超出要求，就利用max与i，可以计算出彩带最左元素的位置，把它在哈希表中的value--，如果value为一就把它删除，删除了表的size也会减少，就满足要求了，继续遍历。记录max的峰值并返回。

4、买东西

类似0-1背包问题，但多了个优惠卷。使用优惠券可以降低某个商品的价格，但优惠券的总数是有限的。要求买的商品（0-1背包问题中装的东西）数量越多越好，东西数量一样的话花的钱越少越好。返回最大数量下最少开销。

楼主用回溯法，与0-1背包相似，只不过0-1背包是二叉树，这里是三叉树，选项为：买，不买，用优惠券买。剪枝情况为：剩下商品如果全买，数量也不如之前计算出最大数量大，就不再搜索这一条分支。结果超时了。。。绝了。应该还有我没想到的剪枝情况。

5、信号塔

问信号塔的覆盖范围。

这题没来得及看。。。

楼主这波是寄中寄了，好久没起这么早，早上状态确实不行，也可能是紧张了，但最根本的原因还是题做少了，希望大家引以为戒。