草庐IT

algorithm - 计算二维数组中 block 组的总数？

coder 2024-07-11 原文

假设您给定了一个二维数组，其中包含值(0 或 1)。

计算给定数组中相邻 1 组的总数。

示例 1:
1, 0, 0
0, 0, 0
0, 0, 1

答案:2

解释:在上面的例子中，单个1的 block 也被认为是一组。

例子2:
1, 1, 0, 1, 1, 0
0, 1, 0, 0, 0, 1
0, 1, 0, 1, 1, 0
0, 1, 1, 0, 0, 0

答案:1

说明:在上面的例子中，一组1的 block 与至少一个1的 block 相邻。

我的解决方案:https://play.golang.org/p/nyw4lm6yrQ1

但是看起来，时间复杂度是O(n^2)

最佳答案

著名的岛屿数量问题。 您可以通过保留已访问单元格的 bool 矩阵来执行 dfs 来轻松解决此问题。

class Graph: 

    def __init__(self, row, col, g): 
        self.ROW = row 
        self.COL = col 
        self.graph = g 

# to check validity of cell
    def isSafe(self, i, j, visited): 
        return (i >= 0 and i < self.ROW and 
                j >= 0 and j < self.COL and 
                not visited[i][j] and self.graph[i][j]) 


    def DFS(self, i, j, visited):

        row = [-1, -1, -1,  0, 0,  1, 1, 1]; 
        col = [-1,  0,  1, -1, 1, -1, 0, 1]; 


        visited[i][j] = True

        # check all 8 neighbours and mark them visited
        # as they will be part of group
        for k in range(8): 
            if self.isSafe(i + row[k], j + col[k], visited): 
                self.DFS(i + row[k], j + col[k], visited) 


    def group(self): 

        visited = [[False for j in range(self.COL)]for i in range(self.ROW)] 

        count = 0
        for i in range(self.ROW): 
            for j in range(self.COL): 
                # traverse not visited cell
                if visited[i][j] == False and self.graph[i][j] == 1: 
                    self.DFS(i, j, visited) 
                    count += 1

        return count

`

g = [[1, 1, 0, 0, 0], 
    [0, 1, 0, 0, 1], 
    [1, 0, 0, 1, 1], 
    [0, 0, 0, 0, 0], 
    [1, 0, 1, 0, 1]]
graphe = graph(len(g),len(g[0]),g)
print(graphe.group())

关于algorithm - 计算二维数组中 block 组的总数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57332440/

algorithmblockselfvisitedsectiongooptimizationmultidimensional-arraydata-structures

有关algorithm - 计算二维数组中 block 组的总数？的更多相关文章

  1. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  2. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  3. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  4. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

  5. ruby - RSpec - 使用测试替身作为 block 参数 - 2

    我有一些Ruby代码，如下所示:Something.createdo|x|x.foo=barend我想编写一个测试，它使用double代替block参数x，这样我就可以调用:x_double.should_receive(:foo).with("whatever").这可能吗？ 最佳答案 specify'something'dox=doublex.should_receive(:foo=).with("whatever")Something.should_receive(:create).and_yield(x)#callthere

  6. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  7. ruby-on-rails - 使用一系列等级计算字母等级 - 2

    这里是Ruby新手。完成一些练习后碰壁了。练习:计算一系列成绩的字母等级创建一个方法get_grade来接受测试分数数组。数组中的每个分数应介于0和100之间，其中100是最大分数。计算平均分并将字母等级作为字符串返回，即“A”、“B”、“C”、“D”、“E”或“F”。我一直返回错误:avg.rb:1:syntaxerror,unexpectedtLBRACK,expecting')'defget_grade([100,90,80])^avg.rb:1:syntaxerror,unexpected')',expecting$end这是我目前所拥有的。我想坚持使用下面的方法或.join，

  8. ruby-on-rails - Enumerator.new 如何处理已通过的 block ？ - 2

    我在理解Enumerator.new方法的工作原理时遇到了一些困难。假设文档中的示例:fib=Enumerator.newdo|y|a=b=1loopdoy[1,1,2,3,5,8,13,21,34,55]循环中断条件在哪里，它如何知道循环应该迭代多少次(因为它没有任何明确的中断条件并且看起来像无限循环)？ 最佳答案 Enumerator使用Fibers在内部。您的示例等效于:require'fiber'fiber=Fiber.newdoa=b=1loopdoFiber.yieldaa,b=b,a+bendend10.times.m

  9. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  10. ruby - 在 Ruby 中用键盘诅咒数组浏览 - 2

    我正在尝试在Ruby中制作一个cli应用程序，它接受一个给定的数组，然后将其显示为一个列表，我可以使用箭头键浏览它。我觉得我已经在Ruby中看到一个库已经这样做了，但我记不起它的名字了。我正在尝试对soundcloud2000中的代码进行逆向工程做类似的事情，但他的代码与SoundcloudAPI的使用紧密耦合。我知道cursesgem，我正在考虑更抽象的东西。广告有没有人见过可以做到这一点的库或一些概念证明的Ruby代码可以做到这一点？ 最佳答案 我不知道这是否是您正在寻找的，但也许您可以使用我的想法。由于我没有关于您要完成的工作

随机推荐