java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846 |
---|
文章目录
广度优先+双分裂蛇
双分裂蛇:是求二维表中从起点到终点的经典思路(也是求无权图的最短路径问题的经典解法)。创建两条分裂蛇,分别从起点和终点出发,两者相遇,则找到一条路径。时间复杂度理论上和单分裂蛇一样,但实际效率双分裂蛇更高。
- 分裂蛇的意思是:如果遇到分叉路,分裂蛇A可以分裂成对应数量的蛇,然后分头行动。
- 为什么双分裂蛇更快?因为只有一条蛇时,最坏情况下所有结点都走一遍才能找到最短路径
- 而
双分裂蛇,无论分裂多少,肯定是最短路径上的两条蛇最先相遇
。所以两条蛇初次相遇的路径,就是最短路径
。而不用像单分裂蛇
那样,很有可能将所有路走一遍再比较才能知道哪条路最短
。简单来说,单分裂蛇,它需要走的步数更多,因为它要自己从起点走到终点,因此分裂的蛇也就越多,访问的结点也就越多。
而双分裂蛇,两条蛇走的步数都是单分裂蛇的一半。所以两条蛇分裂的蛇会很少。访问的结点就少举个例子,一张可以无限对折的0.0002米厚的纸,对折40次左右可以到月球,40次正好就是219902公里。而对折40次的一半左右,比如23次只有1.677公里。此时我搞两张纸各对折40次的一半,加起来是1.677+1.677 = 3.3公里左右
可见,
219902公里是一张纸对折40次的结果
。3.3公里左右是两张纸对折40次一半20次左右的结果
. 而回到分裂蛇的例子。一条蛇分裂40次,和两条蛇各分裂20次。谁访问的结点更少呢?
因此理论上,最坏情况下双分裂蛇和单分裂蛇都是n^2的时间复杂度,也就是每个结点访问两次,但是实际上,找最短路径,就和一张纸对折40次和两张纸对折20次的区别是一样的,只要路径足够长,双分裂蛇访问的结点个数,和单分裂蛇访问的结点个数根本不是一个量级,
就像一张纸对折40次上月球,两张纸对折20次加起来走不出一个小区是一个道理。双分裂蛇的效率是比单分裂蛇高的。
但是无论单分裂蛇还是双分裂蛇,找最短路径,都满足:初次相遇的蛇所在路径为最短路径。
也就是,就算是单分裂蛇,也不需要所有路径走一遍统计路径长度,才能找出最短的
因为最短路径上的蛇一定会先最先到达。(前提是所有蛇的速度一样,都是大家一起一步一步走)
解题思路:时间复杂度O( n 2 n^2 n2),空间复杂度O( n 2 n^2 n2) |
---|
- 创建两个队列A和B,当做分裂蛇,分别从起点[0][0]和终点[n-1][n-1]出发,将两个结点分别入各自的队列
- A队列先走一步,情况允许就分裂。新分裂出的蛇
不
额外走
- 一步的含义是,我可以向8个方向走,只要能走就走。
- 分裂:如果多个方向都满足条件,则进行分裂,让分裂的蛇到达指定地点(一步),
然后将分裂的蛇全部入队列
- 但是新入队列的蛇,不可以继续处理,因为它们已经走了一步了
- 如果两个队列没有相遇,B队列也走一步,情况允许就分裂,新分裂的不走
- 直到两个队列中有蛇相遇,就结束程序。因为双分裂蛇的特点就是,最先相遇的两条蛇所在路径为最短路径
代码:会给出双分裂蛇和单分裂蛇的两版代码,除了蛇的数量不一样,剩余代码全部一样,可以很明显的看见,双分裂蛇的效率高多了,比单分裂蛇效率高了40% |
---|
- 双分裂蛇版本用时6ms
class Solution {
final static int[] dx = {1, 1, 1, 0, 0, -1, -1, -1};//右下,下,左下,右,左,右上,上,左上
final static int[] dy = {1, 0, -1, 1, -1, 1, 0, -1};//右下,下,左下,右,左,右上,上,左上
final static int SIGN_A = 2;//A队列走过的路的标识
final static int SIGN_B = 3;//B队列走过的路的标识
class Node {//队列中的结点,保存x和y坐标
int x, y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public int shortestPathBinaryMatrix(int[][] grid) {
int n = grid.length;
if(grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
else if(grid[0][0] == 0 && n == 1) return 1;
int steps = 2;//走了多少步,两个队列(贪吃蛇)一起算
//头尾队列,一个从头走,一个从尾巴走,两个队列相遇,就是一个答案
Queue<Node> headQue = new LinkedList<Node>();
Queue<Node> tailQue = new LinkedList<Node>();
headQue.offer(new Node(0, 0));
tailQue.offer(new Node(n-1, n-1));
grid[0][0] = SIGN_A;
grid[n-1][n-1] = SIGN_B;
//两个队列一起走
while(!headQue.isEmpty() && !tailQue.isEmpty()) {
boolean encounter = nextStep(grid, headQue, SIGN_A);//A队列走一步,是否相遇B队列
if(encounter) return steps;//如果相遇,则返回步数
//没有相遇,则A队列步数+1
steps++;
//B队列走一步,是否相遇A队列
encounter = nextStep(grid, tailQue, SIGN_B);
if(encounter) return steps;
steps++;
}
return -1;//如果一直没有相遇就返回-1
}
//走一步
private boolean nextStep(int [][]grid, Queue<Node> que, int sign) {
int n = grid.length;
int size = que.size();
while((size--) > 0) {//如果当前队列有结点(无论多少个),那么这些结点只走一步,不多走,也就是这些结点走了一步后,过程中新添加的结点,本次不考虑
Node cur = que.poll();//出队列当前结点
int x = cur.x, y = cur.y;//获取其坐标
for(int i = 0; i < 8; ++i) {//8个方向按右下,下,左下,右,左,右上,上,左上的顺序走一下
int nx = x + dx[i];
int ny = y + dy[i];
//如果下标越界,或者要走的这一方向==1(此路不通),或者要走的这一方向当前队列已经走过了grid[nx][ny] == sign,就跳过
if(nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 1 || grid[nx][ny] == sign) continue;
// 如果要走的方向遇到了另一个队列,则说明相遇
if(grid[nx][ny] != 0) return true;//返回true
//如果没有相遇,向当前方向走一步
grid[nx][ny] = sign;
que.add(new Node(nx, ny));//添加到队列继续
}
}
return false;
}
}
- 单分裂蛇版本,用时10ms
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
if(grid[0][0] != 0)return -1;
if(grid.length == 1){
if(grid[0][0] == 0) return 1;
else return -1;
}
int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dy = {-1, 0, 1, -1, 1, -1, 0,1};
int n = grid.length;
// 记录坐标
Queue<int[]> queue = new LinkedList();//单分裂蛇
queue.offer(new int[]{0,0});//从起点开始
grid[0][0] = 1;//走过的就标志为1
int length = 0;//路径长度
loop:while(queue.size() > 0){//如果还有分裂蛇存在
int size = queue.size();//获取当前分裂蛇,这些分裂蛇可以进行分裂,然后走一步
++length;//走一步+1个路径长度
while((size--) > 0){//只有当前分裂蛇可以走一步,多条路可走就分裂,新的分裂蛇不可以走,如果使用queue.size()会将新的分裂蛇也处理了
int[] pos = queue.poll();//依次获取这些现在存在的分裂蛇
for(int i =0; i < 8; i++){//从8个方向走
int x = pos[0] + dx[i];
int y = pos[1] + dy[i];
//如果这个方向可以走,并且没有分裂蛇走过
if(x >=0 && y >= 0 && x < grid.length && y < grid.length && grid[x][y] == 0){
queue.offer(new int[]{x,y});//就分裂一条蛇过去,这条分裂后新进入队列的蛇,本次不可以再处理
grid[x][y] = length +1;//将此结点标志为已到达过,赋值为:路径长度+1
//这里很重要,终点一定是最短路径的蛇先到,此时它会将这个结点标志为已到访过
//后面在较长路径的蛇,不会覆盖这个值
//如果当前分裂蛇是第一个到终点的,则他就是最短路径上的蛇
if(x == grid.length-1 && y == grid.length-1) break loop;//跳出整个循环,不继续处理任何蛇
}
}
}
}
return grid[n-1][n-1] <2 ? -1 : grid[n-1][n-1];//返回到终点的最短路径长度
}
}
标签:结点,java,int,路径,队列,分裂,-----,LeetCode1091,grid
From: https://blog.csdn.net/grd_java/article/details/137090602