Walls and Gates
这题乍看之下特别像滑雪，于是想试试用 DFS + memoization，于是有了下面的代码，过了 25/62 个 test cases ，错在了一个
- [0 , INF, 0, INF, INF]
- [-1, -1 , 0 , -1 , INF]
- [-1 , 0 , 0 , 0 , INF]
- [-1 , INF , 0 , 0 , -1]
这样的 test case 上。
其原因是，当我们搜索 (0, 4) 这个位置时，dfs 搜索了相邻的 (0, 5)，这时候遇到了比较尴尬的境地:
- 为了避免死循环，我们要把当前元素改一下，免得下一步的 dfs 重新探回来；
- 但是在这个局部上，正解却偏偏要探回来，往左走才能碰到最近的 0.
于是我们发现了这题和滑雪最大的不同：滑雪由于取值限制，是不用担心回头路的，但这题会。留回头路会死循环，不留回头路会算错。
于是下面的代码在如上的 test case 上会挂掉；
public class Solution {
public void wallsAndGates(int[][] rooms) {
for(int i = 0; i < rooms.length; i++){
for(int j = 0; j < rooms[0].length; j++){
if(rooms[i][j] == Integer.MAX_VALUE) rooms[i][j] = memoizedSearch(rooms, i, j);
}
}
}
private int memoizedSearch(int[][] rooms, int x, int y){
if(x < 0 || x >= rooms.length) return Integer.MAX_VALUE;
if(y < 0 || y >= rooms[0].length) return Integer.MAX_VALUE;
if(rooms[x][y] == 0) return 0;
if(rooms[x][y] == -1) return Integer.MAX_VALUE;
if(rooms[x][y] == Integer.MAX_VALUE){
rooms[x][y] = -1;
int N = memoizedSearch(rooms, x - 1, y);
int S = memoizedSearch(rooms, x + 1, y);
int W = memoizedSearch(rooms, x, y - 1);
int E = memoizedSearch(rooms, x, y + 1);
int min = Math.min(Math.min(N, S), Math.min(W, E));
if(min == Integer.MAX_VALUE){
rooms[x][y] = Integer.MAX_VALUE;
return rooms[x][y];
} else {
rooms[x][y] = min + 1;
return rooms[x][y];
}
} else {
return rooms[x][y];
}
}
}
“和最短距离” 相关的问题，最靠谱的还是BFS 解法。
一个最容易想到的做法是，每个 INF 为起点，扫整个矩阵。每个起点走的最长距离是 O(mn)，总共有 O(mn) 个能的起点，所以复杂度为 O(m^2 * n^2)，太慢了。
改良版本是，我们不从 INF 的角度开始，而是反过来，从 0 开始往回找，沿路只添加看到的 INF; 由于是 BFS，从gate出发，第一次看到某个房间的时候就是最短距离。这样我们有 O(mn) 个可能的起点和位置要搜，然而每个位置只会进入队列一次，所以时间和空间复杂度都是 O(mn).
每个位置只看一次，并不一定要靠记忆化搜索，DFS / BFS flood filling 一样可以。事实上，大多数都是靠 flood filling，靠记忆化搜索的反而是少数。
另一个小技巧是，处理矩阵不一定非要拍成一维 index，队列里直接扔 int[] 也完全可以，还省事。
需要注意的是如果gates被INF包围, 则永远都不会搜索到的, 这个时候要用bi-direction search
DFS解法
public void wallsAndGates(int[][] rooms) {
for(int i=0;i<rooms.length;i++)
for(int j=0;j<rooms[0].length;j++){
if(rooms[i][j] == 0)
bfs(rooms, i, j, 0);
}
}
public void bfs(int[][] rooms, int x, int y, int step){
int m = rooms.length;
int n = rooms[0].length;
if(x<0 || x>=m || y<0 || y>=n || rooms[x][y] < step){
return;
}
rooms[x][y] = step;
bfs(rooms, x-1, y, step+1);
bfs(rooms, x+1, y, step+1);
bfs(rooms, x, y-1, step+1);
bfs(rooms, x, y+1, step+1);
}
BFS解法
public class Solution {
public void wallsAndGates(int[][] rooms) {
if(rooms == null || rooms.length == 0) return;
int rows = rooms.length;
int cols = rooms[0].length;
Queue<int[]> queue = new LinkedList<>();
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(rooms[i][j] == 0) queue.offer(new int[]{i, j});
}
}
int distance = 1;
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
int[] cur = queue.poll();
int[] xDir = {0,0,-1,1};
int[] yDir = {-1,1,0,0};
for(int j = 0; j < 4; j++){
int[] next = {cur[0] + xDir[j], cur[1] + yDir[j]};
if(next[0] >= 0 && next[1] >= 0 && next[0] < rows && next[1] < cols){
if(rooms[next[0]][next[1]] == Integer.MAX_VALUE){
rooms[next[0]][next[1]] = distance;
queue.offer(next);
}
}
}
}
distance ++;
}
}
}
先说一下自己第一个不成功的尝试，那就是一维推导错了，以为是所有 X 坐标的平均值。+
在一维情况下：
只有一个点
取当前点的位置；
有两个点
两点之间的任何位置都是等价的，等于区间大小；
有三个点
最外面两点之间的任意位置等价，距离和等于区间大小；
于是剩下一个点，可以发现最优位置就是在点上；
有 N 个点
我们可以对于排序了的坐标从外向里配对消除，每一对的距离等于这对点形成的区间大小。
于是我我们可以总结为：
点的个数为偶数，则最里面 pair 之间的任意位置等价；
点的个数为奇数，则一定在最里面的中心点上；
因此，最优点就是当前维度的中位数。
于是一个最直观的解法就是，记录所有的 "1" 的 X/Y 坐标，选中位数，再把所有的地方过一遍。
扫哪里是 1 + 用两次 quick select + 计算总的距离
O(mn) + O(m) + O(n) + O(m) + O(n) = O(mn)
不过从提交速度上看，这个解法速度不理想，而且写个 quick select 代码量就上去了，面试时候有点浪费时间。
论坛上还有一个很有趣的解法，虽然时间复杂度不好看，但是思路巧妙，简洁易懂。
核心思想在于，最优 meeting point 一定是在所有点的中间，而对于每个 pair ，他们到 best meeting point 的距离和就是 pair 两点的区间长度，所以假设以 0 为远点，用双指针检查每一对就可以了。
实际上, best meeting point, 如果所有点都在同一行或者同一列的时候, point一点在中点, distance是左右或上下pair点的区间和. 现在点不在同一行列上了, 实际上映射到同一行列就可以了, 最后距离distance = min(行)+min(列)
public int minTotalDistance(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
List<Integer> I = new ArrayList<>(m);
List<Integer> J = new ArrayList<>(n);
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 1){
I.add(i);
J.add(j);
}
}
}
return getMin(I) + getMin(J);
}
private int getMin(List<Integer> list){
int ret = 0;
Collections.sort(list);
int i = 0;
int j = list.size() - 1;
while(i < j){
ret += list.get(j--) - list.get(i++);
}
return ret;
}
如果进一步利用循环的特点，甚至排序都可以省了，ArrayList 里自动就是排好序的。不过会扫两次 O(mn)，就有一个取舍的问题在里面了
public class Solution {
public int minTotalDistance(int[][] grid) {
int m = grid.length, n = grid[0].length;
List<Integer> I = new ArrayList<Integer>();
List<Integer> J = new ArrayList<Integer>();
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == 1) {
I.add(i);
}
}
}
for(int j = 0; j < n; j++) {
for(int i = 0; i < m; i ++) {
if(grid[i][j] == 1) {
J.add(j);
}
}
}
return minTotalDistance(I) + minTotalDistance(J);
}
public int minTotalDistance(List<Integer> grid) {
int i = 0, j = grid.size() - 1, sum = 0;
while(i < j) {
sum += grid.get(j--) - grid.get(i++);
}
return sum;
}
}
Shortest Distance from All Buildings
乍看之下是上一题的强化版，因为所谓“距离”的定义是一样的，都是曼哈顿距离。最主要的不同点在于，中间有障碍之后，问题就不再是简单的分开维度拆分分析了，因为对于每一个位置，都要考虑障碍物的具体位置。+
因此不难看出，这题变成了一个 Graph 问题，因为对于矩阵中任意两点 A & B，其最短距离只有靠 BFS 去查。 矩阵就是一种 uniform weight, undirected graph.
一个非常土的办法是，先扫一遍矩阵，找到 k 个起始点；对于每一个起始点开始做 BFS，记录到每一个其他格子的距离，每次扫完了要存这个位置到起点的距离，并且每次扫完一个点要恢复矩阵的访问状态，免得下一次扫描出错，扫到第 k 个起点的时候，把每个 cell 里面的相对于其他店的距离加起来，保持一个 min 就可以了。
时间复杂度： 2k * O(mn) ，考虑到 k 可能等于整个矩阵，其实是 O(m^2 * n^2)
空间复杂度： k * O(mn)，考虑到 k 可能等于整个矩阵，其实时 O(m^2 * n^2)
我觉得这个思路可以不用写代码了，肯定要超时的。。
这个时间复杂度和暴力解 Walls and Gates 一样，不难想到，可以试着从每个 "1" 出发，去反过来探索矩阵。 假如我们记录了这 k 个起始点，我们可以依次 bfs 每一个起始点 / 该起始点的范围，一次一个点，一次扩张一轮，当 k 个点的 “势力范围” 第一次相交的时候，就是我们要找的最优起点。有了最优起点，O(mn) 的时间显然就可以算出最短距离。
问题一 : 如何保证对于固定起点的 BFS 过程中，不走回头路，而且相邻边界不重复添加；
问题二：如何解决多个起点 BFS 之间的覆盖问题？
问题三：对于某一个被若干个队列中边界点包围的位置，我们怎么判断每次试图访问的时候，是同一个起点的重复访问（此时跳过），还是另一个起点的回合点（此时保留）？
可以看到，在 Walls and Gates 中，这两个问题是不存在的，因为当一个位置被某个 BFS 发现之后，最短距离就确定了，后面的所有 BFS 也都不会再去访问了，一口气解决了 “相邻边界重复添加” 和 “不同起点覆盖搜索” 两个问题。
经过了半天的思考之后，依然没能找到接近 O(mn) 的解法，于是我就跑去 LC 论坛看答案了。你妹啊，你们用的也是我一开始的挫算法。。。。所以如果真是面试头一次碰到这种题，不要犹豫，就先撸个最暴力的办法再说。
这个题实际上还可以考很多变法
目标和起点相对数量. 比如如果0比1多, 或者1比0多, 应该选择从1还是搜索, 还是从0开始搜索
障碍物是否会完全包括起点或者目标. 这个时候是否考虑用bi-direction search
public class Solution {
public int shortestDistance(int[][] grid) {
if(grid==null) return 0;
int m = grid.length; int n = grid[0].length;
int[][] numReached = new int[m][n]; int[][] distance = new int[m][n]; int numBuilding = 0;
final int[] shift = new int[] {0, 1, 0, -1, 0};
for(int i=0;i<m;i++)
for(int j=0;j<n;j++){
if(grid[i][j]==1){
numBuilding++;
boolean[][] isVisited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<int[]>();
Queue<Integer> dist = new LinkedList<Integer>();
queue.add(new int[]{i, j});
dist.add(1);
while(!queue.isEmpty()){
int[] cur = queue.poll();
int step = dist.poll();
for (int k = 0; k < 4; k++) {
int row = cur[0] + shift[k];
int col = cur[1] + shift[k + 1];
if(row>=0&&row<m&&col>=0&&col<n&&grid[row][col]==0&&isVisited[row][col]==false){
queue.offer(new int[]{row,col});
dist.offer(step+1);
numReached[row][col]++;
distance[row][col]+=step;
isVisited[row][col] = true;
}
}
}
}
}
int ans = Integer.MAX_VALUE;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++){
if(grid[i][j]==0 && numReached[i][j]==numBuilding)
ans = Math.min(ans, distance[i][j]);
}
return ans==Integer.MAX_VALUE?-1:ans;
}
}
01 Matrix
一开始直接搜素了，对每个点进行BFS，然后进行剪支，实际上这样有重复子问题，在对A点进行BFS的时候，同时也对B点进行了BFS，但是没有记录，也不好记录。37/48后TLE。
这类问题还是先将所有源点加入queue中，跑一遍BFS就可以解决。代码简洁高效。
public class Solution {
public int[][] updateMatrix(int[][] matrix) {
if(matrix==null || matrix[0].length==0)
return new int[0][0];
int m = matrix.length; int n=matrix[0].length;Queue<int[]> queue = new LinkedList<int[]>();
int[][] ans = new int[m][n]; for(int[] arr : ans) Arrays.fill(arr, Integer.MAX_VALUE);
for(int i=0;i<m;i++)
for(int j=0;j<n;j++){
if(matrix[i][j]==0) {ans[i][j]=0;queue.add(new int[]{i,j});}
}
int[][] direct = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
while(!queue.isEmpty()){
int[] cur = queue.poll();
for(int i=0;i<4;i++){
int nx = cur[0]+direct[i][0];
int ny = cur[1]+direct[i][1];
if(nx<0||ny<0||nx>=matrix.length||ny>=matrix[0].length||ans[nx][ny]<=ans[cur[0]][cur[1]]+1) continue;
ans[nx][ny]=ans[cur[0]][cur[1]]+1;
queue.add(new int[]{nx,ny});
}
}
return ans;
}
}