lthero

LeetCodeCampsDay62图论part11 Floyd算法与A*算法 97.小明逛公园 题目描述 小明喜欢去公园散步，公园内布置了许多的景点，相互之间通过小路连接，小明希望在观看景点的同时，能够节省体力，走最短的路径。 给定一个公园景点图，图中有 N 个景点（编号为 1 到 N），以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。 小明有 Q 个观景计划，每个计划都有一个起点 start 和一个终点 end，表示他想从景点 start 前往景点 end。由于小明希望节省体力，他想知道每个观景计划中从起点到终点的最短路径长度。 请你帮助小明计算出每个观景计划的最短路径长度。 输入描述 第一行包含两个整数 N, M, 分别表示景点的数量和道路的数量。 接下来的 M 行，每行包含三个整数 u, v, w，表示景点 u 和景点 v 之间有一条长度为 w 的双向道路。 接下里的一行包含一个整数 Q，表示观景计划的数量。 接下来的 Q 行，每行包含两个整数 start, end，表示一个观景计划的起点和终点。 输出描述 对于每个观景计划，输出一行表示从起点到终点的最 ...

LeetCodeCampsDay63总结 训练营让我系统地、由浅入深地学了一遍算法知识并刷题目巩固知识，让我有了不小的进步！虽然以前也学过算法并做过笔记，但通常是不成体系、不系统化、不全面的，往往是看看别人代码，AC后就不管了，缺少了反思与总结的过程。此外，我从未有过如此常态化、持久化的算法学习，这两个月每天写打卡、写博客（我的博客数量从每月写几篇到每月30篇哈哈），让我也有养成了一定的生活规律，而且每一篇博客都见证了我的每一进步！更重要的是，与大家一起打卡，也让我有坚持下去的动力！“一个人可以走得很快，但一群人可以走得更远”！感谢同期的所有朋友，大家都是最棒的！祝各位前程似锦！！！ 任务清单 ● day 1 任务以及具体安排：第一章 数组part01 （6.25） ● day 2 任务以及具体安排：第一章 数组part02 （6.26） ● day 3 任务以及具体安排：第二章 链表part01（6.27） ● day 4 任务以及具体安排：第二章 链表part02（6.28） ● day5 周末休息（6.29） ● day 6 任务以及具体安排：第三章 哈希表part01 ...

LeetCodeCampsDay60图论part10 94.城市间货物运输 I https://kamacoder.com/problempage.php?pid=1152 题目描述 某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。 网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。 请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。如果最低运输成本是一个负数，它表示在遵循最优路径的情况下，运输过程中反而能够实现盈利。 城市 1 到城市 n 之间可能会出现没有路径的情况，同时保证道路网络中不存在任何负权回路。 输入描述 第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。 接下来为 m 行，每行包括三 ...

LeetCodeCampsDay59图论part09 47.参加科学大会（第六期模拟笔试） 题目描述 小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。 小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。 小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。 输入描述 第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。 接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。 输出描述 输出一个整数，代表小明从起点到终点所花费的最小时间。 输入示例 123456789107 91 2 11 3 42 3 22 4 53 4 24 5 32 6 45 7 46 7 9 输出示例 112 提示信息 能够到达的情况： 如下图所示，起始车站为 1 号车站，终点车站为 7 号车站，绿色路线为最短的路线，路线总长度为 ...

LeetCodeCampsDay58图论part08 拓扑排序与dijkstra初识 117.软件构建 题目描述 某个大型软件项目的构建系统拥有 N 个文件，文件编号从 0 到 N - 1，在这些文件中，某些文件依赖于其他文件的内容，这意味着如果文件 A 依赖于文件 B，则必须在处理文件 A 之前处理文件 B （0 <= A, B <= N - 1）。请编写一个算法，用于确定文件处理的顺序。 输入描述 第一行输入两个正整数 N, M。表示 N 个文件之间拥有 M 条依赖关系。 后续 M 行，每行两个正整数 S 和 T，表示 T 文件依赖于 S 文件。 输出描述 输出共一行，如果能处理成功，则输出文件顺序，用空格隔开。 如果不能成功处理（相互依赖），则输出 -1。 输入示例 123455 40 10 21 32 4 输出示例 10 1 2 3 4 提示信息 文件依赖关系如下： 所以，文件处理的顺序除了示例中的顺序，还存在 0 2 4 1 3 0 2 1 3 4 等等合法的顺序。 数据范围： 0 <= N <= 10 ^ 5 1 <= M <= 1 ...

LeetCodeCampsDay57图论part07 最小生成树算法 分别使用Prim算法和Kruscal算法 prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。 53.寻宝（第七期模拟笔试） 题目描述 在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。 不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。 给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。 输入描述 第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。 接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。 输出描述 输出联通所有岛屿的最小路径总距离 输入示例 1234567891011127 111 2 11 3 11 5 22 6 12 4 22 3 23 4 14 5 ...

LeetCodeCampsDay56图论part06 无向图&有向图变成无向树&有向树问题 108.冗余的边 题目描述 有一个图，它是一棵树，他是拥有 n 个节点（节点编号1到n）和 n - 1 条边的连通无环无向图，例如如图： 现在在这棵树上的基础上，添加一条边（依然是n个节点，但有n条边），使这个图变成了有环图，如图： 先请你找出冗余边，删除后，使该图可以重新变成一棵树。 输入描述 第一行包含一个整数 N，表示图的节点个数和边的个数。 后续 N 行，每行包含两个整数 s 和 t，表示图中 s 和 t 之间有一条边。 输出描述 输出一条可以删除的边。如果有多个答案，请删除标准输入中最后出现的那条边。 输入示例 123431 22 31 3 输出示例 11 3 提示信息 图中的 1 2，2 3，1 3 等三条边在删除后都能使原图变为一棵合法的树。但是 1 3 由于是标准输出里最后出现的那条边，所以输出结果为 1 3 数据范围： 1 <= N <= 1000. 并查集思路 如何判断哪条边是多余的？ 对输入的边进行遍历，如果这边的两个节点已经在并查集里 ...

LeetCodeCampsDay55图论part05(并查集) 包含并查集基础与一个基础题目 并查集理论基础 背景 首先要知道并查集可以解决什么问题呢？ 并查集常用来解决连通性问题。 大白话就是当我们需要判断两个元素是否在同一个集合里的时候，我们就要想到用并查集。 并查集主要有两个功能： 将两个元素添加到一个集合中。 判断两个元素在不在同一个集合 接下来围绕并查集的这两个功能来展开讲解。 原理讲解 从代码层面，我们如何将两个元素添加到同一个集合中呢。 此时有录友会想到：可以把他放到同一个数组里或者set 或者 map 中，这样就表述两个元素在同一个集合。 那么问题来了，对这些元素分门别类，可不止一个集合，可能是很多集合，成百上千，那么要定义这么多个数组吗？ 有录友想，那可以定义一个二维数组。 但如果我们要判断两个元素是否在同一个集合里的时候 我们又能怎么办？ 只能把而二维数组都遍历一遍。 而且每当想添加一个元素到某集合的时候，依然需要把把二维数组都遍历一遍，才知道要放在哪个集合里。 这仅仅是一个粗略的思路，如果沿着这个思路去实现代码，非常复杂，因为管理集合还需要很多逻辑。 那么 ...

LeetCodeCampsDay53图论part04 继续使用深度/广度优先解决图的问题 其中105是有向图问题 110.字符串接龙 https://kamacoder.com/problempage.php?pid=1183 题目描述 字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列： 序列中第一个字符串是 beginStr。 序列中最后一个字符串是 endStr。 每次转换只能改变一个字符。 转换过程中的中间字符串必须是字典 strList 中的字符串，且strList里的每个字符串只用使用一次。 给你两个字符串 beginStr 和 endStr 和一个字典 strList，找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。如果不存在这样的转换序列，返回 0。 输入描述 第一行包含一个整数 N，表示字典 strList 中的字符串数量。 第二行包含两个字符串，用空格隔开，分别代表 beginStr 和 endStr。 后续 N 行，每行一个字符串，代表 strList 中的字符串。 输出描述 ...

LeetCodeCampsDay52图论part03 101.孤岛的总面积 题目描述 给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。 现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。 输入描述 第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。 输出描述 输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。 输入示例 123454 51 1 0 0 01 1 0 0 00 0 1 0 00 0 0 1 1 输出示例 11 提示信息 在矩阵中心部分的岛屿，因为没有任何一个单元格接触到矩阵边缘，所以该岛屿属于孤岛，总面积为 1。 数据范围： 1 <= M, N <= 50。 思路0 题目要求没有任何一个单元格接触到矩阵边缘，那：从四个边缘出发，将与之相邻的格子都变成海洋（设置为0），随后再统计保留下来为陆地的格子即可 如图，在遍历地图周围四个边，靠 ...