微软8.19笔试（含思路，代码）

#校招# #微软#
第一题压路机，二维xy坐标平面，有n个坑给坐标，用压路机压平，压路机宽度w，求需要多少压路机。

看题意是不用管y，直接把x排序后简单贪心。

第二题是给你一串字符串，只有数字。求最大回文串。

思路是记忆化遍历，把数字个数存在哈希表或者数组里（下标是数字的值，如a[1]=3，就是1这个数字有三个）
然后再把数组遍历，把大于2的值依次加到外侧。同时维护一个为数量奇数的最大数。（注意0数字需要排除）把这个最大数加到最中间。

第三题是一个n叉树，每个节点有一个人，大家组团去根节点上班，求最小油耗？
一辆车最多5人，多了要再加一辆车，一个节点到一个节点一辆车1份油。

给的数据结构很傻逼，是两个数组，两个数组是节点链接关系，比如[1.2.3][0.1.1]就是1链接节点0，2.3链接节点1。

思路是hash或者数组int[]存储每个点可以到达哪里。从根节点开始通过hash遍历整个表，且hash内需要删除父结点，最小叶子节点就返回1 1分别是油耗和人数，计算的时候人数每超过5就油耗+1。（下面给代码）

第二种思路是直接n叉树序列化后变成n叉树，再遍历，可惜我不会