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

代码随想录算法训练营第五十一天|Day51 图论

岛屿数量 深搜

https://www.programmercarl.com/kamacoder/0099.%E5%B2%9B%E5%B1%BF%E7%9A%84%E6%95%B0%E9%87%8F%E6%B7%B1%E6%90%9C.html

思路

#include <stdio.h>
#define MAX_SIZE 50
int grid[MAX_SIZE][MAX_SIZE]; 
int visited[MAX_SIZE][MAX_SIZE]; 
int N, M; 
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void DFS(int x, int y) {visited[x][y] = 1; for (int i = 0; i < 4; i++) {int newX = x + directions[i][0];int newY = y + directions[i][1];if (newX >= 0 && newX < N && newY >= 0 && newY < M && grid[newX][newY] == 1 && !visited[newX][newY]) {DFS(newX, newY);}}
}
int main() {scanf("%d %d", &N, &M);for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {scanf("%d", &grid[i][j]);visited[i][j] = 0; }}int islandCount = 0; for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (grid[i][j] == 1 && !visited[i][j]) {DFS(i, j); islandCount++; }}}printf("%d\n", islandCount);return 0;
}

学习反思

用深度优先搜索算法(Depth-First Search, DFS)求解岛屿数量的程序。代码使用一个二维数组grid来表示一个由0和1组成的地图,其中1表示陆地,0表示水。代码中的visited数组用于记录每个格子是否被访问过。主要的算法逻辑在DFS函数中实现。DFS函数会将当前格子标记为已访问,然后递归地对当前格子的上、下、左、右四个邻居格子进行访问,如果邻居格子满足一些条件(在地图范围内且为1且未被访问过),则继续递归访问邻居格子。通过递归的方式,DFS函数可以遍历到所有与当前格子相连的陆地格子。在主函数中,首先读取地图的行数N和列数M。然后使用两个嵌套循环遍历地图中的所有格子,并读取每个格子的值并初始化visited数组。接下来,使用两个嵌套循环遍历地图中的所有格子。如果发现一个未访问过的陆地格子,就调用DFS函数进行访问,并将岛屿数量加1。最后,输出岛屿数量。这段代码的时间复杂度为O(NM),其中N和M分别为地图的行数和列数。代码中使用了递归,递归深度最大为NM,空间复杂度为O(N*M)。

岛屿数量 广搜

https://www.programmercarl.com/kamacoder/0099.%E5%B2%9B%E5%B1%BF%E7%9A%84%E6%95%B0%E9%87%8F%E5%B9%BF%E6%90%9C.html

思路

#include <stdio.h>#define MAX 50int grid[MAX][MAX];
int visited[MAX][MAX];
int n, m;
int directions[4][2] = {{-1, 0},  // 上{1, 0},   // 下{0, -1},  // 左{0, 1}    // 右
};
void dfs(int x, int y) {visited[x][y] = 1;for (int i = 0; i < 4; i++) {int newX = x + directions[i][0];int newY = y + directions[i][1];if (newX >= 0 && newX < n && newY >= 0 && newY < m && grid[newX][newY] == 1 && visited[newX][newY] == 0) {dfs(newX, newY);}}
}int main() {scanf("%d %d", &n, &m);for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {scanf("%d", &grid[i][j]);visited[i][j] = 0; }}int islandCount = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1 && visited[i][j] == 0) {dfs(i, j); islandCount++; }}}printf("%d\n", islandCount);return 0;
}

学习反思

用深度优先搜索算法(DFS)来解决岛屿数量的问题。代码将二维数组grid用于表示地图,其中1表示陆地,0表示水。visited数组用于标记格子是否被访问过。主要的算法逻辑在dfs函数中实现。dfs函数会将当前格子标记为已访问,然后递归地访问当前格子的上、下、左、右四个邻居格子。如果邻居格子满足一些条件(在地图范围内且为1且未被访问过),则继续递归地访问邻居格子。通过递归的方式,dfs函数可以遍历到所有与当前格子相连的陆地格子。在主函数中,首先读取地图的行数n和列数m。然后使用两个嵌套循环遍历地图中的所有格子,并读取每个格子的值并初始化visited数组。接下来,使用两个嵌套循环遍历地图中的所有格子。如果发现一个未访问过的陆地格子,就调用dfs函数进行访问,并将岛屿数量加1。最后,输出岛屿数量。这段代码的时间复杂度为O(nm),其中n和m分别为地图的行数和列数。代码中使用了递归,递归深度最大为nm,空间复杂度为O(n*m)。

岛屿的最大面积

https://www.programmercarl.com/kamacoder/0100.%E5%B2%9B%E5%B1%BF%E7%9A%84%E6%9C%80%E5%A4%A7%E9%9D%A2%E7%A7%AF.html

思路

#include <stdio.h>#define MAX_N 50
#define MAX_M 50int grid[MAX_N][MAX_M];
int visited[MAX_N][MAX_M];
int N, M;
int directions[4][2] = {{0, 1},   // right{1, 0},   // down{0, -1},  // left{-1, 0}   // up
};
int is_valid(int x, int y) {return x >= 0 && x < N && y >= 0 && y < M && grid[x][y] == 1 && !visited[x][y];
}
int dfs(int x, int y) {visited[x][y] = 1;int area = 1;for (int i = 0; i < 4; i++) {int new_x = x + directions[i][0];int new_y = y + directions[i][1];if (is_valid(new_x, new_y)) {area += dfs(new_x, new_y);}}return area;
}
int main() {scanf("%d %d", &N, &M);for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {scanf("%d", &grid[i][j]);visited[i][j] = 0; }}int max_area = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {// If we find a land cell that hasn't been visited yetif (grid[i][j] == 1 && !visited[i][j]) {int area = dfs(i, j);if (area > max_area) {max_area = area;}}}}  printf("%d\n", max_area);return 0;
}

学习反思

使用深度优先搜索算法(DFS)来计算最大岛屿面积。首先,定义了最大行数N和最大列数M,并声明了地图数组grid和访问数组visited。is_valid函数用于判断一个格子是否有效,即格子的坐标在合法范围内,且为陆地(值为1),且未被访问过。dfs函数用于进行深度优先搜索。它首先将当前格子标记为已访问,并初始化面积为1。然后,遍历当前格子的四个方向的邻居格子,如果邻居格子有效,则递归调用dfs函数,并将返回的面积加到当前面积上。最后,返回当前面积。在主函数中,首先读取地图的行数N和列数M。然后,使用两个嵌套循环遍历地图中的所有格子,并读取每个格子的值并初始化visited数组。接下来,使用两个嵌套循环遍历地图中的所有格子。如果发现一个未访问过的陆地格子,就调用dfs函数进行深度优先搜索,并将返回的面积与最大面积进行比较,更新最大面积。最后,输出最大面积。这段代码的时间复杂度为O(NM),其中N和M分别为地图的行数和列数。代码中使用了递归,递归深度最大为NM,空间复杂度为O(N*M)。为了提高效率,使用了is_valid函数来判断格子的有效性,避免了不必要的访问和递归调用。

相关文章:

代码随想录算法训练营第五十一天|Day51 图论

岛屿数量 深搜 https://www.programmercarl.com/kamacoder/0099.%E5%B2%9B%E5%B1%BF%E7%9A%84%E6%95%B0%E9%87%8F%E6%B7%B1%E6%90%9C.html 思路 #include <stdio.h> #define MAX_SIZE 50 int grid[MAX_SIZE][MAX_SIZE]; int visited[MAX_SIZE][MAX_SIZE]; int N, M; …...

uniapp 自定义加载组件,全屏加载,局部加载 (微信小程序)

效果图 全屏加载 页面加载使用 局部加载 列表加载里面使用 使用gif html <template><view><view class"" v-if"typeFullScreen"><view class"loading" v-if"show"><view class""><i…...

STM32完全学习——系统时钟设置

一、时钟框图的解读 首先我们知道STM32在上电初始化之后使用的是内部的HSI未经过分频直接通过SW供给给系统时钟&#xff0c;由于内部HSI存在较大的误差&#xff0c;因此我们在系统完成上电初始化&#xff0c;之后需要将STM32的时钟切换到外部HSE作为系统时钟&#xff0c;那么我…...

Github 2024-11-16Rust开源项目日报 Top10

根据Github Trendings的统计,今日(2024-11-16统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Rust项目10Go项目1Python项目1Lapce:用 Rust 编写的极快且强大的代码编辑器 创建周期:2181 天开发语言:Rust协议类型:Apache License 2.0St…...

CH03_反射

第3章&#xff1a;反射 本章目标 掌握反射的原理 熟悉反射的基本运用 本章内容 反射是什么 C# 编译运行过程 首先我们在VS点击编译的时候&#xff0c;就会将C#源代码编译成程序集 程序集以可执行文件 (.exe) 或动态链接库文件 (.dll) 的形式实现 程序集中包含有Microsoft …...

vue2侧边导航栏路由

<template><div><!-- :default-active"$route.path" 和index对应其路径 --><el-menu:default-active"active"class"el-menu-vertical-demo"background-color"#545c64"text-color"#fff"active-text-col…...

core 不可变类型 线程安全 record

当一个类型的对象在创建时被指定状态后&#xff0c;就不会再变化的对象&#xff0c;我们称之为不可变类型。这种类型是线程安全的&#xff0c;不需要进行线程同步&#xff0c;非常适合并行计算的数据共享。它减少了更新对象会引起各种bug的风险&#xff0c;更为安全。 System.D…...

linux之调度管理(8)-SMP cpu 的 psci启动

一、psci介绍 psci是arm提供的一套电源管理接口&#xff0c;当前一共包含0.1、0.2和1.0三个版本。它可被用于以下场景&#xff1a; &#xff08;1&#xff09;cpu的idle管理 &#xff08;2&#xff09;cpu hotplug以及secondary cpu启动 &#xff08;3&#xff09;系统shutdo…...

review-消息中间件MQ

RabbitMQ RabbitMQ&#xff0c;作为当今流行的开源消息代理软件&#xff0c;以其卓越的可靠性、灵活性和易用性在微服务架构和分布式系统中扮演着至关重要的角色。它不仅能够确保消息在不同系统组件间的高效传递&#xff0c;还能通过其高级消息队列协议&#xff08;AMQP&#x…...

leetcode400第N位数字

代码 class Solution {public int findNthDigit(int n) {int base 1;//位数int weight 9;//权重while(n>(long)base*weight){//300n-base*weight;base;weight*10;}//n111 base3 weight900;n--;int res (int)Math.pow(10,base-1)n/base;int index n%base;return String…...

前端网页开发学习(HTML+CSS+JS)有这一篇就够!

目录 HTML教程 ▐ 概述 ▐ 基础语法 ▐ 文本标签 ▐ 列表标签 ▐ 表格标签 ▐ 表单标签 CSS教程 ▐ 概述 ▐ 基础语法 ▐ 选择器 ▐ 修饰文本 ▐ 修饰背景 ▐ 透明度 ▐ 伪类 ▐ 盒子模型 ▐ 浮动 ▐ 定位 JavaScript教程 ▐ 概述 ▐ 基础语法 ▐ 函数 …...

CSS遮罩:mask

CSS属性 mask 允许使用者通过遮罩或者裁切特定区域的图片的方式来隐藏一个元素的部分或者全部可见区域。 // 一般用位图图片做遮罩 mask: url(~/assets/images/mask.png); mask-size: 100% 100%;// 使用 SVG 图形中的形状来做遮罩 mask: url(~/assets/images/mask.svg#star);…...

Swift闭包的本质

1 闭包的本质其实是一个引用类型&#xff1a;存储在堆空间上&#xff0c;由堆分配空间&#xff0c;且生命周期由ARC&#xff08;自动引用计数机制&#xff09;管理 2 捕获值&#xff1a;闭包会捕获上下文使用到的变量&#xff08;引用类型会保持引用关系&#xff09;&#xff…...

时代变迁对传统机器人等方向课程的巨大撕裂

2020年之后&#xff0c;全面转型新质课程规划&#xff0c;传统课程规划全部转为经验。 农耕-代表性生产关系-封建分配制度主要生产力-人力工业-代表性生产关系-资本分配制度工业分为机械时代&#xff0c;电气时代&#xff0c;信息时代&#xff1b;主要生产力-人力转为人脑&…...

【算法设计与分析实训】第1关:求序列的最大字段和

务描述 本关任务&#xff1a;编写用动态规划解决最大字段和问题。 相关知识 为了完成本关任务&#xff0c;你需要掌握&#xff1a;动态规划。 编程要求 给定由n个整数&#xff08;可能为负数&#xff09;组成的序列&#xff1a;a1,a2,……,an, 求该序列的最大子段和。当所有整…...

【澜舟科技-注册/登录安全分析报告】

前言 由于网站注册入口容易被机器执行自动化程序攻击&#xff0c;存在如下风险&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露&#xff0c;不符合国家等级保护的要求。短信盗刷带来的拒绝服务风险 &#xff0c;造成用户无法登陆、注册&#xff0c;大量收到垃圾短信的…...

【读书笔记-《网络是怎样连接的》- 7】Chapter3_2 路由器

本篇继续介绍路由器及其转发过程。 1 路由器内部结构 路由器内部结构图如图所示。 即主要包含左侧的包转发模块和右侧的端口模块。转发模块负责查找包的发送目的地&#xff0c;端口模块完成包的发送。通过安装不同的硬件&#xff0c;转发模块不仅可以支持以太网&#xff0c;也…...

Android Activity 基础接口知识和常见问题

Activity 知识点及问题点 接口onMultiWindowModeChangedonConfigurationChanged 常见问题Android解决点击桌面图标&#xff0c;就重新启动应用程序问题 接口 onMultiWindowModeChanged 定义 onMultiWindowModeChanged是Android中Activity类的一个回调方法。它会在活动&#xf…...

利用python 检测当前目录下的所有PDF 并转化为png 格式

以下是一个完整的 Python 脚本&#xff0c;用于检测当前目录下的所有 PDF 文件并将每一页转换为 PNG 格式&#xff1a; import os from pdf2image import convert_from_path# 设置输出图像的 DPI&#xff08;分辨率&#xff09; DPI 300# 获取当前目录 current_directory os…...

解决 Spring Boot 中 `Ambiguous mapping. Cannot map ‘xxxController‘ method` 错误

前言 在使用 Spring Boot 开发 Web 应用时&#xff0c;经常会遇到各种各样的错误。其中一种常见的错误是 Ambiguous mapping. Cannot map ‘testController‘ method。本文将详细介绍这个错误的原因及解决方法&#xff0c;帮助开发者快速定位并解决问题。 错误解释 这个错误…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

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

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

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...