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:
如果是要求最佳匹配只是给每个人匹配到车,可以用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];
}