算法训练营第六十七天 | 卡码网110 字符串接龙、卡码网105 有向图的完全可达性、卡码网106 岛屿的周长
卡码网110 字符串接龙
这题一开始用的邻接表+dfs,不幸超时
#include <iostream>
#include <list>
#include <string>
#include <vector>
using namespace std;int minLen = 501;bool count(string a, string b) {int num = 0;for (int i = 0; i < a.length() && i < b. length(); i++) {if (a[i] != b[i]) {num++;if (num > 1) return false;}}return true;
}int dfs(string* s, vector<list<int>>& l, int* visited, int len, int index, int n) {if (index == n + 1) {if (minLen > len) minLen = len;return len;}int result = 501;for (auto it = l[index].begin(); it != l[index].end(); it++) {if (!visited[*it]) {visited[*it] = 1;result = dfs(s, l, visited, len+1, *it, n);visited[*it] = 0;}}return min(minLen, result);
}int main() {int n;cin >> n;string s[n+2];cin >> s[0] >> s[n+1];for (int i = 1; i <= n; i++) {cin >> s[i];}vector<list<int>> l(n+1);for (int i = 0; i <= n; i++) {for (int j = 1; j <= n+1; j++) {if (j != i) {if (count(s[i], s[j])) l[i].push_back(j);}}}int visited[n+2];for (int i = 0; i < n+2; i++) visited[i] = 0;visited[0] = 1;minLen = dfs(s, l, visited, 1, 0, n);if (minLen == 501) cout << 0 << endl;else cout << minLen << endl;
}
题解中用的广搜,可以去看下,说是最短路径用深搜比较麻烦,要确定哪条最短,我确定出来了,但还是超时了。广搜只要搜到就一定是最短路径了,先放这。
卡码网105 有向图的完全可达性
这题就比较轻松了,深搜也不需要完全回溯,只需要遍历记录即可
代码如下:
#include <iostream>
#include <list>
#include <vector>
#include <queue>
using namespace std;void bfs(vector<list<int>>& l, vector<int>& visited, int index) {queue<int> myque;myque.push(index);while (!myque.empty()) {for (int i : l[index]) {if (!visited[i]) {visited[i] = 1;myque.push(i);}}myque.pop();}
}int main() {int n, k;cin >> n >> k;int s, t;vector<list<int>> l(n);for (int i = 0; i < k; i++) {cin >> s >> t;l[s-1].push_back(t-1);}vector<int> visited(n, 0);visited[0] = 1;bfs(l, visited, 0);for (int i = 0; i < n; i++) {if (!visited[i]) {cout << -1 << endl;return 0;}}cout << 1 << endl;return 0;
}
卡码网106 岛屿的周长
这题很简单,没用到dfs和bfs,简单填充边界后判断周围是否触碰边界后计数即可。
代码如下:
#include <iostream>using namespace std;int main() {int n, m;cin >> n >> m;int g[n][m];int sum = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> g[n][m];}}for (int i = 1; i < n - 1; i++) {for (int j = 1; j < m - 1; j++) {if (g[i][j] == 1) {if (g[i-1][j] == 0) sum++;if (g[i][j-1] == 0) sum++;if (g[i+1][j] == 0) sum++;if (g[i][j+1] == 0) sum++;}}}cout << sum << endl;
}
相关文章:
算法训练营第六十七天 | 卡码网110 字符串接龙、卡码网105 有向图的完全可达性、卡码网106 岛屿的周长
卡码网110 字符串接龙 这题一开始用的邻接表dfs,不幸超时 #include <iostream> #include <list> #include <string> #include <vector> using namespace std;int minLen 501;bool count(string a, string b) {int num 0;for (int i 0; …...
搭建 MySQL MHA
搭建 MySQL MHA 搭建 MySQL MHA实验拓扑图实验环境实验思路MHA架构故障模拟 实验部署数据库安装主从复制部署时间同步主服务器配置从服务器配置创建链接 MHA搭建安装依赖的环境安装 node 组件安装 manager 组件配置无密码认证在 manager 节点上配置 MHA管理 mysql 节点服务器创…...
python中的线程与进程
一、线程与进程 在计算机科学中,理解线程和进程的区别是重要的基础知识。这些概念对于多任务操作和并发编程尤为关键。下面将详细介绍线程与进程的区别、特点和各自的使用场景。 1.1 进程(Process) 进程是操作系统分配资源的基本单位。每个进…...
网络安全筑基篇——反序列化漏洞
目录 序列化是什么? 反序列化又是什么? 反序列化漏洞的危害 代码样例 常见的魔术方法 修复方式有哪些? 常见的反序列化漏洞 Shiro反序列化漏洞 Fastjson反序列化漏洞 序列化是什么? 将实例化对象转换成字节流的过程 反序…...
帝国cms定时审核并更新的方法
比如你网站采集了成千上万篇文章,不可能一下子全部放出来的,所以为了模拟人工发布,那么就需要定时审核发布文章内容,本文内容核心解决了更加个性化的逼真模拟人工更新网站内容。 第一:首先要满足你的表中有未审核的数据…...
一个简单好用安全的开源交互审计系统,支持SSH,Telnet,Kubernetes协议
前言 在当今的企业网络环境中,远程访问和交互审计成为了保障网络安-全的重要组成部分。然而,现有的解-决方案往往存在一些痛点,如复杂的配置、有限的协议支持、以及审计功能的不足。这些问题不仅增加了IT管理员的负担,也为企业的…...
使用Spring Boot和WebSocket实现实时通信
使用Spring Boot和WebSocket实现实时通信 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!今天我们将探讨如何在Spring Boot应用中使用WebSocket实现实时通信&am…...
【Vue】集成富文本编辑器
这文章使用的是wangeditor插件,官网地址:wangEditor,这个比较简单 安装 npm i wangeditor --save 使用 <div id"editor"></div>import E from "wangeditor"const editor new E("#editor") e…...
【论文阅读】--Popup-Plots: Warping Temporal Data Visualization
弹出图:扭曲时态数据可视化 摘要1 引言2 相关工作3 弹出图3.1 椭球模型3.1.1 水平轨迹3.1.2 垂直轨迹3.1.3 组合轨迹 3.2 视觉映射与交互 4 实施5 结果6 评估7 讨论8 结论和未来工作致谢参考文献 期刊: IEEE Trans. Vis. Comput. Graph.(发表日期: 2019&…...
重建大师引擎数0,本地引擎设置改不了,空三在跑,这样是正常的吗?
答:任务目录和引擎监控目录并没有按照网络集群设置,需要调整为网络路径。 重建大师是一款专为超大规模实景三维数据生产而设计的集群并行处理软件,输入倾斜照片,激光点云,POS信息及像控点,输出高精度彩色网…...
APM教程-SkyWalking安装和配置
SkyWalking简介 APM (Application Performance Management) 即应用性能管理,属于IT运维管理(ITOM)范畴。主要是针对企业 关键业务的IT应用性能和用户体验的监测、优化,提高企业IT应用的可靠性和质量,保证用户得到良好的服务&#…...
斯坦福大学 AI 研究部门推出的“7 周人工智能学习计划”
①AI Python 基础,包括计算机原理、语法、判断语句等; ②AI Python 进阶,涉及 Linux 命令、多任务编程等; ③机器学习,涵盖算法、数据结构等; ④计算机视觉与图像处理,包含图像分类、目标检测…...
World of Warcraft [CLASSIC] plugin lua
World of Warcraft [CLASSIC] plugin lua 魔兽世界lua脚本插件 World of Warcraft API - Wowpedia - Your wiki guide to the World of Warcraft D:\World of Warcraft\_classic_\Interface\AddOns zwf.lua function CountdownFunc()CountdownFrame CreateFrame("Fram…...
背靠广汽、小马智行,如祺出行打得过滴滴和百度吗?
©自象限原创 作者丨艾AA 编辑丨薛黎 北京时间6月14日凌晨,在特斯拉股东大会上,马斯克阐述了对Robotaxi(自动驾驶出租车)商业模式的构想——特斯拉不仅会运营自己的无人驾驶出租车车队,还可以让特斯拉车主们的爱…...
CCSP自考攻略+经验总结
备考攻略 备考攻略准备阶段通读阶段精度阶段总复习阶段刷题阶段命运审判 写到最后 备考攻略 趁着对ssp知识点的理解还在,开始ccsp的考证之路,文章结构还是按照cissp备考篇的结构梳理。本次备考和cissp的离职在家备考不同,ccsp是在职利用非工…...
面试突击:ArrayList源码详解
本文已收录于:https://github.com/danmuking/all-in-one(持续更新) 前言 哈喽,大家好,我是 DanMu。ArrayList 是我们日常开发中不可避免要使用到的一个类,并且在面试过程中也是一个非常高频的知识点&#…...
力扣每日一题:2734. 执行子串操作后的字典序最小字符串
题目链接 脑子比较笨,分三种情况考虑: 以a开头。xxa,a在中间。 对于情况2还有两种可能: 1. 全是a,最后一个元素需要替换成z,因为必须执行一次操作。 2. aaaxxa,中间有一段非a,将这…...
C++11中std::thread的使用
C11 引入了 std::thread,它是用于创建和管理线程的标准库类。以下是详细的讲解,包括如何使用 std::thread 进行线程创建、管理和参数传递等操作。 1. 包含必要的头文件 在使用 std::thread 前,需要包含 <thread> 头文件: …...
酷瓜云课堂(内网版)v1.1.5 发布,局域网在线学习+考试系统
更新内容 更新layui-v2.9.10更新docker国内镜像地址增加导入镜像构建容器的方式教师不批阅非首次考试试卷轮播图增加专栏类型目标链接增加课程能否发布检查去除初始化kindeditor语言文件去除选择题EF选项优化富文本内容显示样式优化内容图片点击放大监听优化试题题干答案等图片…...
大数据之Hadoop部署
文章目录 服务器规划服务器环境准备1. 网络测试2. 安装额外软件包3. 安装基础工具4. 关闭防火墙5. 创建用户并配置权限6. 创建目录并设置权限7. 卸载JDK8. 修改主机名9. 配置hosts文件10. 重启服务器 配置免密登录安装Java安装Hadoop1. Hadoop部署2. 配置Hadoop3. 格式化Hadoop…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙
Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...
Python常用模块:time、os、shutil与flask初探
一、Flask初探 & PyCharm终端配置 目的: 快速搭建小型Web服务器以提供数据。 工具: 第三方Web框架 Flask (需 pip install flask 安装)。 安装 Flask: 建议: 使用 PyCharm 内置的 Terminal (模拟命令行) 进行安装,避免频繁切换。 PyCharm Terminal 配置建议: 打开 Py…...
WEB3全栈开发——面试专业技能点P4数据库
一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库,基于 mysql 库改进而来,具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点: 支持 Promise / async-await…...
数据库正常,但后端收不到数据原因及解决
从代码和日志来看,后端SQL查询确实返回了数据,但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离,并且ai辅助开发的时候,很容易出现前后端变量名不一致情况,还不报错,只是单…...
