いいものをつくろう

CTOの日記

アルゴリズム

leetcode medium remove duplicate from sorted linked list ii

投稿日:

こんにちは

今回の学びは

・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)ですね

今回の実装は実はデバッグに2時間くらいかかってしまいました。

入力と出力の意識が低かったからでしょう。以下のように入力rootをそのまま出力して、サンプルケース2がなかなか通らずに

並んでおりました。インプレースで得問題でしたので、そこで勘違いが発生していたようです

print(nodeToString(root))
Solution().deleteDuplicates(root)
print(nodeToString(root))

たわしはこのような勘違いが少なくない人です

ということでぐぐりました => 勘違いをなくす方法がびっくりするほど自分に当てはまっていたので

自分は思い込みが強いほうだと意識して、丁寧に情報を入力していこうと

思いました。情報を取り込みながら、あ、これはこういうことでしょう!?早合点とか

次に喋りたいことばっかりきになったり、正解のときはそれは悪いことにならないけど

自分の中の自分でチェックしてくれるもうひとりの自分が必要だと感じました

まとめ

whileですすませるパターン

もうひとりのダブルチェックをしてくれる確認する自分をつくる

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.