微网站建设公司首选,腾讯云存储 wordpress,右面是某网站建设立项需求,个人简历在线填写leetcode 1466
使用dfs 遍历图结构 如图 node 4 - node 0 - node 1 因为节点数是n, 边长数量是n-1。所以如果是从0出发的路线#xff0c;都需要修改#xff0c;反之#xff0c;如果是通向0的节点#xff0c;例如节点4#xff0c;则把节点4当作父节点的节点…leetcode 1466
使用dfs 遍历图结构 如图 node 4 - node 0 - node 1 因为节点数是n, 边长数量是n-1。所以如果是从0出发的路线都需要修改反之如果是通向0的节点例如节点4则把节点4当作父节点的节点之间的路线的方向都需修改。 两个节点间只有一条方向所以可以确定如何修改取决和0节点的关系。
如图 node 0 - node 1 - node 3 - node 2 dfs (0, -1, e) - dfs (1, 0, e) - dfs(3, 1, e) e[3][0].first 1 parent continue; e[3][1].first 2 ! parent 但是 e[3][1].second 0, 所以不增加长度。
如图 (0 - 1), 使用 e[0][1] 1 和 e[1][0] 0 的表达方式。
数据结构
vectorvectorpairint, int
这个数据结构是一个二维的向量vector其中每个元素都是一个pairint, int类型的元素。可以将其理解为一个邻接表的表示方式。
具体来说这个数据结构可以表示一个有n个顶点的图其中每个顶点v都有一个对应的向量e[v]该向量存储了与顶点v相邻的顶点以及它们之间的边的信息。
每个pairint, int元素表示一条边其中第一个int表示与顶点v相邻的顶点第二个int表示边的权重或其他相关信息。
例如:e[0] {{1, 2}, {3, 4}}则表示顶点0与顶点1之间有一条权重为2的边以及顶点0与顶点3之间有一条权重为4的边。 例如: e[0][1] {1,2}
这种数据结构在表示稀疏图时非常有效因为它只存储了实际存在的边而不需要为所有可能的边分配空间。同时通过使用向量而不是链表可以提高访问和遍历的效率。
vectorvector 和 vectorvectorpairint, int
vectorvectorint和vectorvectorpairint, int在内存上的差别主要体现在存储的数据类型和元素的大小上。
对于vectorstd::vectorint它是一个二维向量其中每个元素都是一个一维向量而每个一维向量存储了一系列int类型的元素。因此内存中会按照一维向量的方式存储每个元素每个元素之间是连续存储的。这意味着在内存中整个二维向量是一段连续的内存空间。
而对于vectorvectorpairint, int它也是一个二维向量但每个元素是一个一维向量而每个一维向量存储了一系列pairint, int类型的元素。因为pairint, int占用的内存空间更大所以每个元素之间的存储空间可能不是连续的而是分散存储的。
具体来说对于vectorstd::vectorint内存中的存储布局可能类似于以下示意图
[元素1][元素2][元素3]...而对于vectorvectorpairint, int内存中的存储布局可能类似于以下示意图
[元素1-1][元素1-2][元素2-1][元素2-2][元素3-1][元素3-2]...其中每个元素1-1、1-2、2-1、2-2等表示pairint, int类型的元素。
因此vectorstd::vectorint在内存上是连续存储的而vectorvectorpairint, int可能是分散存储的每个元素之间的存储空间可能不是连续的。这也是它们在内存上的主要差别。
向量和链表
向量和链表在存储效率上有一些差异这取决于具体的操作和使用场景。
向量vector是一个动态数组它使用连续的内存块来存储元素。这意味着向量可以通过索引来快速访问元素并且在尾部进行插入和删除操作的效率也很高。然而在向量中间进行插入和删除操作可能涉及到移动元素的操作这会导致效率降低。此外当向量的大小超过当前分配的内存容量时可能需要重新分配更大的内存块并将现有元素复制到新的内存块中这也会带来一定的开销。
链表linked list是由一系列节点组成的数据结构每个节点包含数据和指向下一个节点的指针。链表的插入和删除操作在任意位置都很高效因为它只需要调整节点的指针而不需要移动其他元素。然而链表的随机访问效率较低因为需要从头节点开始遍历链表直到找到目标位置。此外链表的存储空间相对于向量来说更加分散因为每个节点需要额外的指针来指向下一个节点。
综上所述向量适用于需要频繁进行随机访问、尾部插入和删除操作的场景而链表适用于需要频繁进行插入和删除操作、对随机访问性能要求较低的场景。选择使用哪种数据结构取决于具体的操作和使用需求。
