首页 > 编程语言 >java数据结构与算法刷题-----LeetCode1091. 二进制矩阵中的最短路径

java数据结构与算法刷题-----LeetCode1091. 二进制矩阵中的最短路径

时间:2024-03-31 10:31:38浏览次数:31  
标签:结点 java int 路径 队列 分裂 ----- LeetCode1091 grid

java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

文章目录

在这里插入图片描述
在这里插入图片描述

广度优先+双分裂蛇

双分裂蛇:是求二维表中从起点到终点的经典思路(也是求无权图的最短路径问题的经典解法)。创建两条分裂蛇,分别从起点和终点出发,两者相遇,则找到一条路径。时间复杂度理论上和单分裂蛇一样,但实际效率双分裂蛇更高。

  1. 分裂蛇的意思是:如果遇到分叉路,分裂蛇A可以分裂成对应数量的蛇,然后分头行动。
  2. 为什么双分裂蛇更快?因为只有一条蛇时,最坏情况下所有结点都走一遍才能找到最短路径
  3. 双分裂蛇,无论分裂多少,肯定是最短路径上的两条蛇最先相遇。所以两条蛇初次相遇的路径,就是最短路径。而不用像单分裂蛇那样,很有可能将所有路走一遍再比较才能知道哪条路最短

简单来说,单分裂蛇,它需要走的步数更多,因为它要自己从起点走到终点,因此分裂的蛇也就越多,访问的结点也就越多。
而双分裂蛇,两条蛇走的步数都是单分裂蛇的一半。所以两条蛇分裂的蛇会很少。访问的结点就少

举个例子,一张可以无限对折的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)
  1. 创建两个队列A和B,当做分裂蛇,分别从起点[0][0]和终点[n-1][n-1]出发,将两个结点分别入各自的队列
  2. A队列先走一步,情况允许就分裂。新分裂出的蛇额外走
  1. 一步的含义是,我可以向8个方向走,只要能走就走。
  2. 分裂:如果多个方向都满足条件,则进行分裂,让分裂的蛇到达指定地点(一步),然后将分裂的蛇全部入队列
  3. 但是新入队列的蛇,不可以继续处理,因为它们已经走了一步了
  1. 如果两个队列没有相遇,B队列也走一步,情况允许就分裂,新分裂的不走
  2. 直到两个队列中有蛇相遇,就结束程序。因为双分裂蛇的特点就是,最先相遇的两条蛇所在路径为最短路径
代码:会给出双分裂蛇和单分裂蛇的两版代码,除了蛇的数量不一样,剩余代码全部一样,可以很明显的看见,双分裂蛇的效率高多了,比单分裂蛇效率高了40%
  1. 双分裂蛇版本用时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;
    }
}
  1. 单分裂蛇版本,用时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

相关文章

  • java数据结构与算法刷题-----LeetCode95. 不同的二叉搜索树 II
    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846文章目录分治回溯+记忆化搜索分治回溯+记忆化搜索卡特兰数,例如对于n个进栈元素,有多少种出栈顺序,......
  • 18day-19day-2.2.CSS实战与提高
    2.2.CSS实战与提高练习11:制作开心餐厅页面CSS/*层次选择器*/p{font-size:14px;}/*body后代h2字体16px*/bodyh2{font-size:16px;}/*第一个h2颜色变为红色*/.firstH2{color:red;}/*第一个h2后面的通用兄弟元素h2变为蓝色*/.firstH2~h2{......
  • 矩阵置零 - LeetCode 热题 18
    大家好!我是曾续缘......
  • 缺失的第一个正数 - LeetCode 热题 17
    大家好!我是曾续缘......
  • java毕业设计社团物品租赁小程序(Springboot+mysql+jdk1.8+maven3.39)
    本系统(程序+源码)带文档lw万字以上 文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义一、选题背景:随着校园文化的繁荣和学生社团活动的增多,各类社团对于特定物品的需求日益增长。这些物品包括活动器材、会议设备、表演服装等,购买成本高且使用频率不......
  • java毕业设计汽车服务系统(Springboot+mysql+jdk1.8+maven3.39)
    本系统(程序+源码)带文档lw万字以上 文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义选题背景:随着科技的进步和汽车产业的迅猛发展,汽车行业的竞争已经从单纯的价格竞争逐渐转向服务竞争。消费者对汽车服务的需求日益增长,不仅关注汽车的性能、外观和......
  • 【2024年5月备考新增】《软考真题分章练习(含答案解析) - 14 组织级项目管理(高项)》
    1题目1、办公软件开发公司A非常重视软件过程管理,按照CMMI(能力成熟度模型)逐步进行过程改进,刚刚实现了组织级过程性能、定量项目管理,按照CMMI(能力成熟度模型),A公司达到了()级别。A.CMMI2B.CMMI3C.CMMI4D.CMMI52、CMMI的连续式表示法与阶段式表示法分别表示:()。A.项......
  • 6-92 链表基本操作(Python语言描述)
    本题要求在给出的链节点类、和单链表类部分代码的情况下,编写好基本操作的各种python3代码实现,最后调用测试代码检验。函数接口定义:已实现的链节点类、和单链表类部分代码。如下:classSingleNode(object):"""单链表的结点"""def__init__(self,item):#_i......
  • java毕业设计社团管理系统(Springboot+mysql+jdk1.8+maven3.39)
    本系统(程序+源码)带文档lw万字以上 文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义选题背景:随着高校教育的不断发展,学生社团作为校园文化的重要组成部分,承担着丰富学生课余生活、培养学生兴趣爱好、提升学生实践能力的重要职能。然而,传统的社团管......
  • java毕业设计实验室资源管理(Springboot+mysql+jdk1.8+maven3.39)
    本系统(程序+源码)带文档lw万字以上 文末可领取本课题的JAVA源码参考系统程序文件列表系统的选题背景和意义一、选题背景:在高等教育和科研机构中,实验室是进行教学和科学研究的重要场所。一个现代化的实验室通常拥有大量昂贵的设备、仪器和材料。如何有效地管理这些资源,确......