いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 785 Is Graph Bipartite

投稿日:

こんにちは

今回の学びは

・ソートされた配列と二分木はよく似てるよ。

・できれば二分木探索を配列で実装していて 🙂

問題は。。。

(時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装  20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。

終始、わからないことは声にだして、明確にしていきましょう。

1,まずは入出力をしっかりおさえましょう。(問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと)

 

2,いくつかのソリューションを声にだして出してみましょう。(もちろんtime complexit, space complexityの分析や理由を付け加えて)

 

3,どれでいくか、一緒に決定しましょう。(理由付きでね、よろしく)

timespace analysis (時間とスペースの分析)は 〇〇です

O( V+E log (V)), pO( V )

場合によっては、pseudocode(擬似コード)をかいてみてもよい。

 

4、実装しましょう。

最初の間違った実装は。ロジックが定まってないので、ヒューリスティックに届かないノードは全部マークしてしまっています。これでも半分くらいテスト通るので面白い。

class unionfind:
    def __init__(self, n):
        self.n = n
        self.pars = [-1] * n
    def find(self, x):
        if self.pars[x] < 0:
            return x
        else:
            oya = self.pars[x]
            return self.find(oya)
            #self.pars[x] = self.find(oya)
            #return self.pars[x]
    def union(self, x, y):
        X = self.find(x)
        Y = self.find(y)
        if X == Y: return
        if self.pars[X] > self.pars[Y]:
            X, Y = Y, X

        self.pars[X] += self.pars[Y]
        self.pars[Y] = X


class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        if graph is None: return False
        N = len(graph)
        if N <= 1: return False
        uf = unionfind(N)
        #print(uf.pars)
        whole = {i for i in range(N)}
        for i in range(N):
            for j in whole - set(graph[i] + [i]):
                uf.union(i, j)
        #print(uf.pars)
        return len([x for x in uf.pars if x < 0]) == 2

わからなかったのでこちら、

https://leetcode.com/problems/is-graph-bipartite/discuss/445182/my-cpp-union-find-solution

参考にしまして、

 

class unionfind:
    def __init__(self, n):
        self.n = n
        self.pars = [-1] * n
    def find(self, x):
        if self.pars[x] < 0:
            return x
        else:
            oya = self.pars[x]
            return self.find(oya)
            #self.pars[x] = self.find(oya)
            #return self.pars[x]
    def union(self, x, y):
        X = self.find(x)
        Y = self.find(y)
        if X == Y: return
        if self.pars[X] > self.pars[Y]:
            X, Y = Y, X

        self.pars[X] += self.pars[Y]
        self.pars[Y] = X

#https://leetcode.com/problems/is-graph-bipartite/discuss/445182/my-cpp-union-find-solution
class Solution_unionfind:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        if graph is None: return False
        N = len(graph)
        if N <= 1: return True
        uf = unionfind(N)
        #print(uf.pars)
        whole = {i for i in range(N)}
        for i in range(N):
            for j in range(len(graph[i])):
                if uf.find(i) == uf.find(graph[i][j]):
                    return False
                if j > 0:
                    uf.union(graph[i][j], graph[i][j-1])
        return True

 

色塗りの方法は参考動画

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        # coloring
        # https://www.youtube.com/watch?v=Gmp51E8HVVs
        if graph is None: return False
        if len(graph) <= 1: return True

        colors = [0] * len(graph)

        def dfs(i, color): # trying to color the node
            if colors[i] != 0:
                return colors[i] == color
            else:
                colors[i] = color
                for j in graph[i]:
                    if dfs(j, -color) == False:
                        return False
            return True

        for i in range(len(graph)):
            if colors[i] == 0 and dfs(i, 7) == False:
                return False
        return True

5、エッジケースとサンプルテストを忘れずに!

 

 

 

振り返り

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

色塗りだな。

 

まとめ

 

以上です

-アルゴリズム
-,

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