这题乍看之下特别像滑雪,于是想试试用 DFS + memoization,于是有了下面的代码,过了 25/62 个 test cases ,错在了一个
这样的 test case 上。
其原因是,当我们搜索 (0, 4) 这个位置时,dfs 搜索了相邻的 (0, 5),这时候遇到了比较尴尬的境地:
为了避免死循环,我们要把当前元素改一下,免得下一步的 dfs 重新探回来;
但是在这个局部上,正解却偏偏要探回来,往左走才能碰到最近的 0.
于是我们发现了这题和滑雪最大的不同:滑雪由于取值限制,是不用担心回头路的,但这题会。留回头路会死循环,不留回头路会算错。
于是下面的代码在如上的 test case 上会挂掉;
Copy 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[] 也完全可以,还省事。
Copy 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 代码量就上去了,面试时候有点浪费时间。
Copy public class Solution {
public int minTotalDistance ( int [][] grid) {
if (grid == null || grid . length == 0 ) return 0 ;
List < Integer > listX = new ArrayList <>();
List < Integer > listY = new ArrayList <>();
for ( int i = 0 ; i < grid . length ; i ++ ){
for ( int j = 0 ; j < grid[ 0 ] . length ; j ++ ){
if (grid[i][j] == 1 ){
listX . add (i);
listY . add (j);
}
}
}
int medianX = findMedian(listX , 0 , listX . size() - 1 ) ;
int medianY = findMedian(listY , 0 , listY . size() - 1 ) ;
int minDis = 0 ;
for ( int x : listX){
minDis += Math . abs (medianX - x);
}
for ( int y : listY){
minDis += Math . abs (medianY - y);
}
return minDis;
}
private int findMedian ( List < Integer > list , int start , int end){
int pivot = list . get (start);
int left = start;
int right = end;
while (left <= right){
while (left <= right && list . get (left) <= pivot) left ++ ;
while (left <= right && list . get (right) >= pivot) right -- ;
if (left < right) swap(list , left , right) ;
}
swap(list , start , right) ;
int medianIndex = list . size () / 2 ;
if (right == medianIndex){
return list . get (right);
} else if (right < medianIndex){
return findMedian(list , right + 1 , end) ;
} else {
return findMedian(list , start , right - 1 ) ;
}
}
private void swap ( List < Integer > list , int a , int b){
int temp = list . get (a);
list . set (a , list . get (b));
list . set (b , temp);
}
}
论坛上还有一个很有趣的解法,虽然时间复杂度不好看,但是思路巧妙,简洁易懂。
核心思想在于,最优 meeting point 一定是在所有点的中间,而对于每个 pair ,他们到 best meeting point 的距离和就是 pair 两点的区间长度,所以假设以 0 为远点,用双指针检查每一对就可以了。
Copy 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),就有一个取舍的问题在里面了。
Copy 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;
}
}
乍看之下是上一题的强化版,因为所谓“距离”的定义是一样的,都是曼哈顿距离。最主要的不同点在于,中间有障碍之后,问题就不再是简单的分开维度拆分分析了,因为对于每一个位置,都要考虑障碍物的具体位置。
因此不难看出,这题变成了一个 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 论坛看答案了。你妹啊,你们用的也是我一开始的挫算法。。。。所以如果真是面试头一次碰到这种题,不要犹豫,就先撸个最暴力的办法再说。
痛定思痛,一次撸完AC,速度超过 89.66%
开个 int[][] 记录每个位置相对于每个点的最短距离,每一个 (i , j) 的值只会在一次探索中被更新一次,取值叠加;
用负数作为 flag ,代表探索进度。有两个明显的好处:
剪枝,扫第 5 个起点的时候,对于 flag = -2 的位置,连扫的必要都没有;
去重,每个起点的 BFS 都需要机制来避免重复添加,而 flag 是天然的状态指示,如果当前位置的 flag 和当前 BFS 的有效 flag 不相等,则直接跳过,起到了一个 undirected graph bfs 中的 0, 1, 2 状态功能~
每个起点的 BFS 都会更新其所有能碰到的 “有效点” 的最短距离,一个点在一次迭代中只会被访问一次。
因此最后只要扫一下 flag 矩阵,flag == curMark 的就是合理位置,找其对应的 disMap[][] 值,记录最小就可以了。
另一个优化是,可以在每一轮的 BFS 过程中检查当前最短距离,省去最后收尾扫描。不过对用时影响不大就是了,下面的代码没写那部分。
Copy public int shortestDistance( int [][] grid) {
if (grid == null || grid . length == 0 ) return 0 ;
int rows = grid . length ;
int cols = grid[ 0 ] . length ;
int [][] disMap = new int [rows][cols];
int minDis = Integer . MAX_VALUE ;
int curMark = 0 ;
for ( int i = 0 ; i < rows; i ++ ){
for ( int j = 0 ; j < cols; j ++ ){
if (grid[i][j] == 1 ){
bfs(grid , disMap , i , j , curMark) ;
curMark -- ;
}
}
}
for ( int i = 0 ; i < rows; i ++ ){
for ( int j = 0 ; j < cols; j ++ ){
if (grid[i][j] == curMark) minDis = Math . min (minDis , disMap[i][j]);
}
}
return minDis == Integer . MAX_VALUE ? - 1 : minDis;
}
private void bfs( int [][] grid , int [][] disMap , int x , int y , int curMark) {
int rows = grid . length ;
int cols = grid[ 0 ] . length ;
int distance = 1 ;
Queue < int []> queue = new LinkedList <>();
// Just found out using curMark can save the use of visited
queue . offer ( new int []{x , y});
while ( ! queue . isEmpty ()){
int size = queue . size ();
for ( int i = 0 ; i < size; i ++ ){
int [] cur = queue . poll ();
int curX = cur[ 0 ];
int curY = cur[ 1 ];
int [] xDirs = { 0 , 0 , 1 , - 1 };
int [] yDirs = { - 1 , 1 , 0 , 0 };
for ( int j = 0 ; j < 4 ; j ++ ){
int nextX = curX + xDirs[j];
int nextY = curY + yDirs[j];
if (nextX >= 0 && nextX < rows &&
nextY >= 0 && nextY < cols &&
grid[nextX][nextY] == curMark){
grid[nextX][nextY] = curMark - 1 ;
disMap[nextX][nextY] += distance;
queue . offer ( new int []{nextX , nextY});
}
}
}
distance ++ ;
}
}