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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/company-tag/google.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.