天津建站模板搭建,电子商务网页设计与网站建设论文,有哪些企业网站,j2ee网站开发参考文献java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 广度优先双分裂蛇 广度优先双分裂蛇 双分裂蛇#xff1a;是求二…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.6771.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;//走了多少步两个队列(贪吃蛇)一起算//头尾队列一个从头走一个从尾巴走两个队列相遇就是一个答案QueueNode headQue new LinkedListNode();QueueNode tailQue new LinkedListNode();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队列步数1steps;//B队列走一步是否相遇A队列encounter nextStep(grid, tailQue, SIGN_B);if(encounter) return steps;steps;}return -1;//如果一直没有相遇就返回-1}//走一步private boolean nextStep(int [][]grid, QueueNode 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;// 记录坐标Queueint[] queue new LinkedList();//单分裂蛇queue.offer(new int[]{0,0});//从起点开始grid[0][0] 1;//走过的就标志为1int 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];//返回到终点的最短路径长度}
}
