当前位置: 首页 > 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;帮助开发者快速定位并解决问题。 错误解释 这个错误…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

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

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

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

sshd代码修改banner

sshd服务连接之后会收到字符串&#xff1a; SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢&#xff1f; 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头&#xff0c…...