微软2016校招在线笔试题解 题目地址：mstest2016april1

感受：一定要理解好题意，注意细节。另外微软特别喜欢考察反向思维。

A. Font Size

选择一个最大字号刚好可以令页数不超过给定阈值P。

逻辑理清即可。页由行组成，行由字符组成，其中字符为方形。需要注意的地方是：(1) 每段都从新的一行开始；(2) 每页至少显示一个字符。

字号是整数，可以暴力求解遍历直到合适字号，单点时间复杂度为O(10^6)，没有超过题目限制。但如果题目再卡紧点就有点危险了，所以更好的方法是利用二分查找，注意好边界条件即可。

编码思路如下：

1.确定字号最小值为1，最大值为 min(W, H)

2.求字号为中值 m 时的页数：每段所占行数 a[i]/(W/m)，对所有段所占行数求和，最后求所占页数 total/(H/m)。

3.当所占页数大于等于阈值P，则r=m，小于则l=m+1，直到l>=r。注意等于阈值P时并不代表已经找到解，字号可能还能增大。

4.解为 r-1。

B. 403 Forbidden

题目的要求是进行 IP 地址匹配，返回最先（序号最小）匹配到的规则的动作，没有匹配的规则则返回 allow。

一种方法是利用前缀树求解。建树方法: 在插入新规则 new 时，在该规则的前缀路径上（含等长）已有规则 old，意味着 old 屏蔽了new，直接丢弃新规则new。 由此，在匹配一个 IP 地址时，只需要返回前缀树上匹配这个 IP 地址的最长规则。

建树时间复杂度为 O(N)，匹配一次只需要常数时间，整体时间复杂度为 O(min{N,M})。

C. Demo Day

动态规划水题，起始位置为 (1,1)，动作为向下或向右，考虑好各个状态转移,并且注意边界特殊情况即可。时间复杂度为 O(N*M)。

DP[i][j][k] 含义为：在第 i 行 第 j 列时，向 k 方向前进需要改变多少个格子 (1<=i<=N, 1<=j<=M, k=right or down)。

DP[i][j][right] = min{DP[i][j-1][right], DP[i-1][j][down] + (i + 1 < n && maze[i+1][j] != 'b')} + (maze[i][j] == 'b');
DP[i][j][down] = min{DP[i-1][j][down], DP[i][j-1][right] + (j + 1 < m && maze[i][j+1] != 'b')} + (maze[i][j] == 'b');
DP[i-1][j][k] 仅在 i - 1 > 0 时存在，同理 DP[i][j-1][k] 仅在 j - 1 > 0 时存在。
最后结果：ans = min{DP[N][M][right], DP[N][M][down])

D. Building in Sandbox

思路参考知乎。

题目的初始条件是地面([1,1,0]~[100,100,0])已经摆满了方块。

对于新添加的方块有下面两个要求： 1. 相邻性：必须与之前之前放置的立方体(包括地面)相邻； 2. 可达性：必须能够从空间外部在不穿过任何方块的前提下到达该方块，换言之就是不能处于封闭空间中。

对于第一个要求每次添加时进行简单的逻辑判断即可。

第二个要求根据一位答主的想法，由闭空间判断转换为开空间判断，就变成了图论里的简单题目了：先对外部空间做一个FloodFill；然后倒序判断方块 i 是否与外部空间相邻；相邻的话就删除该方块，然后做FloodFill；一旦存在不相邻就是处于封闭空间中。

不过该方法是离线判断，强制在线可参考另一个回答。

---

阅读参考

https://www.zhihu.com/question/42406890

http://www.gotit.sinaapp.com/

http://yfwz100.github.io/articles/interv/microsoft-2016.html