こんにちは
今回の学びは
・whileですすませるパターンの習得
・思い込みが激しい自分をまずは強く意識して・もうひとりのダブルチェックをしてくれる確認する自分をつくる
問題は最近立て続けやってきましたleetcode easy remove duplicate from sorted array ii配列から重複を省くパターンの
リンクリスト版です
実装前後でこれは毎回書きましょう。timespace anaylysis (時間とスペースの分析）は O(n）です
重複がはじまったら、重複が終わるところまで進ませるをwhileで表現し
そのポイントと重複が始まる前のポイントをくっつける作業をする
いきなり重複が始まるパターン
中腹にあるパターン
最後にあるパターン
その全てのパターンと場合分けが必要かもしれません。
新しい重複なしポイントは常にprevになるべきとうことがわかります。
私はprepreとう変数で前の前のポイントを覚えておく手法をとりました
実際の実装はこちら
O(n)の解法がすぐ思いつく問題は実装力を問われていると思っていいでしょう。
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummy = ListNode("dummy")
dummy.next = head
curr = head
prev = dummy
prepre = None
while curr:
if curr.val == prev.val:
# skip til to new value
temp = curr
curr = curr.next
while curr:
if curr.val != temp.val:
break
curr = curr.next
prev = prepre
prepre.next = curr
else:
prepre = prev
prev = curr
curr = curr.next
return dummy.next
実装後です。timespace anaylysis (時間とスペースの分析）は O(n)ですね
今回の実装は実はデバッグに２時間くらいかかってしまいました。
入力と出力の意識が低かったからでしょう。以下のように入力rootをそのまま出力して、サンプルケース２がなかなか通らずに
並んでおりました。インプレースで得問題でしたので、そこで勘違いが発生していたようです
print(nodeToString(root)) Solution().deleteDuplicates(root) print(nodeToString(root))
たわしはこのような勘違いが少なくない人です
ということでぐぐりました => 勘違いをなくす方法がびっくりするほど自分に当てはまっていたので
自分は思い込みが強いほうだと意識して、丁寧に情報を入力していこうと
思いました。情報を取り込みながら、あ、これはこういうことでしょう！？早合点とか
次に喋りたいことばっかりきになったり、正解のときはそれは悪いことにならないけど
自分の中の自分でチェックしてくれるもうひとりの自分が必要だと感じました
まとめ
whileですすませるパターン
もうひとりのダブルチェックをしてくれる確認する自分をつくる
以上です