Google 面试题 | 建邮局

返回6。

1. 因为这个题目要求无解的时候返回 -1 ，那么我们就先想一下无解的情况。

（1）网格不存在，即行数为0或者列数为0；
（2）网格存在，但是没有地方修，也就是没有空地。
 

之后就要开始要想如何解决这个问题了。

2. 题目是要求所有的房子到某一空地的最小曼哈顿距离和，那我们就有一个朴素的想法，直接枚举所有的空地，求出所有的房子到该空地的曼哈顿距离和，从这些距离和中选取最小的一个即可。

（ps：曼哈顿距离：dis=|x2-x1|+|y2-y1|）

伪代码：

接下来就是改进这个朴素的做法。

3. 观察上述伪代码，显然求所有的房子到某一点的曼哈顿距离和是可以通过预处理实现O(1)询问的。

这里就要先提到有关曼哈顿距离的一个常用技巧了：将曼哈顿距离拆分成 X 轴距离与 Y 轴距离。

设两个点：(x1,y1)、(x2,y2)
曼哈顿距离：dis=|x2-x1|+|y2-y1|

根据上面这个式子，我们就可以把求两个点的曼哈顿距离拆分成求两个点在 X 轴上的距离与求两个点在 Y 轴上的距离。

有了这个拆分，就有了预处理的基础。 

4. 我们现在以对 X 轴距离做预处理为例进行讲解。

我们先预处理出一个rowSum数组，rowSum[i]记录第 i 行一共有几个房子。

那么对于一个点(i,j)，从第 0 。。。i 行的所有房子到该点的 X 轴距离和即等同于从第0。。。i 行的所有房子到第 i 行的 X 轴距离和。

用prefixSum1[i]表示从第0。。。i 行的所有房子到第 i 行的一共有多少房子；
用prefixSum2[i]表示从第0。。。i 行的所有房子到第 i 行的X 轴距离和，即得到下式：

根据推导的式子，prefixsum1与prefixsum2都可以通过O(row)的预处理得到。

这样我们就得到了从第0。。。i 行的所有房子到第 i 行的 X 轴距离和。

同理，还可以通过 O(row) 的预处理得到从第 i 。。。n - 1 行的所有房子到第 i 行的 X 轴距离和。

将以上的两个预处理的值相加，即可得到：所有的房子到第 i 行的距离和，将其记为ansRow[i]。

综上，我们就可以通过O(row)的预处理得到所有房子到某一 行的距离和，并记录在ansRow[] 数组里。

5. 通过与第四点相同的思路，我们可以通过一个O(column)的预处理得到所有房子到某一列的距离和，并记录在ansColumn[] 数组里。

于是，所有房子到某一点(i,j)的曼哈顿距离和即为：ansRow[i] + ansColumn[j]。
代码的总体复杂度就下降到了O(row*column)。