代码随想录算法训练营第 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

相关文章

详解MySQL中JSON数据类型用法及与传统JSON字符串对比

《详解MySQL中JSON数据类型用法及与传统JSON字符串对比》MySQL从5.7版本开始引入了JSON数据类型,专门用于存储JSON格式的数据,本文将为大家简单介绍一下MySQL中JSON数据类型... 目录前言基本用法jsON数据类型 vs 传统JSON字符串1. 存储方式2. 查询方式对比3. 索引

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2