いいものをつくろう

CTOの日記

アルゴリズム

leetcode number of island

投稿日:

はい

最初に考えたのは、

順になめていって、1があったらそれは島なのでdfsで島全体を探索し

終わったら続ける

というようなものです

味噌は、終わったポイントは1以外でうわがきしてしまえば処理が楽ということです

 

最初の解

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        num = 0
        #self.print(S)
        for i, row in enumerate(S):
            for j, s in enumerate(row):
                #print(s, S[i][j])
                if s == '1':
                    num += 1
                    ##print('-'*8)
                    self.explore(S, i, j)
                    #sself.print(S)
                else:
                    pass

        return num

    def print(self, S):
        for row in S:
            print(row)

    def get(self, S, i, j):
        try:
            if i < 0 or j < 0: return None
            else: return S[i][j]
        except:
            return None

    def explore(self, S, i, j):
        stack = []
        stack.append((i, j))
        while len(stack) > 0:
            i, j = stack.pop()
            for ni, nj in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
                if self.get(S, ni, nj) == '1':
                    stack.append((ni, nj))
            S[i][j] = '0' # overwrite


 

そのあと別の回答を見てマネをして書き直してみたのが以下

とてもスッキリかけていますが、実行速度は全く同じです。

むしろ最初の解はスタックを使っている分、再帰呼び出しでスタックりょういき

を使ったり、再帰呼び出し制限とか気にしなくて良い分良かったりする面もありますね。

 

class Solution2:
    def numIslands(self, grid: List[List[str]]) -> int:
        def sinkIsland(grid, r, c):
            if (r < 0 or r >= len(grid) or
                c < 0 or c >= len(grid[0]) or
                grid[r][c] != '1'
            ):
                return
            else: # means grid[r][c] is 1
                grid[r][c] = '#'
                sinkIsland(grid, r-1, c)
                sinkIsland(grid, r+1, c)
                sinkIsland(grid, r, c-1)
                sinkIsland(grid, r, c+1)

        counter = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    counter += 1
                    sinkIsland(grid, i, j)
        return counter

 

良い点はやっぱり断然スッキリかけているところですね。

実行分析は

舐めるのでn*m, でdfsで最大(n*m)なのですからO(2(n*m))ですが最悪でのケースなので

time complexitはと聞かれれば素直に

time => O(n*m)

space => O(1)

です。

 

 

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.