当前位置: 首页 > 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分别是矩阵的行数和列数。

http://www.lryc.cn/news/489006.html

相关文章:

  • LeetCode:203.移除链表元素
  • 知识见闻 - 数学: 均方根 Root Mean Square
  • 机器硬件调优
  • 如何更改手机GPS定位
  • HarmonyOS(57) UI性能优化
  • Mysql的加锁情况详解
  • hive3.1.2编译spark3安装包
  • 网络安全,文明上网(1)享科技,提素养
  • ESP32 烧录问题
  • CnosDB 实时流式计算:优化时序数据处理与降采样解决方案
  • ApiChain 从迭代测试用例到项目回归测试 核心使用教程
  • 数据集-目标检测系列- 花卉 玫瑰 检测数据集 rose >> DataBall
  • django从入门到实战(四)——模型与数据库
  • LeetCode:1008. 前序遍历构造二叉搜索树
  • gdb - 调试工具 - 入门 (一)
  • Swift内存访问冲突
  • 深入理解Spring(三)
  • TB6612电机驱动模块使用指南
  • Paper -- 洪水深度估计 -- 利用图像处理和深度神经网络绘制街道照片中的洪水深度图
  • 学习C#中的BackgroundWorker 组件
  • 【Vue3新工具】Pinia.js:提升开发效率,更轻量、更高效的状态管理方案!
  • PCB 间接雷击模拟
  • JAVA泛型和顺序表ArrayList
  • Qt桌面应用开发 第六天(鼠标事件 定时器事件 定时器类 事件分发器 事件过滤器)
  • Javascript高级—深入JS模板字符串的高级用法
  • 14. 【.NET 8 实战--孢子记账--从单体到微服务】--简易权限--章节总结
  • vulhub之fastjson
  • 2024年亚太地区数学建模大赛D题-探索量子加速人工智能的前沿领域
  • 卷积神经网络各层介绍
  • Python应用指南:高德拥堵延时指数