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

【代码随想录训练营】【Day 65】【图论-2】| 卡码 99

【代码随想录训练营】【Day 65】【图论-2】| 卡码 99

需强化知识点

  • 深度搜索和广度搜索

题目

99. 岛屿数量

思想:遍历到为1的节点,再搜索标记,每遇到新的陆地节点,增加计数

  • 深度搜索
  • 广度搜索:此处用 [] 作为待遍历队列也可,que(append,popleft)
import collectionsdef dfs(grid, visited, x, y):dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]for add_x, add_y in dirs:next_x = x + add_xnext_y = y + add_yif next_x < 0 or next_x >= len(grid) or next_y < 0 or next_y >= len(grid[0]):continueif not visited[next_x][next_y] and grid[next_x][next_y]:visited[next_x][next_y] = Truedfs(grid, visited, next_x, next_y)def bfs(grid, visited, x, y):dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]que = collections.deque()# que = []que.append([x, y])visited[x][y] = Truewhile que:# cur = que.pop()cur = que.popleft()cur_x = cur[0]cur_y = cur[1]for add_x, add_y in dirs:next_x = cur_x + add_xnext_y = cur_y + add_yif next_x < 0 or next_x >= len(grid) or next_y < 0 or next_y >= len(grid[0]):continueif not visited[next_x][next_y] and grid[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]result = 0
for i in range(m):for j in range(n):if not visited[i][j] and grid[i][j]:visited[i][j] = Trueresult += 1bfs(grid, visited, i, j)print(result)

相关文章:

【代码随想录训练营】【Day 65】【图论-2】| 卡码 99

【代码随想录训练营】【Day 65】【图论-2】| 卡码 99 需强化知识点 深度搜索和广度搜索 题目 99. 岛屿数量 思想&#xff1a;遍历到为1的节点&#xff0c;再搜索标记&#xff0c;每遇到新的陆地节点&#xff0c;增加计数 深度搜索广度搜索&#xff1a;此处用 [] 作为待遍…...

【动态规划】139. 单词拆分

139. 单词拆分 难度&#xff1a;中等 力扣地址&#xff1a;https://leetcode.cn/problems/word-break/description/ 问题描述 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意&#xff1a;不要求字…...

【C++】空指针访问成员函数

空指针访问成员函数 C中空指针也是可以调用成员函数的&#xff0c;但是也要注意有没有用到this指针 如果用到this指针&#xff0c;需要加以判断保证代码的健壮性 class Animal { public:void fun1() {//正常的成员函数}void fun2() {if (this NULL) {return;//如果没有这个…...

Linux的IO易错点总结

本文主要记录IO的一些易错操作。 阻塞IO和非阻塞IO&#xff0c;一般都是针对数据读取的&#xff0c;因为write是主动行为&#xff0c;不存在阻塞这一说。 非阻塞式IO&#xff0c;一般都要配合while轮询来读取数据。 IO多路复用 当只检测一路IO的时候&#xff0c;和普通IO的作…...

【Android面试八股文】说一说你对Android中的Context的理解吧

文章目录 一、Context是什么?1.1 主要功能和用途1.2 如何获取 Context 实例?1.3 注意事项二、Context 类的层次结构三、Context的数量四、Context的注意事项五、Android 中有多少类型的 Context,它们有什么区别 ?六、Contextlmpl实例是什么时候生成的,在 Activity 的 oncr…...

AI在音乐创作中的角色:创造还是毁灭?

目录 一、基本情况介绍 二、近期新闻 三、AI生成音乐方面的商业模式 四、人工智能和音乐人可能的合作模式 五、人们如何借助AI来创作音乐 六、人工智能在创意产业引发的伦理道德问题 七、如何平衡技术发展与提高人类创造积极性的关系&#xff1f; 总结 一、基本情况介绍…...

[深入理解DDR] 总目录

依公知及经验整理&#xff0c;原创保护&#xff0c;禁止转载。 专栏 《深入理解DDR》 蓝色的是传送门&#xff0c;点击链接即可到达指定文章。 图。 DDR 分类 导论 [RAM] DRAM 导论&#xff1a;DDR4 | DDR5 | LPDDR5 | GDRR6 | HBM 应运而生 运存与内存&#xff1f;内存与存…...

模板方法模式在金融业务中的应用及其框架实现

引言 模板方法模式&#xff08;Template Method Pattern&#xff09;是一种行为设计模式&#xff0c;它在一个方法中定义一个算法的框架&#xff0c;而将一些步骤的实现延迟到子类中。模板方法允许子类在不改变算法结构的情况下重新定义算法的某些步骤。在金融业务中&#xff…...

leetcode347.前k个高频元素

leetcode347.前k个高频元素 给你一个整数数组 nums 和一个整数 k &#xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 示例 1: 输入: nums [1,1,1,2,2,3], k 2 输出: [1,2] 示例 2: 输入: nums [1], k 1 输出: [1] 优先队列法 struct hash_…...

c++(二)

1. 类和对象 1.1. 封装 封装的意义 将属性和行为作为一个整体&#xff0c;表现生活中的事物&#xff1b;将属性和行为加以权限控制 public -> 公共权限&#xff1a;类内可以访问&#xff0c;类外也可以访问protected -> 保护权限&#xff1a;类内可以访问&#xff0c;…...

基于PHP的初中数学题库管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的初中数学题库管理系统 一 介绍 此初中数学题库管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;系统角色分为学生&#xff0c;教师和管理员。(附带参考设计文档) 技术栈&#xff1a;phpmysqlphpstudyvscode 二 功能 …...

WDG看门狗

1 WDG 1.1 简介 WDG是看门狗定时器&#xff08;Watchdog Timer&#xff09;的缩写&#xff0c;它是一种用于计算机和嵌入式系统中的定时器&#xff0c;用来检测和恢复系统故障。 看门狗就像是一个忠诚的宠物狗&#xff0c;它时刻盯着你的程序&#xff0c;确保它们正常运行。…...

zabbix server client 安装配置

Zabbix Server 采用源码包部署&#xff0c;数据库采用 MySQL8.0 版本&#xff0c;zabbix-web 使用 nginxphp 来实现。具体信息如下&#xff1a; 软件名 版本 安装方式 Zabbix Server 6.0.3 源码安装 Zabbix Agent 6.0.3 源码安装 MySQL 8.0.28 yum安装 Nginx 1.20…...

Unity关于Addressables.Release释放资源内存问题

前言 最近在编写基于Addressables的资源管理器&#xff0c;对于资源释放模块配合MemoryProfiler进行了测试&#xff0c;下面总结下测试Addressables.Release的结论。 总结 使用Addressables.Release释放资源时&#xff0c;通过MemoryProfiler检查内存信息发现加载的内容还在…...

运算放大器(运放)带宽和带宽平坦度

运算放大器带宽和带宽平坦度 电压反馈型运算放大器的带宽 下图1显示电压反馈型运算放大器的开环频率响应。有两种可能&#xff1a;图1A是最常见的情况&#xff0c;高直流增益以6dB/倍频程从极低频率下降至单位增益&#xff0c;也就是典型的单极点响应。相比之下&#xff0c;图…...

npm常用命令使用与事件案例

概述 npm&#xff08;Node Package Manager&#xff09;是一个JavaScript编程语言的包管理器&#xff0c;用于Node.js应用程序。它允许用户安装、共享和管理具有重复使用价值的代码&#xff08;包&#xff09;&#xff0c;这些代码可以是库、工具或应用程序。 npm常用命令详解…...

Spring Boot中的定时任务调度

Spring Boot中的定时任务调度 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01;今天我们将深入探讨如何在Spring Boot应用中实现定时任务调度&#xff0c;这在实际…...

Hadoop3:MapReduce中的ETL(数据清洗)

一、概念说明 “ETL&#xff0c;是英文Extract-Transform-Load的缩写&#xff0c;用来描述将数据从来源端经过抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;、加载&#xff08;Load&#xff09;至目的端的过程。ETL一词较常用在数据仓库&#…...

python解锁图片相似度的神奇力量

在这个信息爆炸的时代,图片成为了我们传递信息、表达情感和记录生活的重要方式。然而,面对海量的图片资源,如何快速准确地找到相似的图片,成为了一个亟待解决的问题。现在,让我们为您揭开图片相似度的神秘面纱,带您领略这一创新技术的魅力! 图片相似度技术,就像是一位…...

TensorFlow 的原理与使用

文章目录 TensorFlow 的基本原理1. 计算图&#xff08;Computation Graph&#xff09;2. 张量&#xff08;Tensor&#xff09;3. 会话&#xff08;Session&#xff09;4. 自动微分&#xff08;Automatic Differentiation&#xff09; TensorFlow 的使用安装 TensorFlow基本使用…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

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

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

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...