美团0813笔试

其实上周做了一次，只不过最后一题没有提交上去，所以这周重新做了一下。

5个编程题：

1、魔法外卖：大概意思就是输入n个订单以及派送每个订单所要消耗的时间t，再给定每个订单的截止时间。使用魔法是立即完成一个订单，问完成所有订单需要使用多少次魔法？

我是用优先队列做的，队列前面如果小于t就必须得用魔法了，计数输出一下就就行。

2、扫地机器人：模拟做一下就行，之前做科大讯飞有了经验，直接写个类重写hashcode和equals方法放进set里面就行

3、扑克：两个人一开始可以将牌堆顶部的牌放到底部，然后再翻开一个牌。输入是最后翻牌的结果，要还原本来的牌顺序。

我用普通队列模拟的，只过了80多。用双端队列应该可以AC

4、合法元数组：输入一个数组，问有多少个三元组（i，j，k）满足a[i] - a[j] = 2 * a[j] - a[k]，其中i < j < k。

直接暴力枚举ijk可以过82%

移动的等式可以得到a[i] + a[k] = 3 * a[j]，所以可以固定i遍历k，然后用map找j

long ans = 0;
for (int i = 0; i < n; i++) {
    int num = a[i];
    Map map = new HashMap();
    for (int j = i + 1; j < n; j++) {
        int c = a[j];
        int target = (num + c);
        ans += target % 3 == 0 ? map.getOrDefault(target / 3, 0) : 0;
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
}
System.out.println(ans);

5、生活在树上：其实就是 lc 124 二叉树中的最大路径和 简化版本，甚至只需要考虑从根节点出发的情况，题目也明示了左右子树的关系，所以也不需要建树。