代码随想录算法训练营第 53 天 |卡码网110.字符串接龙 卡码网105.有向图的完全可达性 卡码网106.岛屿的周长

本文主要是介绍代码随想录算法训练营第 53 天 |卡码网110.字符串接龙 卡码网105.有向图的完全可达性 卡码网106.岛屿的周长,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

代码随想录算法训练营

Day53 代码随想录算法训练营第 53 天 |卡码网110.字符串接龙 卡码网105.有向图的完全可达性 卡码网106.岛屿的周长


目录

  • 代码随想录算法训练营
  • 前言
    • 卡码网110.字符串接龙
    • 卡码网105.有向图的完全可达性
    • 卡码网106.岛屿的周长
  • 一、卡码网110.字符串接龙
    • 1.题目链接
    • 2.思路
    • 3.题解
  • 二、105.有向图的完全可达性
    • 1.题目链接
    • 2.思路
    • 3.题解
  • 三、卡码网106.岛屿的周长
    • 1.题目链接
    • 2.思路
    • 3.题解


前言

卡码网110.字符串接龙

讲解文档

卡码网105.有向图的完全可达性

讲解文档

卡码网106.岛屿的周长

讲解文档


一、卡码网110.字符串接龙

1.题目链接

卡码网110.字符串接龙

2.思路

(1)转换成最短路问题
在这里插入图片描述思路示意图

(2)重点要解决两个问题:
图中的线是如何连在一起的
起点和终点的最短路径长度
(3)起点和终点的最短路径长度:广度优先搜索找到的就是最短路
(4)图中的线是如何连在一起的:
相差一个字符的字符串连线,所以将之前遍历上下左右换成遍历每个字符再遍历26个字母获取新的字符串

注意:
1)用visit映射保存到每个字符串的最短路径长度,也起到防止重复的作用
2)用集合存放字符串,便于看新的字符串是否在是strlist中的
3)在制作新的字符串的时候,在遍历字符的层中string new_word=cur;防止破坏原来的字符串

3.题解

#include <bits/stdc++.h>
using namespace std;
int main()
{int n;cin>>n;string begin;string end;cin>>begin>>end;unordered_set<string>strlist;for(int i=0;i<n;i++){string s1;cin>>s1;strlist.insert(s1);}unordered_map<string,int>visit;queue <string> q;q.push(begin);visit[begin]=1;while(!q.empty()){string cur=q.front();q.pop();int path=visit[cur];for(int j=0;j<cur.size();j++){string new_word=cur;for(int k=0;k<26;k++){new_word[j]=k+'a';if(new_word==end){cout<<path+1;return 0;}else{if(strlist.count(new_word) >0&& visit.count(new_word) ==0){q.push(new_word);visit[new_word]=path+1;}}}}}cout<<0;return 0;
}

二、105.有向图的完全可达性

1.题目链接

105.有向图的完全可达性

2.思路

(1)存图:用数组
graph[i][j]=1指的是i->j是通路
(2)用visit标记点是否走过
最后遍历visit,如果visit里面有没走过的点,有向图不具有完全可达性,输出-1
(3)深度优先搜索遍历所有点
1)当前点index
2)遍历剩下的点
3)如果是index,是不能从index直接走过去的,已经走过的,跳过
4)标记,进行递归

3.题解

#include <bits/stdc++.h>
using namespace std;
int n;
void dfs(int index,vector<vector<int>> &graph,vector<int>&visit)
{for(int i=1;i<=n;i++){if(i==index||graph[index][i]==0||visit[i])continue;visit[i]=1;dfs(i,graph,visit);}
}
int main()
{int k;cin>>n>>k;std::vector<vector<int>> graph(n+1,vector<int>(n+1,0)) ;int s;int t;for(int i=0;i<k;i++){cin>>s>>t;graph[s][t]=1;}vector<int>visit(n+1,0);visit[1]=1;dfs(1,graph,visit);for(int i=1;i<n+1;i++){if(visit[i]==0){cout<<-1;return 0;}}cout<<1;return 0;
}

三、卡码网106.岛屿的周长

1.题目链接

卡码网106.岛屿的周长

2.思路

(1)思路:遇到岛屿则计算其上下左右的空格情况,如果空格为海洋或出界(界外为海),则说明是一条边
(2)遍历图,遇到第一个陆地点即为岛屿,对岛屿进行深度优先搜索,之后结束遍历
(3)深度优先搜索
1)边界:

  • 已经走过—返回
  • 为海洋–计数,返回
    2)当前点是没有走过的陆地:
  • 遍历上下左右
  • 如果新的点超出边界,那么说明是海洋,结果+1,continue
  • visit记录
  • 递归

3.题解

#include <bits/stdc++.h>
using namespace std;
int n;
int m;
int res=0;
int direction[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y,vector<vector<int>> &graph,vector<vector<int>>&visit)
{if(visit[x][y])return;if(graph[x][y]==0){res++;return;}else{visit[x][y]=1;for(int i=0;i<4;i++){int newx=x+direction[i][0];int newy=y+direction[i][1];if(newx<0||newy<0||newx>=n||newy>=m){res++;continue;}dfs(newx,newy,graph,visit);}}
}
int main()
{cin>>n>>m;vector<vector<int>> graph(n+1,vector<int>(m+1,0)) ;vector<vector<int>> visit(n+1,vector<int>(m+1,0)) ;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>graph[i][j];}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(graph[i][j]){dfs(i,j,graph,visit);break;}}}cout<<res;return 0;
}

这篇关于代码随想录算法训练营第 53 天 |卡码网110.字符串接龙 卡码网105.有向图的完全可达性 卡码网106.岛屿的周长的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1103185

相关文章

Java实现将HTML文件与字符串转换为图片

《Java实现将HTML文件与字符串转换为图片》在Java开发中,我们经常会遇到将HTML内容转换为图片的需求,本文小编就来和大家详细讲讲如何使用FreeSpire.DocforJava库来实现这一功... 目录前言核心实现:html 转图片完整代码场景 1:转换本地 HTML 文件为图片场景 2:转换 H

Python实现精确小数计算的完全指南

《Python实现精确小数计算的完全指南》在金融计算、科学实验和工程领域,浮点数精度问题一直是开发者面临的重大挑战,本文将深入解析Python精确小数计算技术体系,感兴趣的小伙伴可以了解一下... 目录引言:小数精度问题的核心挑战一、浮点数精度问题分析1.1 浮点数精度陷阱1.2 浮点数误差来源二、基础解决

从入门到精通详解Python虚拟环境完全指南

《从入门到精通详解Python虚拟环境完全指南》Python虚拟环境是一个独立的Python运行环境,它允许你为不同的项目创建隔离的Python环境,下面小编就来和大家详细介绍一下吧... 目录什么是python虚拟环境一、使用venv创建和管理虚拟环境1.1 创建虚拟环境1.2 激活虚拟环境1.3 验证虚

从基础到高级详解Python数值格式化输出的完全指南

《从基础到高级详解Python数值格式化输出的完全指南》在数据分析、金融计算和科学报告领域,数值格式化是提升可读性和专业性的关键技术,本文将深入解析Python中数值格式化输出的相关方法,感兴趣的小伙... 目录引言:数值格式化的核心价值一、基础格式化方法1.1 三种核心格式化方式对比1.2 基础格式化示例

Redis实现高效内存管理的示例代码

《Redis实现高效内存管理的示例代码》Redis内存管理是其核心功能之一,为了高效地利用内存,Redis采用了多种技术和策略,如优化的数据结构、内存分配策略、内存回收、数据压缩等,下面就来详细的介绍... 目录1. 内存分配策略jemalloc 的使用2. 数据压缩和编码ziplist示例代码3. 优化的

Python ORM神器之SQLAlchemy基本使用完全指南

《PythonORM神器之SQLAlchemy基本使用完全指南》SQLAlchemy是Python主流ORM框架,通过对象化方式简化数据库操作,支持多数据库,提供引擎、会话、模型等核心组件,实现事务... 目录一、什么是SQLAlchemy?二、安装SQLAlchemy三、核心概念1. Engine(引擎)

Python 基于http.server模块实现简单http服务的代码举例

《Python基于http.server模块实现简单http服务的代码举例》Pythonhttp.server模块通过继承BaseHTTPRequestHandler处理HTTP请求,使用Threa... 目录测试环境代码实现相关介绍模块简介类及相关函数简介参考链接测试环境win11专业版python

Python从Word文档中提取图片并生成PPT的操作代码

《Python从Word文档中提取图片并生成PPT的操作代码》在日常办公场景中,我们经常需要从Word文档中提取图片,并将这些图片整理到PowerPoint幻灯片中,手动完成这一任务既耗时又容易出错,... 目录引言背景与需求解决方案概述代码解析代码核心逻辑说明总结引言在日常办公场景中,我们经常需要从 W

使用Spring Cache本地缓存示例代码

《使用SpringCache本地缓存示例代码》缓存是提高应用程序性能的重要手段,通过将频繁访问的数据存储在内存中,可以减少数据库访问次数,从而加速数据读取,:本文主要介绍使用SpringCac... 目录一、Spring Cache简介核心特点:二、基础配置1. 添加依赖2. 启用缓存3. 缓存配置方案方案

MySQL的配置文件详解及实例代码

《MySQL的配置文件详解及实例代码》MySQL的配置文件是服务器运行的重要组成部分,用于设置服务器操作的各种参数,下面:本文主要介绍MySQL配置文件的相关资料,文中通过代码介绍的非常详细,需要... 目录前言一、配置文件结构1.[mysqld]2.[client]3.[mysql]4.[mysqldum