微软2016实习生招聘4月份笔试题目微软2016实习生招聘4月份笔试题

今年4月份参加了微软实习生招聘的在线笔试，400分只得了140（(⊙﹏⊙)）。原题链接戳
http://hihocoder.com/contest/mstest2016april1/problems
接下来就前三个题分析一下解法，也希望大家能共享一下思路。
1. Font Size 题目大意：使用手机屏幕阅读电子书，屏幕宽W高H，如果电子书的字号为S的话，那么每一行的字数最多是?W / S? ，每一列的字数最多是?H / S?。现在假设我们有一本电子书为N段，（每一个新段是另起一行显示）每一段的字数分别是a1,a2...aN。我们需要将字号尽量调大以方便阅读，但是我们希望该书的页数不会超过P，求可调节的最大字号。
输入：第一行为测试用例个数，接着每个测试用例是两行，第一行是N，P，W和H，第二行是每个段的字数（a1,a2...aN）
输出：对每个测试用例，输出所求的最大字号。
样例输入
Java
2
1 10 4 3
10
2 10 4 3
10 10

样例输出 ```Java``` 3 2

解题思路：
先将字号size设为W和H中最小的那个值，就是说一页恰好放得下一个字。然后算出这种情况下的页数。算页数的方法：先根据每段的字数算出每段应占行数，相加得到总行数。然后根据高度算出每个页能放多少行，将总行数除以单页行数得到page值。逐步降低size值，直到page值满足条件。
Java代码：
Java
import java.util.Scanner;
public class Main {
//根据一段的字数算出每段应该占多少行
public int getRow(int width, int fontSize, int wordNum) {
int wordsPerRow = width / fontSize;
int a = wordNum % wordsPerRow;
if (a == 0) {
return wordNum / wordsPerRow;
}
return wordNum / wordsPerRow + 1;
}
//根据设定的fontSize算出页数
public int getPage(int pNum, int[] wordNumPerP, int width, int height, int fontSize) {
if (pNum == 0) {
return 0;
}
int rowPerPage = height / fontSize;
int row = 0;
for (int worNum : wordNumPerP) {
row += getRow(width, fontSize, worNum);
}
int b = row % rowPerPage;
if (b == 0) {
return row / rowPerPage;
}
return row / rowPerPage + 1;
}
//调整fontSize，直到满足结果
public int getMaxSize(int pNum, int[] wordNumPerP, int width, int height, int page) {
int size;
for (size = width; size > 0; size--) {
if (size > height) {
continue;
}
if (getPage(pNum, wordNumPerP, width, height, size) <= page) {
break;
}
}
return size;
}

public static void main(String[] args) { Main main = new Main(); Scanner sc = new Scanner(System.in); if (sc.hasNextLine()) { int num = Integer.parseInt(sc.nextLine()); for (int i = 0; i < num; i++) { String fLine = sc.nextLine(); String[] a = fLine.split(" "); if (a.length != 4) { return; } int pNum = Integer.parseInt(a[0]); int page = Integer.parseInt(a[1]); int width = Integer.parseInt(a[2]); int height = Integer.parseInt(a[3]); String words = sc.nextLine(); String[] arr = words.split(" "); int[] wordPerP = new int[arr.length]; for (int j = 0; j < arr.length; j++) { wordPerP[j] = Integer.parseInt(arr[j]); }System.out.println(main.getMaxSize(pNum, wordPerP, width, height, page)); } } }

}

##2. 403 Forbidden 题目大意：给出一些IP防火墙规则列表和测试IP，对每个测试IP，在规则列表中按照规则的**先后顺序**进行匹配，匹配成功就返回匹配的结果，allow返回YES，deny返回NO。规则列表中有的规则可能会带一个匹配值n，这样只要IP的二进制表示前n位匹配就算作匹配成功。样例输入：(第一行的数字代表规则条数和测试IP个数)

5 5
allow 1.2.3.4/30
deny 1.1.1.1
allow 127.0.0.1
allow 123.234.12.23/3
deny 0.0.0.0/0
1.2.3.4
1.2.3.5
1.1.1.1
100.100.100.100
219.142.53.100

样例输出：

YES
YES
NO
YES
NO

**解题思路**：直观想法，将给定IP转换成二进制串（关于Java中IP转换成二进制，请参考 [IP地址转化为二进制字符串](http://www.jianshu.com/p/d8ccd739a579))，进行遍历暴力匹配。提交，Time Limit, 得40分。 (⊙﹏⊙)。。。事后与同学讨论，又参考了相关赛后讨论思路，得知这道题应该是用Trie树解。相关解法思路和C++代码可以参阅 [微软2016校园招聘4月在线笔试题解(二)](http://www.gotit.sinaapp.com/wei-ruan-2016xiao-yuan-zhao-pin-4yue-zai-xian-bi-shi-ti-jie-er.html).这里给出我根据C++代码翻译来的Java版：

import java.util.Scanner;
/**

Created by Qing on 2016/4/16.
*/
public class Trie {
class TrieNode {
int order = 0; // 规则在规则列表中的顺序，deny规则的为负值。
TrieNode[] children = new TrieNode[2];
}
TrieNode root = new TrieNode();

//添加规则原则，若添加i的过程中，i路径已经包含了原有规则j，那么i的order肯定在j之后，直接将i抛弃。
public void add(String binStr, int order, int mask) {
TrieNode node = root;
for (int i = 0; i < mask; i++) {
if (node.order != 0) {
return;
}
char a = binStr.charAt(i);
int aInt = a - '0';
if (node.children[aInt] == null) {
node.children[aInt] = new TrieNode();
}
node = node.children[aInt];
}
if (node.order == 0) {
node.order = order;
}
}
//检测一个IP匹配的规则，只需检测最长匹配的规则（思考，为什么？考虑一下我们构造树的逻辑）
public int find(String binStr) {
TrieNode node = root;
int order = 1;
for (int i = 0; i < 32; i++) {
if (node.order != 0) {
order = node.order;
}
char a = binStr.charAt(i);
int aInt = a - '0';
if (node.children[aInt] == null) {
break;
}
node = node.children[aInt];
}
return order;
}

public static String ip2BinStr(String ip) { String[] arr = ip.split("\\."); String rs = ""; for (String str : arr) { String s = Integer.toBinaryString(Integer.parseInt(str)); if (s.length() < 8) { int diff = 8 - s.length(); for (int i = 0; i < diff; i++) { s = "0" + s; } } rs += s; } return rs; }public static void main(String[] args) { Scanner scanner = new Scanner(System.in); Trie trie = new Trie(); String fLine = scanner.nextLine(); int ruleNum = Integer.parseInt(fLine.split(" ")[0]); int ipNum = Integer.parseInt(fLine.split(" ")[1]); for (int i = 1; i <= ruleNum; i++) { int mask = 32; String line = scanner.nextLine(); String[] lineArr = line.split(" "); int order = lineArr[0].equals("allow") ? i : -i; String ipRule = lineArr[1]; if (ipRule.contains("/")) { String[] arr = ipRule.split("/"); ipRule = arr[0]; mask = Integer.parseInt(arr[1]); } trie.add(Trie.ip2BinStr(ipRule), order, mask); } for (int i = 0; i < ipNum; i++) { System.out.println(trie.find(Trie.ip2BinStr(scanner.nextLine())) < 0 ? "No" : "YES"); } }

}

## 3. Demo Day 题目大意：说现在有一个机器人走一个矩阵型的迷宫，入口在左上角，出口在右下角，矩阵的每个点是障碍或者通道，由于机器人出了问题，只能向右或者向下两个方向走，并且一旦选定方向就一直走，直到碰到障碍才会改变方向。这样有的迷宫机器人走不出去，我们可以改变节点（障碍变成通道或者通道编程障碍），现在给你一个无法走出的迷宫，求最少改变几个节点能使得机器人顺利通过迷宫？输入，矩阵的行，列，每个点的状况（b代表障碍，·代表通道）。样例输入

4 8
....bb..
........
.....b..
...bb...

样例输出

【微软2016实习生招聘4月份笔试题目】1

**解题思路**：容易看出这是一道动态规划的题目。动态规划的简单介绍可以参考我之前的笔记[动态规划、LCS、01背包问题](http://www.jianshu.com/p/9e6f5126ecaa)。然而就这道题来说，如何下手对我这个菜鸟来说并不容易很快想出来。感觉当时我思考的思路还是局限在矩阵和子矩阵之间最优解的关系。后来参考讨论区的帖子[微软2016校园招聘4月在线笔试题解(三)](http://www.gotit.sinaapp.com/wei-ruan-2016xiao-yuan-zhao-pin-4yue-zai-xian-bi-shi-ti-jie-san.html), 才明白该从每个点和上一步的点之间的关联入手。一个至关重要的信息是每个点都会有两种方向可能，对每种方向，我们也要考虑他是从上方过来还是左方过来的。关键之处是列出最优解和子问题最优解之间的等式：

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');