Python算法题集_岛屿数量

 Python算法题集_岛屿数量

  • 题200：岛屿数量
  • 1. 示例说明
  • 2. 题目解析
    • - 题意分解
    • - 优化思路
    • - 测量工具
  • 3. 代码展开
    • 1) 标准求解【双层循环+递归】
    • 2) 改进版一【双层循环+迭代】
    • 3) 改进版二【双层循环+迭代+高速双向队列】
    • 4) 改进版三【双层循环+并查集】
  • 4. 最优算法
  • 5. 相关资源

本文为Python算法题集之一的代码示例

题200：岛屿数量

1. 示例说明

  • 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

    岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

    此外，你可以假设该网格的四条边均被水包围。

    示例 1：

    输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

    示例 2：

    输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

    提示：

    • m == grid.length
    • n == grid[i].length
    • 1 <= m, n <= 300
    • grid[i][j] 的值为 '0' 或 '1'

2. 题目解析

- 题意分解

  1. 本题是在图中计算岛屿数量，“1”为陆地，"0"为水面
  2. 本题必须通过陆地着手计算，因为即使只有一块水域，也可以有多块陆地
  3. 基本的设计思路是双层循环，自上而下，从左到右，遍历网格；每发现一块陆地，就将相连的陆地全部找出来标记为已检查

- 优化思路

  1. 通常优化：减少循环层次

  2. 通常优化：增加分支，减少计算集

  3. 通常优化：采用内置算法来提升计算速度

  4. 分析题目特点，分析最优解

    1. 可以采用递归法进行相连陆地的遍历

    2. 可以采用迭代法进行相连陆地的遍历，迭代法的队列如果使用pop(0)，则可以考虑使用高速双向队列deque来优化

    3. 可以采用并查集法，将一块岛屿的所有陆地合并到1个类别中，最后检查有多少种类别

- 测量工具

  • 本地化测试说明：LeetCode网站测试运行时数据波动很大【可把页面视为功能测试】，因此需要本地化测试解决数据波动问题
  • CheckFuncPerf（本地化函数用时和内存占用测试模块）已上传到CSDN，地址：Python算法题集_检测函数用时和内存占用的模块
  • 本题本地化超时测试用例自己生成，详见【最优算法章节】

3. 代码展开

1) 标准求解【双层循环+递归】

双层循环，使用递归法遍历相连陆地

页面功能测试，马马虎虎，超过67%在这里插入图片描述

import CheckFuncPerf as cfp

class Solution:
 def numIslands_base(self, grid):
     directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
     def dfs(grid, irow, icol):
         if not 0 <= irow < len(grid) or not 0 <= icol < len(grid[0]):
             return 0
         if grid[irow][icol]!= "1":
             return 0
         grid[irow][icol]= "2"
         for delta in directions:
             dfs(grid, irow+delta[0], icol+delta[1])
         return 1
     landnum=0
     for iIdx in range(len(grid)):
         for jIdx in range(len(grid[0])):
             if grid[iIdx][jIdx]=="1":
                 landnum+=dfs(grid,iIdx,jIdx) 
     return landnum

aSolution = Solution()
list_world = copy.deepcopy(list_originworld)
result = cfp.getTimeMemoryStr(Solution.numIslands_base, aSolution, list_world)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 运行结果
函数 numIslands_base 的运行时间为 604.38 ms；内存使用量为 168.00 KB 执行结果 = 66293

2) 改进版一【双层循环+迭代】

双层循环，使用迭代法遍历相连陆地

页面功能测试，性能良好，超过84%在这里插入图片描述

import CheckFuncPerf as cfp

class Solution:
 def numIslands_ext1(self, grid):
     queue = []
     directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
     imaxrow = len(grid)
     imaxcol = len(grid[0])
     bvisited = [[False] * imaxcol for x in range(imaxrow)]
     landnum = 0  
     for iIdx in range(imaxrow):
         for jIdx in range(imaxcol):
             if bvisited[iIdx][jIdx] or grid[iIdx][jIdx] == '0':
                 continue 
             bvisited[iIdx][jIdx] = True
             queue.append([iIdx, jIdx])
             while queue:
                 irow, icol = queue[0][0], queue[0][1]
                 queue.pop(0)
                 for delta in directions:
                     inextrow, inextcol = irow + delta[0], icol + delta[1]
                     if inextrow < 0 or inextrow >= imaxrow or inextcol < 0 \
                             or inextcol >= imaxcol or bvisited[inextrow][inextcol] \
                             or grid[inextrow][inextcol] == '0':
                         continue  
                     queue.append([inextrow, inextcol])
                     bvisited[inextrow][inextcol] = True  
             landnum += 1            
     return landnum

aSolution = Solution()
list_world = copy.deepcopy(list_originworld)
result = cfp.getTimeMemoryStr(Solution.numIslands_ext1, aSolution, list_world)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 运行结果
函数 numIslands_ext1 的运行时间为 508.67 ms；内存使用量为 840.00 KB 执行结果 = 66293

3) 改进版二【双层循环+迭代+高速双向队列】

双层循环，使用迭代法遍历相连陆地，并使用高速双向队列deque来优化list的pop(0)性能

页面功能测试，性能优越，超越92%在这里插入图片描述

import CheckFuncPerf as cfp

class Solution:
 def numIslands_ext2(self, grid):
     from collections import deque
     queue = deque([])
     directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
     imaxrow = len(grid)
     imaxcol = len(grid[0])
     bvisited = [[False] * imaxcol for x in range(imaxrow)]
     landnum = 0    
     for iIdx in range(imaxrow):
         for jIdx in range(imaxcol):
             if bvisited[iIdx][jIdx] or grid[iIdx][jIdx] == '0':
                 continue  
             bvisited[iIdx][jIdx] = True
             queue.append([iIdx, jIdx])
             while queue:
                 irow, icol = queue[0][0], queue[0][1]
                 queue.popleft()
                 for delta in directions:
                     inextrow, inextcol = irow + delta[0], icol + delta[1]
                     if inextrow < 0 or inextrow >= imaxrow or inextcol < 0 \
                             or inextcol >= imaxcol or bvisited[inextrow][inextcol] \
                             or grid[inextrow][inextcol] == '0':
                         continue   
                     queue.append([inextrow, inextcol])
                     bvisited[inextrow][inextcol] = True  
             landnum += 1             
     return landnum

aSolution = Solution()
list_world = copy.deepcopy(list_originworld)
result = cfp.getTimeMemoryStr(Solution.numIslands_ext2, aSolution, list_world)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 运行结果
函数 numIslands_ext2 的运行时间为 473.73 ms；内存使用量为 24.00 KB 执行结果 = 66293

4) 改进版三【双层循环+并查集】

双层循环，使用并查集【通过字典实现find、union】合并陆地，最后检查类别数

页面功能测试，惨不忍睹，超过33%在这里插入图片描述

import CheckFuncPerf as cfp

class Solution:
 def numIslands_ext3(self, grid):
     dict_type = {}  
     def find(x):
         dict_type.setdefault(x, x)
         if dict_type[x] != x: 
             dict_type[x] = find(dict_type[x])
         return dict_type[x]
     def union(x, y):
         dict_type[find(x)] = find(y)
     if not grid:
         return 0
     imaxrow = len(grid)
     imaxcol = len(grid[0])
     directions = [[-1, 0], [0, -1]]
     for iIdx in range(imaxrow):
         for jIdx in range(imaxcol):
             if grid[iIdx][jIdx] == "1": 
                 for delta in directions: 
                     tmprow_i = iIdx + delta[0]
                     tmpcol_j = jIdx + delta[1]
                     if 0 <= tmprow_i < imaxrow and 0 <= tmpcol_j < imaxcol and grid[tmprow_i][tmpcol_j] == "1": 
                         union(tmprow_i * imaxrow + tmpcol_j, iIdx * imaxrow + jIdx) 
     lands = set()
     for iIdx in range(imaxrow): 
         for jIdx in range(imaxcol):
             if grid[iIdx][jIdx] == "1":
                 tmpType = find(iIdx * imaxrow + jIdx)
                 if tmpType in lands: continue
                 lands.add(tmpType) 
     return len(lands) 

aSolution = Solution()
list_world = copy.deepcopy(list_originworld)
result = cfp.getTimeMemoryStr(Solution.numIslands_ext3, aSolution, list_world)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 运行结果
函数 numIslands_ext2 的运行时间为 473.73 ms；内存使用量为 24.00 KB 执行结果 = 66293

4. 最优算法

根据本地日志分析，最优算法为第3种方式【双层循环+迭代+高速双向队列】numIslands_ext2

import random, copy
imaxrow, imaxcol = 1000, 1000
list_originworld = [[str(random.randint(0, 1)) for y in range(imaxcol)] for x in range(imaxrow)]
aSolution = Solution()
list_world = copy.deepcopy(list_originworld)
result = cfp.getTimeMemoryStr(Solution.numIslands_base, aSolution, list_world)
print(result['msg'], '执行结果 = {}'.format(result['result']))
list_world = copy.deepcopy(list_originworld)
result = cfp.getTimeMemoryStr(Solution.numIslands_ext1, aSolution, list_world)
print(result['msg'], '执行结果 = {}'.format(result['result']))
list_world = copy.deepcopy(list_originworld)
result = cfp.getTimeMemoryStr(Solution.numIslands_ext2, aSolution, list_world)
print(result['msg'], '执行结果 = {}'.format(result['result']))
list_world = copy.deepcopy(list_originworld)
result = cfp.getTimeMemoryStr(Solution.numIslands_ext3, aSolution, list_world)
print(result['msg'], '执行结果 = {}'.format(result['result']))

# 算法本地速度实测比较
函数 numIslands_base 的运行时间为 604.38 ms；内存使用量为 168.00 KB 执行结果 = 66293
函数 numIslands_ext1 的运行时间为 508.67 ms；内存使用量为 840.00 KB 执行结果 = 66293
函数 numIslands_ext2 的运行时间为 473.73 ms；内存使用量为 24.00 KB 执行结果 = 66293
函数 numIslands_ext3 的运行时间为 919.58 ms；内存使用量为 36804.00 KB 执行结果 = 66293

5. 相关资源

本文代码已上传到CSDN，地址：Python算法题集_LeetCode(力扣)_岛屿数量_源代码

一日练，一日功，一日不练十日空

may the odds be ever in your favor ~

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

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

相关文章

五、分类算法 总结

五、分类算法 总结

代码&#xff1a; from sklearn.datasets import load_iris, fetch_20newsgroups from sklearn.feature_extraction.text import TfidfVectorizer from sklearn.model_selection import train_test_split, GridSearchCV from sklearn.naive_bayes import MultinomialNB from s…
阅读更多...
基于JAVA的班级考勤管理系统 开源项目

基于JAVA的班级考勤管理系统 开源项目

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 系统基础支持模块2.2 班级学生教师支持模块2.3 考勤签到管理2.4 学生请假管理 三、系统设计3.1 功能设计3.1.1 系统基础支持模块3.1.2 班级学生教师档案模块3.1.3 考勤签到管理模块3.1.4 学生请假管理模块 3.2 数据库设…
阅读更多...
Kubernetes二进制搭建

Kubernetes二进制搭建

目录 1.操作系统初始化配置&#xff08;所有节点同此操作&#xff09; 2.部署etcd集群 etcd概述 准备签发证书环境 在master01节点上操作&#xff08;192.168.88.22&#xff09; 在两个node节点上操作 总结&#xff1a; 3.部署docker引擎 4.部署Master组件 总结&…
阅读更多...
学习大数据所需的java基础(5)

学习大数据所需的java基础(5)

文章目录 集合框架Collection接口迭代器迭代器基本使用迭代器底层原理并发修改异常 数据结构栈队列数组链表 List接口底层源码分析 LinkList集合LinkedList底层成员解释说明LinkedList中get方法的源码分析LinkedList中add方法的源码分析 增强for增强for的介绍以及基本使用发2.使…
阅读更多...
五种多目标优化算法（MOJS、MOGWO、NSWOA、MOPSO、NSGA2）性能对比（提供MATLAB代码）

五种多目标优化算法（MOJS、MOGWO、NSWOA、MOPSO、NSGA2）性能对比（提供MATLAB代码）

一、5种多目标优化算法简介 1.1MOJS 1.2MOGWO 1.3NSWOA 1.4MOPSO 1.5NSGA2 二、5种多目标优化算法性能对比 为了测试5种算法的性能将其求解9个多目标测试函数&#xff08;zdt1、zdt2 、zdt3、 zdt4、 zdt6 、Schaffer、 Kursawe 、Viennet2、 Viennet3&#xff09;&#xff0…
阅读更多...
【虚拟仿真】Unity3D中实现3DUI，并且实现Button、InputField、Toggle等事件绑定

【虚拟仿真】Unity3D中实现3DUI，并且实现Button、InputField、Toggle等事件绑定

推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址大家好，我是佛系工程师☆恬静的小魔龙☆，不定时更新Unity开发技巧，觉得有用记得一键三连哦。 一、前言 最近在项目中需要用到3DUI的展示，之前一般会用TextMeshPro进行展示： 但是，后面又需要添加按钮、Toggle等…
阅读更多...
《nvm 安装》nodejs 版本管理工具

《nvm 安装》nodejs 版本管理工具

一.前言 如果先于 nvm 安装了 node&#xff0c;一定要先卸载&#xff01; 两种卸载方式&#xff1a; 方式一 控制面板 -> 程序和功能 -> nodejs 删除 方式二 下载的 node 安装包有卸载选项 二. 安装 nvm 下载地址 中找到对应的安装包&#xff0c;我本机使用 window…
阅读更多...
Autosar-Mcal配置详解-GPT

Autosar-Mcal配置详解-GPT

3.3.1添加GPT模块 方法与添加Dio相似&#xff0c;可参加Dio模块添加方法。 3.3.2 创建、配置GPT通道 1)根据需求创建GPT通道&#xff08;即创建几个定时器&#xff09; 本例中创建了3个定时器通道&#xff1a;1ms&#xff0c;100us&#xff0c;OsTimer。 2)配置GPT通道 配置T…
阅读更多...
进度条小程序

进度条小程序

文章目录 铺垫回车换行缓冲区概述强制冲刷缓冲区 简单实现倒计时功能进度条小程序版本一实例代码效果展示分析 版本二 铺垫 回车换行 回车和换行是两个独立的动作 回车是将光标移动到当前行的最开始&#xff08;最左侧&#xff09; 换行是竖直向下平移一行 在C语言中&…
阅读更多...
图的遍历-----深度优先遍历（dfs）,广度优先遍历（bfs）【java详解】

图的遍历-----深度优先遍历（dfs）,广度优先遍历（bfs）【java详解】

目录 简单介绍&#xff1a;什么是深度、广度优先遍历&#xff1f; 深度优先搜索&#xff08;DFS&#xff0c;Depth First Search&#xff09;&#xff1a; 大致图解&#xff1a; 广度优先搜索&#xff08;BFS&#xff0c;Breadth First Search&#xff09;&#xff1a; 大致图…
阅读更多...
数据结构·顺序表

数据结构·顺序表

1数据结构简介 学习数据结构与算法之前&#xff0c;一般是先学数据结构&#xff0c;方便之后学习算法&#xff0c;那么数据结构拆开介绍&#xff0c;就是数据 和 结构&#xff0c;数据&#xff0c;生活中到处都是&#xff0c;结构&#xff0c;就是数据存储的方式&#xff0c;即…
阅读更多...
分布式系统一致性与共识算法

分布式系统一致性与共识算法

分布式系统的一致性是指从系统外部读取系统内部的数据时&#xff0c;在一定约束条件下相同&#xff0c;即数据&#xff08;元数据&#xff0c;日志数据等等&#xff09;变动在系统内部各节点应该是一致的。 一致性模型分为如下几种&#xff1a; ① 强一致性 所有用户在任意时…
阅读更多...
git使用过的命令记录

git使用过的命令记录

目录 git add .git commit --amendgit push -f origin HEAD:mastergit checkout .git stash想把某个pr的修改应用到本地git pull 将远程仓库的最新代码更新到本地git 撤销&#xff0c;放弃本地修改参考文档 git add . 将本地修改提交到暂存区 git commit --amend 如果本地有…
阅读更多...
MySQL 8.0.36 WorkBench安装

MySQL 8.0.36 WorkBench安装

一、下载安装包 百度网盘链接&#xff1a;点击此处下载安装文件 提取码&#xff1a;hhwz 二、安装&#xff0c;跟着图片来 选择Custom,然后点Next 顺着左边框每一项的加号打开到每一个项的最底层&#xff0c;点击选中最底层的项目&#xff0c;再点击传过去右边的绿色箭头&a…
阅读更多...
MATLAB 导出可编辑的eps格式图像

MATLAB 导出可编辑的eps格式图像

任务描述&#xff1a;部分期刊要求提交可编辑的eps格式图像&#xff0c;方便美工编辑对图像进行美化 我试了直接print或者在figure窗口导出&#xff0c;发现导出的文件放到Adobe AI中并不能编辑&#xff0c;经Google找到解决办法&#xff1a; %EPS exportgraphics(gcf,myVect…
阅读更多...
FFmpeg的HEVC解码器源代码学习笔记-1

FFmpeg的HEVC解码器源代码学习笔记-1

一直想写一个HEVC的码流解析工具&#xff0c;看了雷神264码流解析工具&#xff0c;本来想尝试模仿写一个相似的265码流分析工具&#xff0c;但是发现265的解码过程和结构体和264的不太一样&#xff0c;很多结构体并没有完全暴露出来&#xff0c;没有想到很好的方法获得量化参数…
阅读更多...
[晓理紫]AI专属会议截稿时间订阅

[晓理紫]AI专属会议截稿时间订阅

AI专属会议截稿时间订阅 VX关注{晓理紫}免费，每日更新最新AI专属会议信息，如感兴趣，请转发给有需要的同学，谢谢支持！！ VX关注{晓理紫}免费 IROS 2024 Deadline: Sat Mar 2nd 2024 03:59:59 PM CST (2024-03-02 15:59:59 UTC-08) date_location: October 14-18, 2024. A…
阅读更多...
鸿蒙会成为安卓的终结者吗？

鸿蒙会成为安卓的终结者吗？

随着近期鸿蒙OS系统推送测试版的时间确定&#xff0c;关于鸿蒙系统的讨论再次升温。 作为华为自主研发的操作系统&#xff0c;鸿蒙给人的第一印象是具有颠覆性。 早在几年前&#xff0c;业内就开始流传鸿蒙可能会代替Android的传言。毕竟&#xff0c;Android作为开源系统&…
阅读更多...
第10讲用户登录SpringSecurity查库实现

第10讲用户登录SpringSecurity查库实现

用户登录SpringSecurity查库实现 security包下新建MyUserDetailServiceImpl Service public class MyUserDetailServiceImpl implements UserDetailsService {AutowiredSysUserService sysUserService;Overridepublic UserDetails loadUserByUsername(String username) throw…
阅读更多...
C#算法（12）—对图像像素做X/Y方向的偏移

C#算法（12）—对图像像素做X/Y方向的偏移

我们在上位机开发领域有时候需要对获取的图像的像素做整体的偏移，比如所有像素在X方向上偏移几个像素，或者所有像素在Y方向上偏移几个像素，本文就是开发了像素整体偏移算法来解决这个问题。 比如有一个图像大小为3*3，像素值如下图1，如果我想实现将这个幅图像的像素整体往右…
阅读更多...
最新文章

Copyright @ 2022~2023