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

代码随想录算法训练营Day 63| 图论 part03 | 417.太平洋大西洋水流问题、827.最大人工岛、127. 单词接龙

代码随想录算法训练营Day 63| 图论 part03 | 417.太平洋大西洋水流问题、827.最大人工岛、127. 单词接龙


文章目录

  • 代码随想录算法训练营Day 63| 图论 part03 | 417.太平洋大西洋水流问题、827.最大人工岛、127. 单词接龙
  • 17.太平洋大西洋水流问题
    • 一、DFS
    • 二、BFS
    • 三、本题总结
  • 827.最大人工岛
    • 一、DFS 用全局变量得到area
    • 二、DFS 用局部变量
    • 三、BFS
  • 127. 单词接龙
    • 一、BFS


17.太平洋大西洋水流问题

题目链接

一、DFS

class Solution(object):def pacificAtlantic(self, heights):""":type heights: List[List[int]]:rtype: List[List[int]]"""m,n=len(heights),len(heights[0])dirs = [(-1,0),(0,1),(1,0),(0,-1)]pacific=[[0]*n for _ in range(m)]atlantic=[[0]*n for _ in range(m)]result=[] # DFSdef dfs(x,y,ocean):ocean[x][y]=1for d in dirs:nextx,nexty=x+d[0],y+d[1]if 0 <= nextx < m and 0 <= nexty < n  and heights[nextx][nexty] >=heights[x][y] and ocean[nextx][nexty]==0:dfs(nextx,nexty,ocean)for i in range(m):dfs(i,0,pacific)dfs(i,n-1,atlantic)for j in range(n):dfs(0,j,pacific)dfs(m-1,j,atlantic)for i in range(m):for j in range(n):if pacific[i][j]==1 and atlantic[i][j]==1:result.append([i,j])return result

二、BFS

class Solution(object):def pacificAtlantic(self, heights):""":type heights: List[List[int]]:rtype: List[List[int]]"""m,n=len(heights),len(heights[0])dirs = [(-1,0),(0,1),(1,0),(0,-1)]pacific=[[0]*n for _ in range(m)]atlantic=[[0]*n for _ in range(m)]result=[] # BFSdef bfs(x,y,ocean):q=collections.deque()q.append((x,y))ocean[x][y]=1while q:x,y = q.popleft()for d in dirs:nextx,nexty=x+d[0],y+d[1]if 0 <= nextx < m and 0 <= nexty < n  and heights[nextx][nexty] >=heights[x][y] and ocean[nextx][nexty]==0:ocean[nextx][nexty]=1q.append((nextx,nexty))for i in range(m):bfs(i,0,pacific)bfs(i,n-1,atlantic)for j in range(n):bfs(0,j,pacific)bfs(m-1,j,atlantic)for i in range(m):for j in range(n):if pacific[i][j]==1 and atlantic[i][j]==1:result.append([i,j])return result

三、本题总结

用两个visited来表示


827.最大人工岛

题目链接

一、DFS 用全局变量得到area

class Solution(object):def largestIsland(self, grid):""":type grid: List[List[int]]:rtype: int"""'''总体思路利用 DFS 计算出各个岛屿的面积,并标记每个 1(陆地格子)属于哪个岛。遍历每个 0,统计其上下左右四个相邻格子所属岛屿的编号,去重后,累加这些岛的面积,更新答案的最大值。'''m,n = len(grid),len(grid[0])dirs = [(-1,0),(0,1),(1,0),(0,-1)]area = collections.defaultdict(int) # 用于储存岛屿面积def dfs(x,y,island_num): # 输入岛屿编号grid[x][y]=island_num area[island_num] += 1 # 更新岛屿面积for d in dirs:nextx,nexty=x+d[0],y+d[1]if 0 <= nextx < m and 0 <= nexty < n  and grid[nextx][nexty]==1:grid[nextx][nexty]=island_numdfs(nextx,nexty,island_num)island_num = 1 for i in range(m):for j in range(n):if grid[i][j]==1: # 遇到新岛屿island_num += 1 # 岛屿编号从2开始dfs(i,j,island_num) ans=0for i in range(m):for j in range(n):s=set() # 去重if grid[i][j]==0:for d in dirs:nexti,nextj=i+d[0],j+d[1]if 0 <= nexti < m and 0 <= nextj < n  and grid[nexti][nextj]!=0:s.add(grid[nexti][nextj])ans = max(ans,1+sum(area[idx] for idx in s))return ans if ans else n*n # 如果最后 ans 仍然为 0,说明所有格子都是 1,返回 n^2

二、DFS 用局部变量

class Solution(object):def largestIsland(self, grid):""":type grid: List[List[int]]:rtype: int"""'''总体思路
利用 DFS 计算出各个岛屿的面积,并标记每个 1(陆地格子)属于哪个岛。
遍历每个 0,统计其上下左右四个相邻格子所属岛屿的编号,去重后,累加这些岛的面积,更新答案的最大值。'''m,n = len(grid),len(grid[0])dirs = [(-1,0),(0,1),(1,0),(0,-1)]area = collections.defaultdict(int) # 用于储存岛屿面积def dfs(x,y,island_num): # 输入岛屿编号grid[x][y]=island_num size=1# area[island_num] += 1 # 更新岛屿面积for d in dirs:nextx,nexty=x+d[0],y+d[1]if 0 <= nextx < m and 0 <= nexty < n  and grid[nextx][nexty]==1:grid[nextx][nexty]=island_numsize += dfs(nextx,nexty,island_num)return size # 得到岛屿的面积island_num = 1 for i in range(m):for j in range(n):if grid[i][j]==1: # 遇到新岛屿island_num += 1 # 岛屿编号从2开始area[island_num]=dfs(i,j,island_num) ans=0for i in range(m):for j in range(n):s=set() # 去重if grid[i][j]==0:for d in dirs:nexti,nextj=i+d[0],j+d[1]if 0 <= nexti < m and 0 <= nextj < n  and grid[nexti][nextj]!=0:s.add(grid[nexti][nextj])ans = max(ans,1+sum(area[idx] for idx in s))return ans if ans else n*n # 如果最后 ans 仍然为 0,说明所有格子都是 1,返回 n^2

三、BFS

class Solution(object):def largestIsland(self, grid):""":type grid: List[List[int]]:rtype: int"""'''总体思路
利用 DFS 计算出各个岛屿的面积,并标记每个 1(陆地格子)属于哪个岛。
遍历每个 0,统计其上下左右四个相邻格子所属岛屿的编号,去重后,累加这些岛的面积,更新答案的最大值。'''# BFSdef bfs(x,y,island_num): # 输入岛屿编号grid[x][y]=island_num size=1# area[island_num] += 1 # 更新岛屿面积q=collections.deque()q.append((x,y))while q:x,y=q.popleft()for d in dirs:nextx,nexty=x+d[0],y+d[1]if 0 <= nextx < m and 0 <= nexty < n  and grid[nextx][nexty]==1:grid[nextx][nexty]=island_numq.append((nextx,nexty))size += 1return sizeisland_num = 1 for i in range(m):for j in range(n):if grid[i][j]==1: # 遇到新岛屿island_num += 1 # 岛屿编号从2开始# dfs(i,j,island_num) # 法1area[island_num]=bfs(i,j,island_num) ans=0for i in range(m):for j in range(n):s=set() # 去重if grid[i][j]==0:for d in dirs:nexti,nextj=i+d[0],j+d[1]if 0 <= nexti < m and 0 <= nextj < n  and grid[nexti][nextj]!=0:s.add(grid[nexti][nextj])ans = max(ans,1+sum(area[idx] for idx in s))return ans if ans else n*n # 如果最后 ans 仍然为 0,说明所有格子都是 1,返回 n^2

127. 单词接龙

题目链接

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

一、BFS

class Solution(object):def ladderLength(self, beginWord, endWord, wordList):""":type beginWord: str:type endWord: str:type wordList: List[str]:rtype: int"""wordset = set(wordList)if len(wordList)==0 or endWord not in wordset :return 0q = collections.deque()q.append(beginWord)visited=set(beginWord)step=1while q:level = len(q)for l in range(level):word = q.popleft()word_list = list(word)for i in range(len(word_list)):origin_char=word_list[i]for j in range(26):word_list[i] = chr(ord('a')+j)new_word = ''.join(word_list)if new_word in wordset:if new_word == endWord:return step+1if new_word not in visited:q.append(new_word)visited.add(new_word)word_list[i]=origin_charstep +=1return 0  

相关文章:

代码随想录算法训练营Day 63| 图论 part03 | 417.太平洋大西洋水流问题、827.最大人工岛、127. 单词接龙

代码随想录算法训练营Day 63| 图论 part03 | 417.太平洋大西洋水流问题、827.最大人工岛、127. 单词接龙 文章目录 代码随想录算法训练营Day 63| 图论 part03 | 417.太平洋大西洋水流问题、827.最大人工岛、127. 单词接龙17.太平洋大西洋水流问题一、DFS二、BFS三、本题总结 82…...

【全网最全】CSDN博客的文字颜色、字体和字号设置

文章目录 一、字体颜色二、字体大小三、字体类型四、字体背景色 在这篇博客中&#xff0c;我们将深入探讨如何在Markdown编辑器中设置文字颜色、大小、字体与背景色。Markdown本身并不直接支持这些功能&#xff0c;但通过结合HTML标签和CSS样式&#xff0c;我们可以实现这些视觉…...

C#实现数据采集系统-Mqtt实现采集数据转发

在数据采集系统中,通过ModbusTcp采集到数据之后,再通过MQTT转发到其他应用 MQTT操作 安装MQTT mqtt介绍和环境安装 使用MQTT 在C#/Net中使用Mqtt MQTT类封装 MQTT配置类 public class MqttConfig{public string Ip {get; set;...

common-intellisense:助力TinyVue 组件书写体验更丝滑

本文由体验技术团队Kagol原创~ 前两天&#xff0c;common-intellisense 开源项目的作者 Simon-He95 在 VueConf 2024 群里发了一个重磅消息&#xff1a; common-intellisense 支持 TinyVue 组件库啦&#xff01; common-intellisense 插件能够提供超级强大的智能提示功能&…...

图片在线压缩有效方法详解,分享7款最佳图片压缩工具免费(全新)

当您的系统中图片数量不断增加&#xff0c;却无法删除时&#xff0c;那么就需要通过图片压缩来解决您的问题。随着图片文件的增大&#xff0c;高分辨率图片占据了大量存储空间。而此时系统中的存储空间也开始变得不够用&#xff0c;无法跟上高质量图片的增长。因此&#xff0c;…...

electron安装及快速创建

electron安装及快速创建 electron是一个使用 JavaScript、HTML 和 CSS 构建桌面应用程序的框架。 详细内容见官网&#xff1a;https://www.electronjs.org/zh/docs/latest/。 今天来记录下练习中的安装过程和hello world的创建。 创建项目文件夹&#xff0c;并执行npm 初始化命…...

需要消化的知识点

需要消化 消灭清单 如何自定义一个Interceptor拦截器&#xff1f; 后端开发可以用上的前端技巧 10个堪称神器的 Java 学习网站. 【前端胖头鱼】11 chrome高级调试技巧&#xff0c;学会效率直接提升666% 【前端胖头鱼】10个我经常逛的“小网站” 【前端劝退师lv-6】Chrome D…...

2024年7月25日(Git gitlab以及分支管理 )

分布式版本控制系统 一、Git概述 Git 是一种分布式版本控制系统,用于跟踪和管理代码的变更。它是由Linus Torvalds创建的,最 初被设计用于Linux内核的开发。Git允许开发人员跟踪和管理代码的版本,并且可以在不同的开 发人员之间进行协作。 Github 用的就是Git系统来管理它们的…...

pdf格式过大怎么样变小 pdf文件过大如何缩小上传 超实用的简单方法

面对体积庞大的 PDF 文件&#xff0c;我们常常需要寻找有效的方法来缩减其大小。这不仅能够优化存储空间&#xff0c;还能提升文件的传输和打开速度。PDF文件以其稳定性和跨平台兼容性成为工作和学习中的重要文件格式。然而&#xff0c;当我们需要通过邮件发送或上传大文件时&a…...

前端文件下载word乱码问题

记录一次word下载乱码问题&#xff1a; 用的请求是axios库&#xff0c;然后用Blob去接收二进制文件 思路&#xff1a;现在的解决办法有以下几种&#xff0c;看看是对应哪种&#xff0c;可以尝试解决 1.将响应类型设为blob&#xff0c;这也是最重要的&#xff0c;如果没有解决…...

repo中的default.xml文件project name为什么一样?

文章目录 default.xml文件介绍为什么 name 是一样的&#xff0c;path 不一样&#xff1f;总结 default.xml文件介绍 在 repo 工具的 default.xml 文件中&#xff0c;定义了多个 project 元素&#xff0c;每个元素都代表一个 Git 仓库。 XML 定义了多个不同的 project 元素&…...

<section id=“nice“ data-tool=“mdnice编辑器“ data-webs

大模型日报 2024-07-24 大模型资讯 Meta发布最大Llama 3 AI模型&#xff0c;语言和数学能力提升 摘要: Meta公司发布了其迄今为止最大的Llama 3人工智能模型。该模型主要免费提供&#xff0c;具备多语言处理能力&#xff0c;并在语言和数学方面表现出显著提升。 Meta发布最强AI…...

作业7.26~28

全双工&#xff1a; 通信双方 既可以发送&#xff0c;也可以接收数据 1. 利用多线程 或者 多进程&#xff0c; 实现TCP服务器 和 客户端的全双工通信 思路&#xff1a; 服务器和客户端&#xff0c; 在建立通信以后&#xff0c;可以创建线程&#xff0c;在线程编写另一个功能代…...

自定义webIpad证件相机(webRTC)

该技术方案可用于各浏览器自定义相机开发 相机UI&#xff08;index.html&#xff09; <!DOCTYPE html> <html lang"zh" prew"-1"><head><meta charset"UTF-8"><meta name"viewport"content"user-sc…...

GO发票真伪批量查验方法、数电票查验接口

“教”给机器标注数据的正确率就决定了人工智能判断的正确率。翔云人工智能开放平台的OCR产品经过我们的开发人员精心调“教”&#xff0c;识别率高、识别速度快。 发票&#xff0c;是发生的成本、费用或收入的原始凭证。于公司来说&#xff0c;发票主要是公司做账的依据&…...

【Go系列】Go的UI框架Fyne

前言 总有人说Go语言是一门后端编程语言。 Go虽然能够很好地处理后端开发&#xff0c;但是者不代表它没有UI库&#xff0c;不能做GUI&#xff0c;我们一起来看看Go怎么来画UI吧。 正文 Go语言由于其简洁的语法、高效的性能和跨平台的编译能力&#xff0c;非常适合用于开发GUI…...

.NET MAUI:跨平台开发的未来

常用资源 &#xff08;1&#xff09;.NET MAUI8构建应用文档。 Build your first .NET MAUI app - .NET MAUI | Microsoft Learn 一、什么是 .NET MAUI&#xff1f; .NET Multi-platform App UI (.NET MAUI) 是微软推出的一款跨平台开发框架。作为 Xamarin.Forms 的下一代产…...

VSCode切换默认终端

我的VSCode默认终端为PowerShell&#xff0c;每次新建都会自动打开PowerShell。但是我想让每次都变为cmd&#xff0c;也就是Command Prompt 更改默认终端的操作方法如下&#xff1a; 键盘调出命令面板&#xff08;CtrlShiftP&#xff09;中,输入Terminal: Select Default Prof…...

卫星观测叶绿素的相反信号

Contrasted Trends in Chlorophyll-a Satellite Products 运用卫星产品研究Chl的长时间序列变化时需要注意 Introduction &#xff08;1&#xff09;研究叶绿素的长期变化&#xff0c;需要至少40年的长时间序列&#xff1b; &#xff08;2&#xff09;Tian and Zhang 2023报告…...

2024年最新NVIDIA T4价格表及行业趋势!

英伟达&#xff08;NVIDIA&#xff09;作为目前全球T0级别的GPU制造商&#xff0c;其T4系列显卡以其卓越的计算性能和能效比&#xff0c;在数据中心、云计算及AI领域占据重要地位。 一、NVIDIA T4价格表概览 在探讨NVIDIA T4显卡的价格时&#xff0c;我们需要从直接购买和租赁…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...