こんにちは
今回の学びは
・技の習得を一個づつ丁寧にすべし！
・変数の流れを制約するすることで処理の向きを一方方向に、そして変数管理を減らす！
（ぎゃくに言えば0だったらkを使うということを必須にしてしまう。）
・実装はいつもシンプルでなければアルゴリズムを見直せ
マラソンのやりかた
マラソンでは一時間で難問とけるかのトライアルです。今までの練習の実践編です。
できるだけ解ければ良しなのですが、1問解く時間の目安は20分としてみます。
マラソン中は振り返らず、終了後にいつものように「次のこの問題を解くばあい知っていればよい一つの事実とは？」
とう問題の核となるものを抽出していきます。
問題の選び方は、今はleetcodeのpick nextで良さげなもを選ぶ、というほぼノールールでいきます。
それでは始めます。(適当な問題へのリンクはこちら、ここからPick Oneでスタート!)
8:03 start
1問目 => easy 594. Longest Harmonious Subsequence
30分かかってしまいました。
dpでも解けそうな問題ですのであとで挑戦しますが、
差分が1というのでhashマップを利用してO(N)で解いています。
from collections import defaultdict
class Solution:
def findLHS(self, nums: List[int]) -> int:
# space O(N) - duplicate
mapping = defaultdict(int)
# time O(N)
for n in nums:
mapping[n] += 1
# time O(N)
maxi = 0
pre = None
tups = [(n, count) for n, count in mapping.items()]
tups.sort(key=lambda tup: tup[0])
for n, count in tups:
#print(n, count)
if pre is not None and abs(pre - n) == 1:
y = mapping[n] + mapping[pre]
maxi = max(maxi, y)
pre = n
return maxi
2問目 => medium 397 integer-replacement
さっきのより簡単に感じた。
recursiveなんですが、O(logN)の速さです。入力が必ず半減していくので 🙂
3問目 => medium 1004. Max Consecutive Ones III
完敗。手足でず。。。。
このショックは大きかったので三日ほどleetcodeから離れました。
意図的にでなく潜在的な意識でサボったと思います。
動画をみました。
sliding windowを使えばすごくシンプルだよ、とのことなので
しばし考えさせてください。
Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
例えばこのケースね
[1,1,1,0,0,0,1,1,1,1,0]
i
j
while i < len(S) or j < len(S):
S[i]
S[j]
if S[j] == 1:
max_update()
else:
もしk > 0で
S[j]が1なら j++
0なら k--
えるす
S[j]が1なら i++
0なら k++
max_update => max(maxi, j+1 - i)
こういう細かい遷移は苦手です。頭が追いつかない。
短期記憶の前頭葉を鍛える必要がありそうです。
時には動画の人のようにいきなりコーディングにはいるのも悪くない。
そちらのほうがまだスッキリイメージできる
class Solution:
def longestOnes(self, S: List[int], k: int) -> int:
maxi = 0
sz = len(S)
i = j = 0
while i < sz and j < sz:
if S[j] == 1:
maxi = max(maxi, j+1 - i)
j += 1
else:
if k > 0:
maxi = max(maxi, j+1 - i)
k -= 1
j += 1
else:
if S[i] == 0:
k += 1
i += 1
return maxi
そしてしばらくたってできたのが上記。
この問題、難しかったよ。
スライディングって一応頭の中で当初考えたけどできないって弾きましたし。。。
しかし
あらためて思うのは実装はいつもシンプル
少しでも複雑な時はアルゴリズむが良くないというのはほとんどのケースであてはまるんではないだろうか。
・実装はいつもシンプルでなければアルゴリズムを見直せ
これ後輩にかっこよく言いたいレベルのセリフですねw
そしてどうやったらスライディングでいける！というとこまでかんがえられるのだろうか？
まずは
総当たり -> 0が置ける組み合わせを `0の個数 C k` とい数式で表して、そこからO(N)で長さチェック。約O(N^3)
のアルゴリズムができます。
この次は解答者の力量を問われるところですが、
ここを形式化したいところでもあります
私の場合はDPっぽなー と思って、その路線で考えたこと。
しかしDPもマスターしていないので、これに時間がかかる！もしくはできる、できないの判断に持っていけない
技の習得を一個づつ丁寧にすべし！
習得したい技はDP, sliding window, dfs, bfs, recursive, greedy, 累積和
といったところです。
マスターすれば、それを軸にまた考えが速くなるんで非常に、勉強してマスターするまでには時間はかかるがマスター
できれば、好循環です。
ということで
まずは苦手意識のあるsliding masterコースへ link
と、まぁ鍛えるのはすぐ後にするとして
話をもどしてDPの他にわたしが何を考えたか。
あぁ、ハッシュだ。ハッシュでなんとかならないかと。
連続値を覚えておく、0の連続のところにkをはめていく。。。。
kをはめるパターンが実はおおくて断念。とこのあたりで頓挫。
スライディングに関しては
最大をもとめてるんだからi, jを両脇に置いてうまいこと縮めてこれないかと？
どちらか0の場合は中央へ、0の場合もk回は救える。
kをどうしたら復活増やす条件につながるかなんて
考えれなかったし、考えたとしても整理できていたかどうか。。。とい感想です。
最終的にな解答は
秀逸です。
1110001111って会った時にk=2だとして
1111101111と二つkで0を救ったところで、これ以上この連鎖はできないと
見た目ではわかります。
これは大きな手がかりだと後になるとわかります。
index 4以上は０ももうkつか果たしたし、救いようがない。
しかし、一旦処理をきってしまうのは、余計複雑になる。なんとかsliding window的な
アプローチができないだろうか！？
kが枯渇したので,今度は左ポインタをインクリしてみる
むむ。インクリしていくと
0だった部分は、kを使った部分なので＝＞ぎゃくに言えば0だったらkを使うということを必須にしてしまう。
それで幾分処理は楽になる。
それで
考えていくと
左ポインターの場合は0の時にkがインクリできる。
あらためて両はしにポインタを置いてスターさせるのは、kをどこで使ったのかの管理できないので無理
という風に判断して
このパスを捨てることができたのではないだろうか
・変数の流れを制約するすることで処理の向きを一方方向に、そして変数管理を減らす！
とにかく、まずは苦手意識のあるsliding masterコースへ link
やります。
（時間配分は5分問題理解 10分検討 10分実装の一文20分構成)
まずは入出力をしっかりおさえましょう。
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
1問目 => medium 71. Simplify Path => linuxのパスでcanonicalっていうのがあります。
次！easy valid-phone-numbers => while read lineを覚えておきましょう
easy 189. Rotate Array => 一個づらすのをどうやって解くかかんがえてみましょうか？
3問目 => medium 1004. Max Consecutive Ones III => sliding widnow
まとめ
・技の習得を一個づつ丁寧にすべし！
・変数の流れを制約するすることで処理の向きを一方方向に、そして変数管理を減らす！
（ぎゃくに言えば0だったらkを使うということを必須にしてしまう。）
・実装はいつもシンプルでなければアルゴリズムを見直せ
以上です