并查集练习 —岛屿数量(解法一)

题目:
给定一个二维数组matrix(char[][]),里面的值不是1就是0,上、下、左、右相邻的1认为是一片岛。返回matrix中岛的数量。
本题共有2种解法,本篇先介绍最快的一种解法—递归。

分析:
递归的方式做这道题代码最简单,也是最好理解的。递归方式采用“”感染“”的策略。

  1. 如果matrix[i][j] = ‘1’,则先将自己的值改为2的ASCII码,并且从我出发去感染上、下、左、右四个方向。
  2. 如果上、下、左、右中,也有matrix[i][j] = ‘1’的,同1中处理方式ASCII改成2,继续向外感染。
  3. 在最外层的2层for循环中,如果碰到matrix[i][j] = ‘1’,则变量isLand + 1,经历一次感染过程就相当于发现了一座岛,感染多少不用管,因为不管感染多少每次感染都是一座岛屿。
  4. 为什么改成2,因为如果不改成2,等到绿色1感染的时候,绿色1的上下左右还会回来,GG,死循环了。

比方说下图:
在这里插入图片描述

遍历从最上角红色1开始感染,会将上下左右所有的1都改成2,如果此时修改完后,又变回了1,等到绿色1再次感染时,如果变回1,还会重新感染。

代码:

   public static int numIslands1(char[][] board) {

        int isLand = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '1') {
                    isLand++;
                    infect(board,i,j);
                }
            }
        }
        return isLand;
    }

    public static void infect(char[][] board, int i, int j) {
        if (i < 0 || i == board.length || j < 0 || j == board.length || board[i][j] != '1') {
            return;
        }
        //如果是‘1’,改成2,并且上下左右去感染
        board[i][j] = 2;
        infect(board, i + 1, j);
        infect(board, i - 1, j);
        infect(board, i, j + 1);
        infect(board, i, j - 1);
    }

时间复杂度
如果二维数组行m,列n的话,整体复杂度就是 O ( m ∗ n ) O(m * n) O(mn)。虽然采用递归的方式,但是在主流程2个for循环中,所有数只循环了一遍,并且在感染过程里,需要修改成2的’1’,在下一次递归回来时,if条件不满足,直接renturn,‘0’的过程也是,所以所有数值走了一遍 O ( m ∗ n ) O(m * n) O(mn)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/61392.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

RadioButton基本使用

作用&#xff1a;单选框&#xff0c;一般用于设置或者选择某项任务。 常用属性&#xff1a; 常用事件&#xff1a; 选中事件 后台代码&#xff1a; private void radioButton1_CheckedChanged(object sender, EventArgs e){if (radioButton1.Checked){MessageBox.Show(radioB…

JVM之类加载与字节码

1.类文件结构 一个简单的HelloWorld.Java package cn.itcast.jvm.t5; // HelloWorld 示例 public class HelloWorld { public static void main(String[] args) { System.out.println("hello world"); } }编译为 HelloWorld.class 后的样子如下所示&#xff1a; […

SpringBoot3---核心特性---2、Web开发II

星光下的赶路人star的个人主页 大鹏一日同风起&#xff0c;扶摇直上九万里 文章目录 1、内容协商1.1 多端内容适配1.1.1 默认规则1.1.2 效果演示1.1.3 配置协商规则与支持类型 1.2 自定义内容返回1.2.1 增加yaml返回支持 1.2.2 思考&#xff1a;如何增加其它1.2.3 HttpMessageC…

Flutter 实现按位置大小比例布局的控件

文章目录 前言一、如何实现&#xff1f;1、数值转成分数2、RowFlexible布局横向3、ColumnFlexible布局纵向 二、完整代码三、使用示例1、基本用法2、四分屏3、六分屏4、八分屏5、九分屏6、414分屏 总结 前言 做视频监控项目时需要需要展示多分屏&#xff0c;比如2x2、3x3、414…

docker安装MinIO

简介 Minio 是一个面向对象的简单高性能存储服务。使用 Go 语言编写&#xff0c;性能高、具有跨平台性。 Minio 官网为&#xff1a;https://min.io &#xff0c;有一个中文站点&#xff0c;单内容更新不是很及时&#xff0c;建议从原始官网学习。 本文采用 Docker 安装&…

grid map学习笔记3之详解grid_map_pcl库实现point cloud点云转换成grid map栅格地图

文章目录 0 引言1 grid_map_pcl示例1.1 主要文件1.2 示例数据1.3 启动文件1.4 配置文件1.5 主要实现流程1.6 启动示例1.7 示例结果 2 D435i 点云生成栅格地图2.1 D435i 点云文件2.2 修改启动文件2.3 测试和结果2.4 修改配置文件2.5 重新测试和结果 0 引言 grid map学习笔记1已…

Go学习第六天

Golang变量内置pair结构详细说明 变量包括&#xff08;type, value&#xff09;两部分type 包括 static type和concrete type. 简单来说 static type是你在编码是看见的类型(如int、string)&#xff0c;concrete type是runtime系统看见的类型类型断言能否成功&#xff0c;取决…

electron+vue3全家桶+vite项目搭建【25】使用electron-updater自动更新应用

文章目录 引入实现效果实现步骤引入依赖配置electron-buidler文件封装版本升级工具类主进程调用版本更新校验渲染进程封装方法调用 测试版本更新 引入 demo项目地址 electron-updater官网 我们不可能每次发布新的版本都让用户去手动下载安装最新的包&#xff0c;而是应用可以…

vue2-组件和插件的区别

1、组件是什么&#xff1f; 组件就是把图形、非图形的各种逻辑均抽象为一个统一的概念&#xff08;组件&#xff09;来实现开发的模式&#xff0c;在vue中每一个.vue文件都可以被视为一个组件。 组件的优势&#xff1a; 降低整个系统的耦合度&#xff0c;在保持接口不变的情况下…

Qt QThread的moveToThread方法使用

Qt线程简介 从 Qt4.4 版本之后&#xff0c;因为 QThread 的 run 方法创建新线程这样实现与 Qt 设计的理念不符&#xff0c;Qt 主推使用 moveToThread 方法来创建新线程。QThread 应该被看做是操作系统线程的接口或控制点&#xff0c;而不应该包含需要在新线程中运行的代码。需…

kodi 电视遥控器 不起作用 ,无法唤醒视频OSD

最近电视盒子上安装了kodi播放器&#xff0c;但是安装好之后&#xff0c;盒子本身的遥控器就不起作用了&#xff0c;之前看网络上其他的文章&#xff0c;需要重新安装tv 控制器&#xff0c;重新映射&#xff0c;比较麻烦&#xff0c;而且观看视频的时候没办法唤起OSD切换字幕和…

在美国,信用分数超过800,这是一个很好的分数吗?

超过800的信用评分被认为是极好的&#xff0c;而且这确实是可以实现的。事实上&#xff0c;美国有很多人的信用评分都在这个范围内。 信用评分是一个数字化的表示&#xff0c;反映了一个人的信用值得信赖度&#xff0c;贷款机构用它来评估这个人偿还债务的可能性。最广泛使用的…

PyCharm安装使用2023年教程,PyCharm与现流行所有编辑器对比。

与PyCharm类似的功能和特性的集成开发环境&#xff08;IDE&#xff09;和代码编辑器有以下几种&#xff1a; Visual Studio Code&#xff08;VS Code&#xff09;&#xff1a;由Microsoft开发&#xff0c;VS Code是一个高度可定制和可扩展的代码编辑器。它支持多种编程语言&am…

为什么list.sort()比Stream().sorted()更快?

真的更好吗&#xff1f; 先简单写个demo List<Integer> userList new ArrayList<>();Random rand new Random();for (int i 0; i < 10000 ; i) {userList.add(rand.nextInt(1000));}List<Integer> userList2 new ArrayList<>();userList2.add…

ORA-48913: Writing into trace file failed, file size limit [50000000] reached

检查某环境的alert_orcl1.log时&#xff0c;发现有很多的ORA-48913报错&#xff0c;细节如下 Sat Jul 22 19:34:04 2023 Non critical error ORA-48913 caught while writing to trace file "/u01/app/oracle/diag/rdbms/orcl/orcl1/trace/orcl1_dw00_138010.trc" E…

LeetCode 热题 100 JavaScript--108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums &#xff0c;其中元素已经按 升序 排列&#xff0c;请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 提示&#xff1a; 1 < nums.length < 104 -104 < n…

C#利用自定义特性以及反射,来提大型项目的开发的效率

在大型项目的开发过程中&#xff0c;需要多人协同工作&#xff0c;来加速项目完成进度。 比如一个软件有100个form&#xff0c;分给100个人来写&#xff0c;每个人完成自己的Form.cs的编写之后&#xff0c;要在Mainform调用自己写的Form。 如果按照正常的Form form1 new For…

摄像头电池组和平衡车电池组

摄像头电池组 Wh~是电量 Wh V*Ah 毫安(mA)~是电流 电量是9.62Wh&#xff0c;电压是 3.7v 9.62 wh / 3.7v 2.6 Ah 2600mAH 4个并联电池&#xff1a;10400mAH / 4 2600mAH PH2.0mm-2Pins 平衡车 72 wh / 36v 2 Ah 2000mAH 对比自己买的单粒电池 vs 摄像头和平衡车的 …

云安全攻防(四)之 云原生技术

云原生技术 容器技术 容器与虚拟化 虚拟化&#xff08;Virtualization&#xff09;和容器&#xff08;Container&#xff09;都是系统虚拟化的实现技术&#xff0c;可实现系统资源的”一虚多“共享。容器技术可以理解成一种”轻量的虚拟化“方式&#xff0c;此处的”轻量“主…

JNI之Java实现远程打印

打印机是最常见的办公设备了。一般情况下如果需要实现打印&#xff0c;可通过前端print.js包来完成。但是&#xff0c;如果要实现智能办公打印&#xff0c;就可以使用JNI技术、封装接口、远程调用实现完成。 导包 jacob&#xff1a;Java COM Bridge <dependency><g…
最新文章