> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/company-tag/google.md).

# 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**](https://blog.csdn.net/u011721440/article/details/38169201)
   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)

```java
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)

```java
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维度，每一列复用上一列信息)

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