代码随想录算法训练营第五十三天|Day53 图论
字符串接龙
https://www.programmercarl.com/kamacoder/0110.%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%8E%A5%E9%BE%99.html
思路
#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX 1000 // 假设最大字符串数
#define WORD_LENGTH 100 // 假设每个单词的最大长度typedef struct {char words[MAX][WORD_LENGTH]; // 保存字符串int size; // 当前字符串数量
} StringSet;typedef struct {char words[MAX][WORD_LENGTH]; // 保存字符串int length[MAX]; // 保存路径长度int front, rear; // 队列头尾指针
} Queue;void initStringSet(StringSet *set) {set->size = 0;
}void addString(StringSet *set, const char *word) {strcpy(set->words[set->size++], word);
}int contains(StringSet *set, const char *word) {for (int i = 0; i < set->size; i++) {if (strcmp(set->words[i], word) == 0) {return 1; // 存在}}return 0; // 不存在
}void initQueue(Queue *q) {q->front = 0;q->rear = 0;
}void enqueue(Queue *q, const char *word, int pathLength) {strcpy(q->words[q->rear], word);q->length[q->rear] = pathLength;q->rear++;
}void dequeue(Queue *q, char *word, int *pathLength) {strcpy(word, q->words[q->front]);*pathLength = q->length[q->front];q->front++;
}int isEmpty(Queue *q) {return q->front == q->rear;
}int main() {int n;scanf("%d", &n);char beginStr[WORD_LENGTH], endStr[WORD_LENGTH];scanf("%s %s", beginStr, endStr);StringSet strSet;initStringSet(&strSet);for (int i = 0; i < n; i++) {char str[WORD_LENGTH];scanf("%s", str);addString(&strSet, str);}Queue que;initQueue(&que);enqueue(&que, beginStr, 1); while (!isEmpty(&que)) {char word[WORD_LENGTH];int pathLength;dequeue(&que, word, &pathLength);for (int i = 0; i < strlen(word); i++) {char newWord[WORD_LENGTH];strcpy(newWord, word); for (char j = 'a'; j <= 'z'; j++) {newWord[i] = j; if (strcmp(newWord, endStr) == 0) {printf("%d\n", pathLength + 1);return 0;}if (contains(&strSet, newWord)) {enqueue(&que, newWord, pathLength + 1);}}}}printf("0\n");return 0;
}
学习反思
代码是一个可以计算字符串变换路径长度的程序,根据输入的起始字符串和目标字符串,通过变换每个字符的方式,计算出从起始字符串到目标字符串的最短变换路径长度。代码中使用了两个数据结构StringSet和Queue来实现功能。StringSet用于保存输入的字符串集合,Queue用于保存待处理的字符串和路径长度。代码的主要逻辑是通过BFS(广度优先搜索)算法遍历所有可能的变换路径。代码中使用了一些函数来实现各种操作,例如initStringSet用于初始化StringSet,addString用于向StringSet中添加字符串,contains用于判断StringSet中是否包含某个字符串。类似地,initQueue用于初始化Queue,enqueue用于入队,dequeue用于出队,isEmpty用于判断Queue是否为空。在主函数中,首先读取输入的字符串数量n和起始字符串和目标字符串beginStr、endStr。然后利用循环读取n个字符串,并将它们添加到StringSet中。接下来,初始化Queue,并将起始字符串和路径长度1入队。然后进入循环,直到队列为空,从队列中取出一个字符串和路径长度,然后对该字符串的每个字符进行变换,生成新的字符串,判断是否与目标字符串相等,如果相等则输出路径长度并结束程序。如果不相等,则判断新生成的字符串是否在StringSet中存在,如果存在则将其入队,并增加路径长度。循环结束后,如果没有找到路径,则输出0。
有向图的完全可达性
https://www.programmercarl.com/kamacoder/0105.%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E5%AE%8C%E5%85%A8%E5%8F%AF%E8%BE%BE%E6%80%A7.html
思路
#include <stdio.h>
#include <stdlib.h>#define MAX_NODES 101 // 节点编号范围 [1, N]
#define MAX_EDGES 2000 // 最大边数typedef struct {int edges[MAX_NODES][MAX_NODES]; // 邻接矩阵表示图int visited[MAX_NODES]; // 访问标记int n; // 节点数
} Graph;void initGraph(Graph *g, int n) {g->n = n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {g->edges[i][j] = 0; }g->visited[i] = 0; }
}
void addEdge(Graph *g, int s, int t) {g->edges[s][t] = 1;
}
void dfs(Graph *g, int v) {g->visited[v] = 1; for (int i = 1; i <= g->n; i++) {if (g->edges[v][i] == 1 && !g->visited[i]) { dfs(g, i); }}
}int main() {int n, k; scanf("%d %d", &n, &k);Graph g;initGraph(&g, n);for (int i = 0; i < k; i++) {int s, t;scanf("%d %d", &s, &t);addEdge(&g, s, t); }dfs(&g, 1);for (int i = 1; i <= n; i++) {if (!g.visited[i]) { printf("-1\n"); return 0;}}printf("1\n"); return 0;
}
学习反思
实现了一个无向图的深度优先搜索,用于判断图是否是连通图。
代码的主要逻辑如下:
- 首先定义了一个Graph结构体,包含了邻接矩阵表示的图的边和节点信息。
- initGraph函数初始化了图的边和节点信息。
- addEdge函数用于向图中添加一条边。
- dfs函数实现了深度优先搜索算法,其中使用了递归的方式进行搜索,如果找到一个节点未被访问过,则递归调用dfs继续搜索。
- main函数中首先读取输入的节点数和边数,然后根据输入的边信息构建图。接着调用dfs函数进行深度优先搜索,并根据搜索结果判断图是否是连通图。
岛屿的周长
https://www.programmercarl.com/kamacoder/0106.%E5%B2%9B%E5%B1%BF%E7%9A%84%E5%91%A8%E9%95%BF.html
思路
#include <stdio.h>
#define MAX_SIZE 50
int main() {int n, m;int matrix[MAX_SIZE][MAX_SIZE];int perimeter = 0;scanf("%d %d", &n, &m);for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {scanf("%d", &matrix[i][j]);}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (matrix[i][j] == 1) {// 上if (i == 0 || matrix[i - 1][j] == 0) perimeter++;// 下if (i == n - 1 || matrix[i + 1][j] == 0) perimeter++;// 左if (j == 0 || matrix[i][j - 1] == 0) perimeter++;// 右if (j == m - 1 || matrix[i][j + 1] == 0) perimeter++;}}}printf("%d\n", perimeter); return 0;
}
学习反思
用来计算一个由0和1组成的矩阵的周长的。输入包括两个整数n和m,表示矩阵的行数和列数,然后根据输入的n和m读取矩阵的元素。如果矩阵中的某个元素为1,则计算该元素所在位置的周围四个方向的元素,如果是0或者超出矩阵边界,则周长+1。最后输出计算得到的周长。其中使用了一个宏定义MAX_SIZE来定义矩阵的最大大小,防止数组越界。通过两个循环来依次读取矩阵的元素,并通过四个判断语句来计算周长。代码的主要思路是遍历矩阵的每个元素,如果当前元素是1,则计算周围四个方向的元素,如果是0或者超出边界,则周长+1。最后输出周长。该代码的时间复杂度为O(n*m),其中n和m分别是矩阵的行数和列数。
相关文章:
代码随想录算法训练营第五十三天|Day53 图论
字符串接龙 https://www.programmercarl.com/kamacoder/0110.%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%8E%A5%E9%BE%99.html 思路 #include <stdio.h> #include <stdlib.h> #include <string.h>#define MAX 1000 // 假设最大字符串数 #define WORD_LENGTH 100 // 假…...

LeetCode:203.移除链表元素
跟着carl学算法,本系列博客仅做个人记录,建议大家都去看carl本人的博客,写的真的很好的! 代码随想录 LeetCode:203.移除链表元素 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.…...

知识见闻 - 数学: 均方根 Root Mean Square
What is Root Mean Square (RMS)? 在统计学上,均方根(RMS)是均方的平方根,而均方是一组数值的平方的算术平均数。均方根也称为二次均值,是指数为 2 的广义均值的一种特例。均方根也被定义为基于一个周期内瞬时值的平方…...

机器硬件调优
grub参数 ipv6.disable1 ipv6.autoconf0 intel_pstatedisable nohzoff idlepoll intel_idle.max_cstate0 processor.max_cstate0 mceignore_ce nmi_watchdog0 transparent_hugepagenever pcie_aspm.policyperformance audit0 irqaffinity0 nosoftlockup grub2-mkconfig -o /bo…...

如何更改手机GPS定位
你是否曾想过更改手机GPS位置以保护隐私、玩游戏或访问受地理限制的内容?接下来我将向你展示如何使用 MagFone Location Changer 更改手机GPS 位置!无论是在玩Pokmon GO游戏、发布社媒贴子,这种方法都快速、简单且有效。 第一步:下…...

HarmonyOS(57) UI性能优化
性能优化是APP开发绕不过的话题,那么在HarmonyOS开发过程中怎么进行性能优化呢?今天就来总结下相关知识点。 UI性能优化 1、避免在组件的生命周期内执行高耗时操作2、合理使用ResourceManager3、优先使用Builder方法代替自定义组件4、参考资料 1、避免在…...

Mysql的加锁情况详解
最近在复习mysql的知识点,像索引、优化、主从复制这些很容易就激活了脑海里尘封的知识,但是在mysql锁的这一块真的是忘的一干二净,一点映像都没有,感觉也有点太难理解了,但是还是想把这块给啃下来,于是想通…...
hive3.1.2编译spark3安装包
此安装包是《去破解站长》在公司真实生产环境所使用的安装包。 引言:Hive引擎包括:默认MR、tez、sparkDownload:www.qupojie.com 1、Hive on Spark 1、Hive onSpark:Hive既作为存储元数据又负责SQL的解析优化,语法是HQL语法&…...

网络安全,文明上网(1)享科技,提素养
前言 在这个信息化飞速发展的时代,科技的快速进步极大地丰富了我们的生活,并为我们提供了无限的可能性。然而,随着网络世界的不断扩张,增强我们的网络素养成为了一个迫切需要解决的问题。 与科技同行,培育网络素养 技术…...
ESP32 烧录问题
ESP32 烧录问题 1.无法连接 Connecting......................................A fatal error occurred: Failed to connect to ESP32: No serial data received.这个表示通过串口连接esp32失败,可能存在多种原因,比如串口选择错误。 所选串口不是连接…...

CnosDB 实时流式计算:优化时序数据处理与降采样解决方案
在处理时序数据时,数据写入周期通常与数据采集设备的频率相关,有时每秒钟就需要处理大量的数据点。长时间处理如此多的数据会导致存储问题。一个有效的解决方案是使用流式计算,将原始数据进行降采样。 流式计算在时序数据库中指对实时数据流…...

ApiChain 从迭代测试用例到项目回归测试 核心使用教程
项目地址:ApiChain 项目主页 环境变量 环境变量是在特定的开发环境(开发、测试、uat等)下,保存的一份数据集,环境变量是发送网络请求或者执行单测的一个重要数据源。环境变量根据作用范围可以分为全局环境变量、项目…...

数据集-目标检测系列- 花卉 玫瑰 检测数据集 rose >> DataBall
数据集-目标检测系列- 花卉 玫瑰 检测数据集 rose >> DataBall DataBall 助力快速掌握数据集的信息和使用方式,会员享有 百种数据集,持续增加中。 贵在坚持! 数据样例项目地址: * 相关项目 1)数据集可视化项…...
django从入门到实战(四)——模型与数据库
1. 模型的定义与数据迁移 1.1 模型的定义 在 Django 中,模型是一个 Python 类,用于定义数据库中的数据结构。每个模型类对应数据库中的一张表,类的属性对应表中的字段。 示例: from django.db import modelsclass Blog(models…...

LeetCode:1008. 前序遍历构造二叉搜索树
目录 题目描述: 代码: 第一种: 第二种: 第三种:分治法 题目描述: 给定一个整数数组,它表示BST(即 二叉搜索树 )的 先序遍历 ,构造树并返回其根。 保证 对于给定的测试用例,总是有可能找到具有给定需求的二叉搜索树。 二叉搜索树 是一棵…...

gdb - 调试工具 - 入门 (一)
GDB(GNU Debugger)是GNU项目调试器的缩写,它是Linux下一个强大的C/C(以及其他语言如Fortran)程序调试工具。以下是对GDB的详细解释: 一、GDB的功能 GDB允许开发者对程序执行进行深入控制,可以…...
Swift内存访问冲突
内存的访问,发生在给变量赋值的时候,或者传递值(给函数)的时候,例如 var one 1//向one的内存区域发起一次写的操作 print("\(one)")//向one的内存区域发起一次读的操作 在 Swift 里,有很多修改…...

深入理解Spring(三)
目录 2.1.3、Spring配置非自定义Bean 1)配置Druid数据源交由Spring管理 2)配置Connection交由Spring管理 3)配置日期对象交由Spring管理 4)配置MyBatis的SqlSessionFactory交由Spring管理 2.1.4、Bean实例化的基本流程 1)Bean信息定义对象-BeanDefinition 2)DefaultLi…...

TB6612电机驱动模块使用指南
实物图: 简介:TB6612是一款双路H桥型直流电机驱动模块,可以控制两个直流电机的转速和方向 H桥:(双路H桥就是有两个这个结构) 引脚图:...

Paper -- 洪水深度估计 -- 利用图像处理和深度神经网络绘制街道照片中的洪水深度图
基本信息 论文题目:Flood depth mapping in street photos with image processing and deep neural networks 中文题目: 利用图像处理和深度神经网络绘制街道照片中的洪水深度图 作者及单位: Bahareh Alizadeh Kharazi,美国得克萨斯州立大…...

css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...

华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...

vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
Vue3中的computer和watch
computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...