Google

1.自行车和人匹配问题

描述

2D平面上，有m个人（P），n辆自行车(B)，还有空白（O）满足以下条件

1.m < n

2.不存在两个人，到同一辆自行车距离相等, 距离用abs(x1-x2) + abs(y1-y2)定义

3.每个人尽量找离自己最近的自行车，一旦某辆自行车被占，其他人只能找别的自行车。

例：

OPOBOOP
OOOOOOO
OOOOOOO
OOOOOOO
BOOBOOB

红色的人(0, 1)找到第一行的自行车(0, 3)，距离最近。

蓝色的人(0, 6)离第一行自行车(0, 3最近，但自行车已经被红色人占有，所以他只能找离他第二近的，右下角的自行车(4,6)。

问：把人和自行车配对，输出vector<pair<int, int>>每个人对应的自行车. {i, j} 是人i对应自行车j

思路

Summary:

1. 需要跟面试官讨论清楚他需要的最佳匹配是什么

2. 如果是要求全局人车距离最短

   1. 二分图的最佳匹配问题，使用匈牙利算法，参考题目https://blog.csdn.net/u011721440/article/details/3816920

   2. 发现这里不能使用max flow， 因为这个bipartite is a weighted graph. 参考 https://www.topcoder.com/community/competitive-programming/tutorials/assignment-problem-and-hungarian-algorithm/

3. 如果是要求最佳匹配只是给每个人匹配到车，可以用PQ+Map

2.机器人左上到右上的可能路径数量

LC类似题目: LC 62 Unique Paths 和 LC 63 Unique Paths II

描述

给定一个矩形的宽和长，求所有可能的路径数量 Rules： 1. 从左上角走到右上角 2. 机器人只能走右上，右和右下

思路：

按照列dp, dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1] + dp[i + 1][j - 1]， 注意i-1，i+1需要存在

解法：

2D Dynamic Programming - Time O(mn), Space O(mn)

public static int uniquePaths(int rows, int cols) {
    int[][] dp = new int[rows][cols];
    dp[0][0] = 1;
    for(int j = 1 ; j  < cols ; j++) {
        for(int i = 0 ; i < rows ; i++) {
            int val1 = i - 1 >= 0 ? dp[i - 1][j - 1] : 0;
            int val2 = dp[i][j - 1];
            int val3 = i + 1 < rows ? dp[i + 1][j - 1] : 0;
            dp[i][j] = val1 + val2 + val3;
        }
    }
    return dp[0][cols - 1];
}

优化空间 - 滚动数组 DP - Time O(mn), Space O(m)

public static int uniquePathsI(int rows, int cols) {
    int[][] dp = new int[rows][2];
    dp[0][0] = 1;
    for(int j = 1 ; j  < cols ; j++) {
        for(int i = 0 ; i < rows ; i++) {
            int val1 = i - 1 >= 0 ? dp[i - 1][(j - 1) % 2] : 0;
            int val2 = dp[i][(j - 1) % 2];
            int val3 = i + 1 < rows ? dp[i + 1][(j - 1) % 2] : 0;
            dp[i][j % 2] = val1 + val2 + val3;
        }
    }
    return dp[0][(cols - 1) % 2];
}

进一步优化 - 1维DP (省略cols维度，每一列复用上一列信息)

public static int uniquePathsII(int rows, int cols) {
    int[] dp = new int[rows];
    dp[0] = 1;
    for(int j = 1 ; j  < cols ; j++) {
        for(int i = 0 ; i < rows ; i++) {
            int val1 = i - 1 >= 0 ? dp[i - 1] : 0;
            int val2 = dp[i];
            int val3 = i + 1 < rows ? dp[i + 1] : 0;
            dp[i] = val1 + val2 + val3;
        }
    }
    return dp[0];
}