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

【代码随想录训练营】【Day 66】【图论-3】| 卡码 101-104

【代码随想录训练营】【Day 66】【图论-3】| 卡码 101-104

需强化知识点

  • 103,104 优化思路

题目

101. 孤岛的总面积

  • 此处 area 多余
def dfs(grid, x, y, area):dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]m, n = len(grid), len(grid[0])area[0] += 1grid[x][y] = 0for add_x, add_y in dirs:next_x, next_y = x + add_x, y + add_yif next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:continueif grid[next_x][next_y]:dfs(grid, next_x, next_y, area)tmp = list(map(int, input().split()))
m, n = tmp[0], tmp[1]
grid = [[0] * n for _ in range(m)]for i in range(m):tmp = list(map(int, input().split()))for j in range(n):grid[i][j] = tmp[j]for i in range(m):if grid[i][0]:dfs(grid, i, 0, [0])if grid[i][n-1]:dfs(grid, i, n-1, [0])for j in range(n):if grid[0][j]:dfs(grid, 0, j, [0])if grid[m-1][j]:dfs(grid, m-1, j, [0])cur = 0
for i in range(m):for j in range(n):if grid[i][j]:cur += 1print(cur)          

102. 沉没孤岛

  • 思路:从左右上下边界出发遍历,然后visited数组标记,最后 grid 为 1 且没被访问过的,即为孤岛
import collectionsdef bfs(grid, visited, x, y):dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]m, n = len(grid), len(grid[0])que = collections.deque()que.append([x, y])visited[x][y] = Truewhile que:tmp = que.popleft()cur_x, cur_y = tmp[0], tmp[1]for add_x, add_y in dirs:next_x, next_y = cur_x + add_x, cur_y + add_yif next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:continueif grid[next_x][next_y] and not visited[next_x][next_y]:que.append([next_x, next_y])visited[next_x][next_y] = Truetmp = list(map(int, input().split()))
m, n = tmp[0], tmp[1]
grid = [[0] * n for _ in range(m)]
visited = [[False] * n for _ in range(m)]for i in range(m):tmp = list(map(int, input().split()))for j in range(n):grid[i][j] = tmp[j]for i in range(m):if grid[i][0]:bfs(grid, visited ,i, 0)if grid[i][n-1]:bfs(grid, visited, i, n-1)for j in range(n):if grid[0][j]:bfs(grid, visited, 0, j)if grid[m-1][j]:bfs(grid, visited, m-1, j)for i in range(m):for j in range(n):if grid[i][j] and not visited[i][j]:grid[i][j] = 0for i in range(m):for j in range(n):print(grid[i][j], end=" ")

103. 水流问题

  • 暴力法:直接每个位置 dfs,然后根据其最终是否能到达边界位置,返回布尔值
  • 优化思路:从边界出发,逆流而上,最终不能被访问到的地方为结果
# def dfs(grid, visited, x, y):
#     dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]#     m, n = len(grid), len(grid[0])
#     visited[x][y] = True#     for add_x, add_y in dirs:
#         next_x, next_y = x + add_x, y + add_y
#         if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:
#             continue
#         if grid[x][y] < grid[next_x][next_y]:
#             continue
#         if not visited[next_x][next_y]:
#             dfs(grid, visited, next_x, next_y)# def isResult(grid, x, y):
#     m, n = len(grid), len(grid[0])
#     visited = [[False] * n for _ in range(m)]
#     dfs(grid, visited, x, y)
#     first_result, second_result = False, False#     for i in range(m):
#         if visited[i][0]:
#             first_result = True
#         if visited[i][n-1]:
#             second_result = True#     for j in range(n):
#         if visited[0][j]:
#             first_result = True
#         if visited[m-1][j]:
#             second_result = True#     return first_result and second_result# tmp = list(map(int, input().split()))
# m, n = tmp[0], tmp[1]# grid = [[0] * n for _ in range(m)]
# for i in range(m):
#     tmp = list(map(int, input().split()))
#     for j in range(n):
#         grid[i][j] = tmp[j]# for i in range(m):
#     for j in range(n):
#         if isResult(grid, i, j):
#             print("{} {}".format(i, j))def dfs(grid, visited, x, y):dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]m, n = len(grid), len(grid[0])visited[x][y] = Truefor add_x, add_y in dirs:next_x, next_y = x + add_x, y + add_yif next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:continue# 等于不行if grid[x][y] > grid[next_x][next_y]:continueif not visited[next_x][next_y]:dfs(grid, visited, next_x, next_y)tmp = list(map(int, input().split()))
m, n = tmp[0], tmp[1]grid = [[0] * n for _ in range(m)]
for i in range(m):tmp = list(map(int, input().split()))for j in range(n):grid[i][j] = tmp[j]   visited_first = [[False]*n for _ in range(m)]
visited_second = [[False]*n for _ in range(m)]for i in range(m):dfs(grid, visited_first, i, 0)dfs(grid, visited_second, i, n-1)for j in range(n):dfs(grid, visited_first, 0, j)dfs(grid, visited_second, m-1, j)for i in range(m):for j in range(n):if visited_first[i][j] and visited_second[i][j]:print("{} {}".format(i, j))

104. 建造最大岛屿

  • 暴力法:直接每个为0的位置,dfs,记录其面积
  • 优化思路:先记录每个岛屿的面积,并编号,然后 每个为0的位置,假设其为1,然后加上周围能访问到岛屿面积
    • 注意周围访问岛屿的去重问题,以及为grid 0的情况
def dfs(grid, mask, x, y, count):dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]m, n = len(grid), len(grid[0])grid[x][y] = maskcount[0] += 1for add_x, add_y in dirs:next_x, next_y = x + add_x, y + add_yif next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:continueif grid[next_x][next_y] != 1 :continuedfs(grid, mask, next_x, next_y, count)def main():tmp = list(map(int, input().split()))m, n = tmp[0], tmp[1]grid = [[0] * n for _ in range(m)]for i in range(m):tmp = list(map(int, input().split()))for j in range(n):grid[i][j] = tmp[j]   mask = 2isAllgrid = TruegridNum = {}for i in range(m):for j in range(n):if grid[i][j] == 0:isAllgrid = Falseif grid[i][j] == 1:count = [0]dfs(grid, mask, i, j, count)gridNum[mask] = count[0]mask += 1if isAllgrid:print(m*n)return result = 0dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]for i in range(m):for j in range(n):if grid[i][j] == 0:tmp = 1visitedGrid = []for add_x, add_y in dirs:next_x, next_y = i + add_x, j + add_yif next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:continueif grid[next_x][next_y] not in visitedGrid and grid[next_x][next_y] != 0:tmp += gridNum[grid[next_x][next_y]]visitedGrid.append(grid[next_x][next_y])result = max(result, tmp)print(result)   main()

相关文章:

【代码随想录训练营】【Day 66】【图论-3】| 卡码 101-104

【代码随想录训练营】【Day 66】【图论-3】| 卡码 101-104 需强化知识点 103&#xff0c;104 优化思路 题目 101. 孤岛的总面积 此处 area 多余 def dfs(grid, x, y, area):dirs [[0, 1], [0, -1], [1, 0], [-1, 0]]m, n len(grid), len(grid[0])area[0] 1grid[x][y] …...

【面试系列】C#高频面试题

欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;欢迎订阅相关专栏&#xff1a; ⭐️ 全网最全IT互联网公司面试宝典&#xff1a;收集整理全网各大IT互联网公司技术、项目、HR面试真题. ⭐️ AIGC时代的创新与未来&#xff1a;详细讲解AIGC的概念、核心技术、…...

AI助力校园安全:EasyCVR视频智能技术在校园欺凌中的应用

一、背景分析 近年来&#xff0c;各地深入开展中小学生欺凌行为治理工作&#xff0c;但有的地方学生欺凌事件仍时有发生&#xff0c;严重损害学生身心健康&#xff0c;引发社会广泛关注。为此&#xff0c;教育部制定了《防范中小学生欺凌专项治理行动工作方案》进一步防范和遏…...

Yolov8可视化界面使用说明,含代码

⭐⭐ YOLOv8改进专栏|包含主干、模块、注意力机制、检测头等前沿创新 ​ ⭐⭐ YOLOv8可视化界面如下 使用需要安装opencv-python、torch、numpy及PySide6(python版本>3.9) pip install PySide6 pip install numpy pip install opencv-python 使用说明 运行下方代码&#xf…...

怎么使用MarkDown画矩阵

本文首发于公众号“AntDream”&#xff0c;欢迎微信搜索“AntDream”或扫描文章底部二维码关注&#xff0c;和我一起每天进步一点点 今天写文章需要用到矩阵&#xff0c;记录一下 画矩阵需要用到特殊的语法 &#xff08;1&#xff09;画普通矩阵&#xff0c;不带括号的 $$be…...

Kafka入门-基础概念及参数

一、Kafka术语 1. Broker Kafka属于分布式的消息引擎系统&#xff0c;它的主要功能是提供一套完备的消息发布与订阅解决方案。可以为每个业务、每个应用甚至是每类数据都创建专属的主题。 Kafka的服务器端由被称为Broker的服务进程构成&#xff0c;即一个Kafka集群由多个Broke…...

Clickhouse 常见操作

数据查询 从json array string中解析字段 json array string 为json.dumps(array(dict)) select JSONExtractString(row,"Date") as Date from( select arrayJoin(JSONExtractArrayRaw(Remarks)) as row from table x )JSONExtractArrayRaw&#xff1a; 将JsonS…...

Docker使用daocloud镜像加速

之前给大家分享的阿里云的镜像加速&#xff0c;今天再给大家分享一个还可以使用的镜像加速地址daocloud。 经过测试速度还是比较快的。 [rootbogon ~]# cat /etc/docker/daemon.json {"registry-mirrors": ["https://docker.m.daocloud.io"] }[rootbogon…...

flink的窗口

目录 窗口分类 1.按照驱动类型分类 1. 时间窗口&#xff08;Time window&#xff09; 2.计数窗口&#xff08;Count window&#xff09; 2.按照窗口分配数据的规则分类 窗口API分类 API调用 窗口分配器器&#xff1a; 窗口函数 增量聚合函数&#xff1a; 全窗口函数…...

lodash.js 工具库

lodash 是什么? Lodash是一个流行的JavaScript实用工具库,提供了许多高效、高兼容性的工具函数,能够方便地处理集合、字符串、数值、函数等多种数据类型,大大提高工作效率。 lodash官网 文档参见:Lodash Documentation lodash 在Vue中怎么使用? 1、首先安装 lodash np…...

使用ElementUI组件库

引入ElementUI组件库 1.安装插件 npm i element-ui -S 2.引入组件库 import ElementUI from element-ui; 3.引入全部样式 import element-ui/lib/theme-chalk/index.css; 4.使用 Vue.use(ElementUI); 5.在官网寻找所需样式 饿了么组件官网 我这里以button为例 6.在组件中使用…...

【SkiaSharp绘图14】SKCanvas方法详解(三)URL注释、按顶点绘制、 是否裁切区域之外、旋转、缩放、倾斜、平移、保存/恢复画布

文章目录 SKCanvas方法DrawUrlAnnotation 绘制URL注释DrawVertices 按顶点绘制Flush 立即绘制QuickReject 判断区域是否在裁切区域之外ResetMatrix重置矩阵Restore、RestoreToCountRotateDegrees按角度旋转画布RotateRadians按弧度旋转画布SaveLayer保存并新建图层Scale 缩放画…...

WebDriver API (2)

本文将继续上文对WebDriver API的功能使用进行介绍。 一、浏览器操作 1. 浏览器前进forward与后退back 浏览器前进操作是指导航到前一个页面&#xff0c;在浏览器的历史记录中向前移动一页。 浏览器后退操作是指导航到前一个页面&#xff0c;在浏览器的历史记录中向后移动一…...

GCP FrontendConfig 详解:优化您的云负载均衡

目录 1. 什么是GCP FrontendConfig? 2. FrontendConfig的主要功能 2.1 协议选择 2.2 SSL/TLS配置 2.3 重定向配置 2.4 自定义响应头 3. 配置FrontendConfig 4. FrontendConfig的高级特性 4.1 智能路由 4.2 流量控制 4.3 日志和监控 5. FrontendConfig最佳实践 5.…...

TensorFlow代码逻辑 vs PyTorch代码逻辑

文章目录 一、TensorFlow&#xff08;一&#xff09;导入必要的库&#xff08;二&#xff09;加载MNIST数据集&#xff08;三&#xff09;数据预处理&#xff08;四&#xff09;构建神经网络模型&#xff08;五&#xff09;编译模型&#xff08;六&#xff09;训练模型&#xf…...

boost asio异步服务器(4)处理粘包

粘包的产生 当客户端发送多个数据包给服务器时&#xff0c;服务器底层的tcp接收缓冲区收到的数据为粘连在一起的。这种情况的产生通常是服务器端处理数据的速率不如客户端的发送速率的情况。比如&#xff1a;客户端1s内连续发送了两个hello world&#xff01;,服务器过了2s才接…...

【QT】常用控件|widget|QPushButton|RadioButton|核心属性

目录 ​编辑 概念 信号与槽机制 控件的多样性和定制性 核心属性 enabled geometry ​编辑 windowTiltle windowIcon toolTip styleSheet PushButton RadioButton 概念 QT 控件是构成图形用户界面&#xff08;GUI&#xff09;的基础组件&#xff0c;它们是实现与…...

【C++ Primer Plus学习记录】函数参数和按值传递

函数可以有多个参数。在调用函数时&#xff0c;只需使用都逗号将这些参数分开即可&#xff1a; n_chars(R,25); 上述函数调用将两个参数传递给函数n_chars()&#xff0c;我们将稍后定义该函数。 同样&#xff0c;在定义函数时&#xff0c;也在函数头中使用由逗号分隔的参数声…...

MySQL:设计数据库与操作

设计数据库 1. 数据建模1.1 概念模型1.2 逻辑模型1.3 实体模型主键外键外键约束 2. 标准化2.1 第一范式2.2 链接表2.3 第二范式2.4 第三范式 3. 数据库模型修改3.1 模型的正向工程3.2 同步数据库模型3.3 模型的逆向工程3.4 实际应用建议 4. 数据库实体模型4.1 创建和删除数据库…...

OBS 免费的录屏软件

一、下载 obs 【OBS】OBS Studio 的安装、参数设置和录屏、摄像头使用教程-CSDN博客 二、使用 obs & 输出无黑屏 【OBS任意指定区域录屏的方法-哔哩哔哩】 https://b23.tv/aM0hj8A OBS任意指定区域录屏的方法_哔哩哔哩_bilibili 步骤&#xff1a; 1&#xff09;获取区域…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...