Leetcode: Google interview questions - Round 2 - #3 - 他人汇总
莉蔻三九九及其变种（汇率）频率：21
就是一个2维数组里的有人和自行车，要每个人匹配到一辆自行车，人和自行车的距离越短越好，没有距离相同的情况。就是算出所有的距离然后放到heap里慢慢pop出来，记录下人和车的状态就可以了。
频率：13
再跟一下
利口六八四 六八五及其变种（bst删除额外边）
频率：10
-baidu 1point3acres
利口六二
著名变种：DP。给定一个矩形的长宽，用多少种方法可以从左上角走到右上角 （每一步，只能向正右、右上 或 右下走）：整个矩形遍历做DP即可，不需要想复杂. 牛人云集,一亩三分地
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | public static void main(String[] ss) { System.out.println(ways(7, 6));}public static int ways(int m, int n) { int[][] dp = new int[m + 2][n]; dp[1][0] = 1; for (int i = 1; i < n; i++) { for (int j = 1; j < m + 1; j++) { dp[j][i] = dp[j - 1][i - 1] + dp[j][i - 1] + dp[j + 1][i - 1]; } } return dp[1][n - 1];} |
Solution, 所有路径必须经过这3个点，求一共有多少种走法（到达右上）
其实这3个点跟起点和终点没有区别。如果存在这3个点，则这5个点中的任意2个点不可能存在在一个column上。按column来划分矩形，分别对两两做dp
可以写一个方法
int ways(int m, int n, int[] start, int[] end, int startCount) 来避免代码重复
-follow up：如何判断这三个点一个是合理的，即存在遍历这三个点的路经
Solution
2个相邻之间的点的连线与水平线的夹脚 <= 45度，就可以说明左边的点能到达右边的点。表示为 |y2 - y1| >= x2 - x1, 假设(x1, y1) (x2, y2) 为左右2点
-follow up：如果给你一个H，要求你的路径必须向下越过H这个界，怎么做 （别问我，我不会）
Solution
找出不越界的路线个数，原来的结果相减就得到越过的个数
楼主这题试一试用镜像做，也就是说重点不在(W, 0), 而在(W, 2H)， W是矩阵的宽度
频率：9
六口把四散（猜词）
843
频率：9
Read full article from Leetcode: Google interview questions - Round 2 - #3 - 他人汇总
No comments:
Post a Comment