こんにちは
今回の学びは
・ソートされた配列と二分木はよく似てるよ。
・できれば二分木探索を配列で実装していて 🙂
問題はmeduim 133 clone-graph
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
終始、わからないことは声にだして、明確にしていきましょう。
１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと）
配列でわたされるの？ノードで？valはユニーク？
２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析や理由を付け加えて）
３，どれでいくか、一緒に決定しましょう。（理由付きでね、よろしく）
timespace analysis (時間とスペースの分析）は 〇〇です
場合によっては、pseudocode（擬似コード）をかいてみてもよい。
４、実装しましょう。
自分の実装はO(3N)で、悪くわないと思いますが、冗長です
class Solution:
def rec(self, node: Node, cloned):
if node is None: return None
if node.val not in cloned:
new_node = Node(node.val) # let's clone
cloned[node.val] = new_node
for next_node in node.neighbors:
self.rec(next_node, cloned)
def rec2(self, node: Node, cloned, visited):
if node is None: return None
if node.val not in visited or visited[node.val] == 0:
new_node = cloned[node.val]
# neighbors creation
for next_node in node.neighbors:
new_node.neighbors.append(cloned[next_node.val])
visited[node.val] = 1
for next_node in node.neighbors:
self.rec2(next_node, cloned, visited)
def cloneGraph(self, node: Node) -> Node:
if node is None: return None
cloned = {}
self.rec(node, cloned)
visited = {}
self.rec2(node, cloned, visited)
return cloned[node.val]
いいやつはO(1N)です
https://leetcode.com/problems/clone-graph/discuss/478738/Intuitive-Python-BFS
class Node:
def __init__(self, val):
self.val = val
self.neighbors = []
class Solution:
def cloneGraph(self, node: Node) -> Node:
from collections import deque
if node is None: return None
q = deque()
visited = {}
visited[node] = Node(node.val) # 最初に作っておく
q.append(node)
"""
queueに入れる前に具現がされていること！
"""
while len(q) > 0:
curr: Node = q.popleft() # q = [4], cloned = {1: 1', 2: 2', 4: 4'}
for neighbor in curr.neighbors: # q = [4], curr = 2
if neighbor not in visited: # neighbors = [1, 3]
visited[neighbor] = Node(neighbor.val) # cloned = {1: 1', 2: 2', 4: 4', 3:3'}
q.append(neighbor) # q = [2, 4]
# visited[1] = 1' -> neighors(2', 4')
# visited[2] = 2' -> neighors(1')
visited[curr].neighbors.append(visited[neighbor]) # すでに具現化されているので。
return visited[node]
最初の実装は40ms, 36%で、
あとのdequeは36ms, 72%の速さでした。
５、エッジケースとサンプルテストを忘れずに！
振り返り
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
この問題はdequeを使うとと楽
類似問題はcopy-list-with-random-pointer
まとめ
以上です