こんにちは
今回の学びは
・擬似コードでアイデアの取捨選択を早めの段階で行え。POCみたいなもんやね。
・文字化すると、逆点の発想を起こしやすい、逆転の発想とは、各文字の反対の意味を考えていけばいいからだ。
・うまくいかないときは一旦白紙にもどそう。
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
最初はアイデアをとりあえずだして
あーだこーだ
する。
3<4>2,n<3>n,n<2>2,n<1>n,1<2>n S = 3<4>2,n<3>n,n<2>2,n<1>n,1<2>n .split(',') def dfs(S): if len(S) == 1: clause = S.pop() v, l, r = S[0].split('<|>') Node(v) すでにむずいやん。 だからやっぱbfsでいこ bfs info = 3<4>2,n<3>n,n<2>2,1<2>n,n<1>n info = [4<3:2:,3<:,2<:2,2<1:,1<:] S = [4<3:2:,3<:,2<:2,2<1:,1<:] i = start index j = end index (exclusive) like python list slice parent_node def bfs(S, i, j, parent): for child in S[i:j]: l, r = child left, right = None(l), Node(r) if parent: parent.left(left), parent.right(right) num = how many, childrene doesn, l and r has? if num > 0: for spawn in (l, r) bfd(S, i, j+num,spawn) ssss = 3<4>2 left = 3 value = 4 right = 2 # instanciate node = Node(4) --> もしnext_parentがあれば、こいつ l = Node(3), r = Node(2) node.left = l, node.right = r # ここで子供の数も数えておかないといけない。 next_parent = node とまぁ、こんな感じだ。 次はdfsでやってみる
というように
bfsでやったほうが良さそうだ感をえる。
これが擬似コードの素晴らしいとこです。
・擬似コードでアイデアの取捨選択を早めの段階で行え。POCみたいなもんやね。
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は bfsでO(n)
実際の実装はこちら
この最初の実装は次へのポイントがうまく機能してない
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
def str_or_empty(node: TreeNode):
return node.val if node else ""
if root == None: return ""
values = []
layer = [root]
while len(layer) > 0:
next_layer = []
layer_elements = len(layer)
while len(layer) > 0:
node: TreeNode = layer.pop(0)
tmp = "%s<%s|%s:%s" % (
node.val,
str_or_empty(node.left), str_or_empty(node.right),
layer_elements
)
layer_elements -= 1
values.append(tmp)
if node.left: next_layer.append(node.left)
if node.right: next_layer.append(node.right)
layer.extend(next_layer)
return ",".join(values)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
S = data.split(',')
def bfs(i) -> TreeNode:
if i >= len(S): return None
clause = S[i].split('<')
value = clause[0]
tree_layer = clause[1].split(':')
layer_elments = int(tree_layer[1])
l, r = tree_layer[0].split('|')
# number of children of this node. 0, 1 or 2
n = len([x for x in [l, r] if x != ''])
node = TreeNode(value)
if l:
node.left = bfs(i + layer_elments + 0)
if r:
offset = 1 if l else 0
node.right = bfs(i + layer_elments + offset)
return node
if data.strip() == "": return None
else: return bfs(0)
でも
惜しいのよ。
もうちょいよ。
もうちょい、デバッグして見て。
だめだ。 全然、うまくいかない。 かれこれ計三時間は考えているぞ このような時は 一回まっさらに戻し、ます。 新降級してから はい。再度行きましょう。
・うまくいかないときは一旦白紙にもどそう。
この繰り返しで人は強くなる。
どうしても息詰まる時は既に複雑度が俺の許容量を超えている。
そういうときはもう一回整理してキレイな方法がないか確認するようにする。
そして、いきなり
カッコイイ解答をだそうとしない。
hardに限るが、ブルートフォースに毛が生えたくらいでもよい。（特にhardとかの場合はね。mediumだったら本番でもはブルートフォースを悠長に実装して、でっできました！ふぅ〜といっている余裕はないですので）
解法の肝は
シリアライズ時に使えそうなmeta情報、次のノードは右にいくつシフトすればいいか？を予め埋め込んでおくという発想
これは、deserialize時に計算するのではなく、事前にやってしまえばいいじゃん！というある種，逆転の発想であるが
文字化すると、逆点の発想を起こしやすい、逆転の発想とは、各文字の反対の意味を考えていけばいいからだ。
具体的には
これを今から計算するのは大変なのでserializationの時にどうにか
埋め込めないか？ A:俺の答えは逆点の発想で埋め込むことだった。 同じ階層のノード数をdeserialize時に調べるにはどうしたらいいか？というように丁寧に文字起こしと、言葉の入れ替え作業を行った結果だったのだ。
このシリアライズのいいところはnull情報のみのsubtreeを保存してないので、大きな木の場合、メモリの消費が少なくて済む
""" まずはメモリ使い放題プランでいこうと思う """ class Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ def str_or_empty(node: TreeNode): return node.val if node else "" if root == None: return "" values = [] layer = [root] while len(layer) > 0: next_layer = [] layer_elements = len(layer) next_point = layer_elements while len(layer) > 0: node: TreeNode = layer.pop(0) tmp = "%s<%s|%s:%s" % ( node.val, str_or_empty(node.left), str_or_empty(node.right), next_point ) next_point -= 1 values.append(tmp) if node.left: next_layer.append(node.left) if node.right: next_layer.append(node.right) next_point += (1 if node.left else 0) + (1 if node.right else 0) layer.extend(next_layer) return ",".join(values) def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ S = data.split(',') def bfs(i) -> TreeNode: if i >= len(S): return None clause = S[i].split('<') value = clause[0] tree_layer = clause[1].split(':') next_point = int(tree_layer[1]) l, r = tree_layer[0].split('|') # number of children of this node. 0, 1 or 2 n = len([x for x in [l, r] if x != '']) # 同じ階層でどれだけのノードがあるのか？ # これを今から計算するのは大変なのでserializationの時にどうにか # 埋め込めないか？ A:俺の答えは逆点の発想で埋め込むことだった。 # 同じ階層のノード数をdeserialize時に調べるにはどうしたらいいか？というように丁寧に # （すごいチップ！！！）文字化すると、逆点の発想を起こしやすい、逆転の発想とは、各文字の反対の意味を考えていけばいいからだ。 # layer_elementsを単純に足すと、参照が飛んでしまった。 # 現時点から次のlayerへの最初のindexに飛ぶにはいくつ飛べばいいのか、というような情報にしなければならない。 # そこでlayer_elements -= 1とうのを考えた。 # これを、serialize時に入れようと。 # layer_elementsという考えから # いくつヅラせば良いかという考えへ。next_point logging.debug("i:%s, value:%s, l:%s, r:%s, n:%s, next_point:%s" % (i, value, l, r, n, next_point)) node = TreeNode(value) if l: node.left = bfs(i + next_point + 0) if r: offset = 1 if l else 0 node.right = bfs(i + next_point + offset) return node if data.strip() == "": return None else: return bfs(0)
実装後です。timespace analysis (時間とスペースの分析）は ◯◯
きた来たーーーーーーーーーーーーーーーーーー！！
これ。
ハード問題、また来たー
まじ、半日考えて、実装してこれだ。
ちゃんと、アイデアの軌跡をまとめたいところ。
他の回答、なんじゃこれ。
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/discuss/357899/Classic-naive-approach
解析したい。
まとめ
・擬似コードでアイデアの取捨選択を早めの段階で行え。POCみたいなもんやね。
・文字化すると、逆点の発想を起こしやすい、逆転の発想とは、各文字の反対の意味を考えていけばいいからだ。
・うまくいかないときは一旦白紙にもどそう。
以上です