当前位置: 首页 > news >正文

代码随想录算法训练营第五十三天|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;
}

学习反思

实现了一个无向图的深度优先搜索,用于判断图是否是连通图。

代码的主要逻辑如下:

  1. 首先定义了一个Graph结构体,包含了邻接矩阵表示的图的边和节点信息。
  2. initGraph函数初始化了图的边和节点信息。
  3. addEdge函数用于向图中添加一条边。
  4. dfs函数实现了深度优先搜索算法,其中使用了递归的方式进行搜索,如果找到一个节点未被访问过,则递归调用dfs继续搜索。
  5. 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学算法&#xff0c;本系列博客仅做个人记录&#xff0c;建议大家都去看carl本人的博客&#xff0c;写的真的很好的&#xff01; 代码随想录 LeetCode&#xff1a;203.移除链表元素 给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所有满足 Node.…...

知识见闻 - 数学: 均方根 Root Mean Square

What is Root Mean Square (RMS)? 在统计学上&#xff0c;均方根&#xff08;RMS&#xff09;是均方的平方根&#xff0c;而均方是一组数值的平方的算术平均数。均方根也称为二次均值&#xff0c;是指数为 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位置以保护隐私、玩游戏或访问受地理限制的内容&#xff1f;接下来我将向你展示如何使用 MagFone Location Changer 更改手机GPS 位置&#xff01;无论是在玩Pokmon GO游戏、发布社媒贴子&#xff0c;这种方法都快速、简单且有效。 第一步&#xff1a;下…...

HarmonyOS(57) UI性能优化

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

Mysql的加锁情况详解

最近在复习mysql的知识点&#xff0c;像索引、优化、主从复制这些很容易就激活了脑海里尘封的知识&#xff0c;但是在mysql锁的这一块真的是忘的一干二净&#xff0c;一点映像都没有&#xff0c;感觉也有点太难理解了&#xff0c;但是还是想把这块给啃下来&#xff0c;于是想通…...

hive3.1.2编译spark3安装包

此安装包是《去破解站长》在公司真实生产环境所使用的安装包。 引言&#xff1a;Hive引擎包括&#xff1a;默认MR、tez、sparkDownload:www.qupojie.com 1、Hive on Spark 1、Hive onSpark&#xff1a;Hive既作为存储元数据又负责SQL的解析优化&#xff0c;语法是HQL语法&…...

网络安全,文明上网(1)享科技,提素养

前言 在这个信息化飞速发展的时代&#xff0c;科技的快速进步极大地丰富了我们的生活&#xff0c;并为我们提供了无限的可能性。然而&#xff0c;随着网络世界的不断扩张&#xff0c;增强我们的网络素养成为了一个迫切需要解决的问题。 与科技同行&#xff0c;培育网络素养 技术…...

ESP32 烧录问题

ESP32 烧录问题 1.无法连接 Connecting......................................A fatal error occurred: Failed to connect to ESP32: No serial data received.这个表示通过串口连接esp32失败&#xff0c;可能存在多种原因&#xff0c;比如串口选择错误。 所选串口不是连接…...

CnosDB 实时流式计算:优化时序数据处理与降采样解决方案

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

ApiChain 从迭代测试用例到项目回归测试 核心使用教程

项目地址&#xff1a;ApiChain 项目主页 环境变量 环境变量是在特定的开发环境&#xff08;开发、测试、uat等&#xff09;下&#xff0c;保存的一份数据集&#xff0c;环境变量是发送网络请求或者执行单测的一个重要数据源。环境变量根据作用范围可以分为全局环境变量、项目…...

数据集-目标检测系列- 花卉 玫瑰 检测数据集 rose >> DataBall

数据集-目标检测系列- 花卉 玫瑰 检测数据集 rose >> DataBall DataBall 助力快速掌握数据集的信息和使用方式&#xff0c;会员享有 百种数据集&#xff0c;持续增加中。 贵在坚持&#xff01; 数据样例项目地址&#xff1a; * 相关项目 1&#xff09;数据集可视化项…...

django从入门到实战(四)——模型与数据库

1. 模型的定义与数据迁移 1.1 模型的定义 在 Django 中&#xff0c;模型是一个 Python 类&#xff0c;用于定义数据库中的数据结构。每个模型类对应数据库中的一张表&#xff0c;类的属性对应表中的字段。 示例&#xff1a; from django.db import modelsclass Blog(models…...

LeetCode:1008. 前序遍历构造二叉搜索树

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

gdb - 调试工具 - 入门 (一)

GDB&#xff08;GNU Debugger&#xff09;是GNU项目调试器的缩写&#xff0c;它是Linux下一个强大的C/C&#xff08;以及其他语言如Fortran&#xff09;程序调试工具。以下是对GDB的详细解释&#xff1a; 一、GDB的功能 GDB允许开发者对程序执行进行深入控制&#xff0c;可以…...

Swift内存访问冲突

内存的访问&#xff0c;发生在给变量赋值的时候&#xff0c;或者传递值&#xff08;给函数&#xff09;的时候&#xff0c;例如 var one 1//向one的内存区域发起一次写的操作 print("\(one)")//向one的内存区域发起一次读的操作 在 Swift 里&#xff0c;有很多修改…...

深入理解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电机驱动模块使用指南

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

Paper -- 洪水深度估计 -- 利用图像处理和深度神经网络绘制街道照片中的洪水深度图

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

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_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

华为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章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

vue3+vite项目中使用.env文件环境变量方法

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

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 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…...