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];
}

results matching ""

    No results matching ""