当前位置: 首页 > news >正文

Leetcode 200. 岛屿数量

在这里插入图片描述

心路历程:

在没有看图论这一章之前看这道题没什么直接的思路,在看完图论之后,学着使用DFS和BFS去套用解决。第一次自己做的时候还是遇到了很多小问题。整体思路很流畅,但是需要处理的细节第一次没怎么处理好,花了很多时间去思考图中的回溯和常规组合/子集回溯问题的区别。
这道题的一个整体思路还是对grid进行遍历,然后标记所有连成一片陆地的点,下次直接跳过。

注意的点:

1、这道题很难用visited=[]然后append的方式去记录访问过的点,只能用visited[i][j]=True这种方式,否则会超时。
2、用DFS时,虽然用的还是回溯的模板,但是由于目的是记录访问过的所有点而不是路径(区域问题而非路径问题),所以不需要恢复现场。
3、用BFS时,如果在出队时记录visited会超时,需要在入队的时候记录visited才行。因为在BFS中队列的长度可能会很长,而且很容易把重复的结点入队。用DFS时,把visited的赋值放在candidate的选择那,也会加快程序的运行,这样就不用在下次收集candicate的时候收集重复的结点了。可以总结为,在visited岛屿问题中,在用到not allvisited[newx][newy]后立刻赋值True。
4、图中的四向问题用dxy = [(0,1), (0,-1), (1,0), (-1,0)]的形式会更清晰简洁。
5、无论是DFS还是BFS,本质在每次处理的都是以i, j为索引的’结点‘。
6、图中的DFS和回溯的唯一区别就是对于visited的维护模式不同,回溯需要pop,图的深搜只要遍历过就下次无论如何也不用考虑了,毕竟搜索的是区域而不是路径。(遍历过的多叉树的路径就保存下来)

解法一:DFS+遍历grid

class Solution:def numIslands(self, grid: List[List[str]]) -> int:# DFS + 循环遍历;回溯求区域而不是路径,因此不需要在回溯函数调用后恢复现场m, n = len(grid), len(grid[0])dxy = [(0,1), (0,-1), (1,0), (-1,0)]def dfs(i,j):  # 对i,j区域进行搜索,将联通i,j的陆地全部记录起来。# 获取可选集合candicate = []for dx, dy in dxy:newx, newy = i+dx, j+dyif 0 <= newx <= m-1 and 0 <= newy <= n-1 and grid[newx][newy] == '1' and not allvisited[newx][newy]:candicate.append([newx, newy])allvisited[newx][newy] = True  # 在用到not allvisited[newx][newy]后立刻赋值if not candicate:returnfor each in candicate:dfs(each[0], each[1])# visited.pop()  # 不用恢复了,因为不是要求路径的总和,而是记录遍历过的路径(路径就是一个grid)allvisited = [[False]*n for _ in range(m)]  # 用allvisited += visited的那种做法会超时num = 0for xi in range(m):for yi in range(n):if not allvisited[xi][yi] and grid[xi][yi] == '1':dfs(xi,yi)num += 1return num

解法二:BFS+遍历grid

class Solution:def numIslands(self, grid: List[List[str]]) -> int:# BFS; 没有必要找到每个岛屿的陆地区域,只需要将遍历过的标记上即可;基本图和回溯的任何问题都得记录visited,至少要考虑上一步重复from collections import dequem, n = len(grid), len(grid[0])dxy = [(0,1), (0,-1), (1,0), (-1,0)]visited = [[False]*n for _ in range(m)]num = 0quelen = []for i in range(m):for j in range(n):# 对每个i,j做bfs并标记上搜索过的区域if grid[i][j] == '1' and not visited[i][j]:  # 1 和 '1'num += 1que = deque([[i,j]])visited[i][j] = Truewhile que:  # 不需要记录层数quelen.append(len(que))x, y = que.popleft()# visited[x][y] = True  # 出队放会超时for dx, dy in dxy:newx, newy = x+dx, y+dyif 0 <= newx <= m-1 and 0 <= newy <= n-1 and not visited[newx][newy] and grid[newx][newy] == '1':que.append([newx, newy])visited[newx][newy] = True  # 只可以在进队的时候设置visited,出队的时候会超时!return num

相关文章:

Leetcode 200. 岛屿数量

心路历程&#xff1a; 在没有看图论这一章之前看这道题没什么直接的思路&#xff0c;在看完图论之后&#xff0c;学着使用DFS和BFS去套用解决。第一次自己做的时候还是遇到了很多小问题。整体思路很流畅&#xff0c;但是需要处理的细节第一次没怎么处理好&#xff0c;花了很多…...

多线程基础 -概念、创建、等待、分离、终止

文章目录 一、 线程概念1. 什么是线程2. 线程的优点3.线程的缺点4. 线程异常5. 线程用途 二、 Linux进程VS线程1. 进程和线程2. 进程和线程的地址空间3. 进程和线程的关系 三、Linux线程控制1. POSIX线程库2. 线程创建3. 线程ID及进程地址空间布局4. 线程终止5. 线程等待6. 线程…...

【Vue3】走进Pinia,学习Pinia,使用Pinia

&#x1f497;&#x1f497;&#x1f497;欢迎来到我的博客&#xff0c;你将找到有关如何使用技术解决问题的文章&#xff0c;也会找到某个技术的学习路线。无论你是何种职业&#xff0c;我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章&#xff0c;也欢…...

【TB作品】430单片机,单片机串口多功能通信,Proteus仿真

文章目录 题目功能仿真图程序介绍代码、仿真、原理图、PCB 题目 60、单片机串口多功能通信 基本要求: 设计一串口通信程序,波特率38400,通过RS232与PC机通信。 自动循环发送数据串(设计在程序中) 接收并存储和显示该数据串 在发送端定义10个ASCII码键0-9 按键发送单字节,PC机接…...

【C++ leetcode】双指针问题

1. 611. 有效三角形的个数 题目 给定一个包含非负整数的数组 nums &#xff0c;返回其中可以组成三角形三条边的三元组个数。 题目链接 . - 力扣&#xff08;LeetCode&#xff09; 画图 和 文字 分析 判断是否是三角形要得到三边&#xff0c;由于遍历三边要套三层循环&#x…...

Kubernetes集群部署

1.集群环境搭建 1.1 环境规划 kubernetes集群大体上分为两类&#xff1a;一主多从和多主多从。 一主多从&#xff1a;一台Master节点和多台Node节点&#xff0c;搭建简单&#xff0c;但是有单机故障风险&#xff0c;适合用于测试环境多主多从&#xff1a;多台Master节点和多…...

深拷贝与浅拷贝

深拷贝与浅拷贝是在进行对象复制时常见的两种方式&#xff0c;这两个概念其实比较混淆&#xff0c;面试中也经常出现&#xff0c;但是实际开发很少用到&#xff0c;所以本文就来详细讲解一下&#xff0c;让大家不再迷惑。 浅拷贝只是复制了对象的引用&#xff08;地址&#xf…...

golang学习网址

.1LearnKu 终身编程者的知识社区 https://learnku.com/...

2024学习鸿蒙开发,未来发展如何?

一、前言 想要了解一个领域的未来发展如何&#xff0c;可以从如下几点进行&#xff0c;避免盲从&#xff1a; 国家政策落地情况就业市场如何学习 通过上述三点&#xff0c;就能分析出一个行业的趋势。大家可以看到&#xff0c;我上面的总体逻辑就是根据国家政策来分析未来方…...

3.21Code

基于二叉链表的二叉树最大宽度的计算 #include<iostream>#define MAXSIZE 1000using namespace std;int k0; int m0; //记录层数 typedef struct BiNode{char data;struct BiNode *lchild;struct BiNode *rchild; }BiNode,*BiTree;void CreateBiTree(BiTree &T){cha…...

学习总结2

解题思路 用bfs进行搜索,标记A罐B罐所保存的水的出现情况,当再次出现的时候停止搜索,然后用数组模拟链表进行保存路径.最后输出. 代码 #include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #in…...

【LeetCode】--- 动态规划 集训(一)

目录 一、1137. 第 N 个泰波那契数1.1 题目解析1.2 状态转移方程1.3 解题代码 二、面试题 08.01. 三步问题2.1 题目解析2.2 状态转移方程2.3 解题代码 三、746. 使用最小花费爬楼梯3.1 题目解析3.2 状态转移方程3.3 解题代码 一、1137. 第 N 个泰波那契数 题目地址&#xff1a…...

【数据结构与算法】(18):树形选择排序:按照锦标赛的思想进行排序

&#x1f921;博客主页&#xff1a;Code_文晓 &#x1f970;本文专栏&#xff1a;数据结构与算法 &#x1f63b;欢迎关注&#xff1a;感谢大家的点赞评论关注&#xff0c;祝您学有所成&#xff01; ✨✨&#x1f49c;&#x1f49b;想要学习更多数据结构与算法点击专栏链接查看&…...

统计单词数

统计单词数 题目描述 一般的文本编辑器都有查找单词的功能&#xff0c;该功能可以快速定位特定单词在文章中的位置&#xff0c;有的还能统计出特定单词在文章中出现的次数。 现在&#xff0c;请你编程实现这一功能&#xff0c;具体要求是&#xff1a;给定一个单词&#xff0…...

c++pair的用法

pair简单来说就是可以存储两种类型数据的一个类&#xff0c;其内部是使用模板实现的&#xff0c;所以可以指定其内部的类型。 pair在#include <utility> pair的构造 pair<int, string> p1({ 1,"张三" });pair<int, string> p2;pair<int, str…...

石油炼化5G智能制造工厂数字孪生可视化平台,推进行业数字化转型

石油炼化5G智能制造工厂数字孪生可视化平台&#xff0c;推进行业数字化转型。在石油炼化行业&#xff0c;5G智能制造工厂数字孪生可视化平台的出现&#xff0c;为行业的数字化转型注入了新的活力。石油炼化行业作为传统工业的重要领域&#xff0c;面临着资源紧张、环境压力、安…...

IP代理技术革新:探索数据采集的新路径

引言&#xff1a; 随着全球化进程不断加深&#xff0c;网络数据采集在企业决策和市场分析中扮演着愈发重要的角色。然而&#xff0c;地域限制和IP封锁等问题常常给数据采集工作带来了巨大挑战。亿牛云代理服务凭借其强大的网络覆盖和真实住宅IP资源&#xff0c;成为解决这些问…...

流畅的 Python 第二版(GPT 重译)(一)

前言 计划是这样的&#xff1a;当有人使用你不理解的特性时&#xff0c;直接开枪打死他们。这比学习新东西要容易得多&#xff0c;不久之后&#xff0c;活下来的程序员只会用一个容易理解的、微小的 Python 0.9.6 子集来编写代码 。 Tim Peters&#xff0c;传奇的核心开发者&am…...

Vue+jquery+jquery.maphilight实现图片热区高亮以及点击效果

//鼠标悬浮效果 mounted() {this.setCurrentTask(0); //对于id为mapAll的热区图&#xff0c;设置鼠标放置在上面有一个颜色 fillColor填充颜色 strokeColor边框颜色 strokeWidth边框宽度 fillOpacity 是设置热区填充颜色的不透明度的属性。 alwaysOn:true 保持常量$(function(…...

靠谱!朋友圈一键转发和自动转发好友朋友圈

微信朋友圈在生活和工作中扮演着重要的社交和信息传播角色。尤其是对于一些企业来说&#xff0c;朋友圈是不可或缺的推广渠道。 今天就给大家分享一个能够实现一键转发和自动转发好友朋友圈的工具——微信管理系统&#xff0c;让大家都能有效的管理朋友圈。 1、定时发圈&…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...