arrays - 如何在数组中找到连接的组件
问题描述
我正在尝试在 hackerrank、Roads 和 Libraries中解决算法问题。问题背后的想法是使用 DFS 通过数组查找连接的组件 (CC)。
这是测试用例:
queries = [
{
n_cities_roads: [9,2],
c_lib_road: [91, 84],
matrix: [
[8, 2], [2, 9]
]
},
{
n_cities_roads: [5,9],
c_lib_road: [92, 23],
matrix: [
[2,1], [5, 3], [5,1],
[3,4], [3,1], [5, 4],
[4,1], [5,2], [4,2]
]
},
{
n_cities_roads: [8,3],
c_lib_road: [10, 55],
matrix: [
[6,4], [3,2], [7,1]
]
},
{
n_cities_roads: [1, 0],
c_lib_road: [5, 3],
matrix: []
},
{
n_cities_roads: [2, 0],
c_lib_road: [102, 1],
matrix: []
}
]
queries.each do |query|
(n_city, n_road), (c_lib, c_road) = [*query[:n_cities_roads]], [*query[:c_lib_road]]
roads_and_libraries n_city, c_lib, c_road, query[:matrix]
end
输出应该是:
805
184
80
5
204
我目前的解决方案在某些情况下可以获得 CC,但不是全部。
def dfs(i, visited, matrix)
visited[i] = true
unless matrix[i].nil?
matrix[i].each do |j|
unless visited[j]
dfs j, visited, matrix
end
end
end
end
def roads_and_libraries(no_cities, c_lib, c_road, cities)
return c_lib * no_cities if c_lib <= c_road
visited, count = Array.new(no_cities, false), 0
(0..no_cities).each do |i|
unless visited[i]
count += 1
dfs i, visited, cities
end
end
p (c_road * (no_cities - count)) + (c_lib * count)
end
上面我的代码的测试输出是:
805
184
7
305
我正在努力了解如何正确使用 DFS 来查找连接的组件。不知道我哪里错了。
解决方案
只需打印这一行:
p roads_and_libraries n_city, c_lib, c_road, query[:matrix]
不是这个
p (c_road * (no_cities - count)) + (c_lib * count)
因为方法中有返回:
return c_lib * no_cities if c_lib <= c_road
我不知道算法,但似乎矩阵不能为空[]
,至少它必须是[[1,1]]
获得所需的输出:
roads_and_libraries 1, 5, 3, [[1,1]] #=> 5
roads_and_libraries 2, 102, 1, [[1,1]] #=> 204
因此,要处理空矩阵,一种方法是将其添加为dfs
方法中的第一行:
matrix = [[1,1]] if matrix.empty?
推荐阅读
- python - 如何将 Postgres 结果集作为 CSV 从远程数据库连接导出到本地机器?
- python - 将带有字典列表的熊猫系列转换为带有字典列的数据框
- javascript - 如何在 Ember js 3.13 中正确处理按键事件
- c# - 每个 GCode 图像的 Windows 文件资源管理器预览 C#
- python - Pandas 根据条件获取行 ID
- flutter - 如何根据颤动中TextField中的输入填充下拉列表?
- java - JPA 继承:MappedSuperclass 还是加入?
- sql - 需要按数据集中的值对第一列进行排序,然后找到平均值
- function - 在 Julia 中绘制函数突然不起作用
- c - 根据包含索引的另一个数组的内容对 C 字符数组进行排序