06、数据结构与算法 - 实战:图的接口实现
摘要 本期通过实现图的接口函数,来进一步理解在代码中,图的结构是如何形成的,比如怎么定义边、如何定义顶点、如何定义边与顶点的连接关系等等。 本期通过实现图的接口函数,来进一步理解在代码中,图的结构是如何形成的,比如怎么定义边、如何定义顶点、...
摘要 本期通过实现图的接口函数,来进一步理解在代码中,图的结构是如何形成的,比如怎么定义边、如何定义顶点、如何定义边与顶点的连接关系等等。 本期通过实现图的接口函数,来进一步理解在代码中,图的结构是如何形成的,比如怎么定义边、如何定义顶点、...
摘要 实现图结构的方案大致为邻接矩阵和邻接表,本期就介绍一下这两个方案分别是什么。在最后会处理一下图的基本接口,以及顶点结构和边结构,为下期代码实现做准备。 实现图结构的方案大致为邻接矩阵和邻接表,本期就介绍一下这两个方案分别是什么。在最后...
公众号:“皇子谈技术”主理人
摘要 在上期介绍完无向图和有向图之后,延伸出完全图、有权图以及连通图。主要根据边直接连接,还是间接连接,有方向,还是没有方向来区分。其中的有权图在实际生活中可以找到很多对应的场景。 在上期介绍完无向图和有向图之后,延伸出完全图、有权图以及连...
摘要 数据结构中第三大分类就是图结构。简单地理解,图就是由顶点和边组成的。根据顶点的分布和边的连接这两种情况,可以分成不同的类型。接下来将介绍图以及它的大致分类。 数据结构中第三大分类就是图结构。简单地理解,图就是由顶点和边组成的。根据顶点...
摘要 并查集解决的就是快速查找和连接的问题,所以就有在连接(即合并)上的优化和在查找上的优化。不管哪个方面的优化,核心就是降低树的高度,就能减少合并时调整的路径,查找时经过的路径,时间复杂度也就随之降低。 并查集解决的就是快速查找和连接的问...
摘要 并查集可以快速查找多个点之间是否连接,以及快速连接多个点。并且并查集使用数组的数据结构实现。那么如何利用数组的结构实现?以及为什么能够快速查找和连接呢?文章将给出答案。 并查集可以快速查找多个点之间是否连接,以及快速连接多个点。并且并...
题目一 力扣第312题 有n个气球,编号为0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i...
什么是后缀数组 假设有字符串 aabaabaa 那么从每个位置开始,到结尾位置,截取后缀串,可得 a aa baa abaa aabaa baabaa abaabaa aabaabaa 然后根据字典序对后缀串进行排序,排序结果放入数组中,数...
can-i-win 力扣464题 https://leetcode.cn/problems/can-i-win/description/ 在“100 game” 这个游戏中,两名玩家轮流选择从 1 到 10 的任意整数,累计整数和,先使得累...
题目一 给定一个非负数组arr,长度为N, 那么有N-1种方案可以把arr切成左右两部分 每一种方案都有,min{左部分累加和,有部分累加和} 求这么多方案中,min{左部分累加和,有部分累加和}的最大值是多少? 整个过程要求时间复杂度O(...