こんにちは
今回の学びは
・ソートされた配列と二分木はよく似てるよ。
・できれば二分木探索を配列で実装していて 🙂
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
hardです。
Hardで、ちょっと身構えちゃいますが
おそれることは有りません。基礎ができているば
あとはその組み合わせ
それか、それプラス、ちょっと視点をかえて、アイデアをいれる
それでも解けない場合は、bucket sortなど、高度な術を知っている
と
簡単に解ける場合など様々です。
が、くりかえしになりますが、ほとんどの問題は考えれば解けます。
解けると思って、身構えず、風通にmediumの延長として取り組みましょう。
さぁ、
この問題
sortしたら簡単だけど、それをしちゃーだめで
o(n)でときなさいと
graphを利用するんだな、とほぼ確信に近いチートの上で
どのよに、それが利用できるか考える。
なんか
1-2-3のような木構造をつくってから、それこそnumber of island的に
数えられそう。
ということで
graph + dfsという術が効きそう、と思っている。
さらに
それをするためには
1の辺は0, 2で -1, +1で汎用化できる。
ここまで来たらあとは実装です。
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
graphのdfsなのでO(n)です。
何を返すかは、解いている最中は、まだ整理がついてないので
いつもまごつきます。
実際の実装はこちら
def longestConsecutive(self, S: List[int]) -> int:
length = len(S)
if length <= 0: return 0
edges = {}
from collections import defaultdict
exist = defaultdict(lambda:False)
visit = defaultdict(lambda:False)
for i in range(length):
value = S[i]
edges[value] = [value-1, value+1]
exist[value] = True
def dfs(value, sofar=0) -> int:
visit[value] = True
counter = sofar
#if value not in exist: # O(logN)
if not exist[value]: # O(1)
return counter
counter += 1 # value is exist, so add one
tmp = 1
for neighbour in edges[value]:
if exist[neighbour] and not visit[neighbour]:
# 帳尻合わせっぽい、感じになってしまったが、まぁ -1というのは neigherから帰ってくるのはvalueも含めてにことなので、その辺
# をうまくやるための -1。
tmp += dfs(neighbour, counter) - 1
return max(tmp, counter)
maxi = 0
for i in range(length):
maxi = max(dfs(S[i], 0), maxi)
return maxi
後から考えれば、自分を含まない数を返してそのままtmp +=するのが
キレイかなとおもう。
実装後です。timespace analysis (時間とスペースの分析）は ◯◯
o(n)問題ですからね♪
まとめ
・hardもやれば解ける！
以上です