こんにちは
今回の学びは
・ソートされた配列と二分木はよく似てるよ。
・できれば二分木探索を配列で実装していて 🙂
問題は。。。
（時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装 20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。
終始、わからないことは声にだして、明確にしていきましょう。
１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと）
２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析や理由を付け加えて）
３，どれでいくか、一緒に決定しましょう。（理由付きでね、よろしく）
timespace analysis (時間とスペースの分析）は 〇〇です
O( V+E log (V)), pO( V )
場合によっては、pseudocode（擬似コード）をかいてみてもよい。
４、実装しましょう。
最初の間違った実装は。ロジックが定まってないので、ヒューリスティックに届かないノードは全部マークしてしまっています。これでも半分くらいテスト通るので面白い。
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
５、エッジケースとサンプルテストを忘れずに！
振り返り
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
色塗りだな。
まとめ
以上です