【アルゴリズム脳トレ】leetcode medium 19 remove nth from end

こんにちは

今回の学びは

・ソートされた配列と二分木はよく似てるよ。

・できれば二分木探索を配列で実装していて 🙂

問題は。。。

（時間配分は5分問題理解　10分検討 10分実装  20分振り返り　の一文45分構成)

まずは入出力をしっかりおさえましょう。

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は　O(N*２）

実際の実装はこちら

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        curr = head
        i = 0
        while curr:
            curr = curr.next
            i += 1
        sz = i
        target = sz - (n)
        print(sz, target)
        if target == 0 and sz == 1: return None
        i = 0
        if target == 0 and sz >= 2:
            head = head.next
            return head
        curr = head
        while curr:
            if i == target-1:
                curr.next = curr.next.next if curr.next else None
                curr = curr.next
            else:
                curr = curr.next
            i += 1
        return head

実装後です。timespace analysis (時間とスペースの分析）は　O(N*2)

1116am 途中別のことをしたのでタイムロス、しかし場合分けが多い問題は実装が疲れるな。
なんとかならんかねぇ。
one passでもできるらしいだけど、それは、配列にnode記憶していって、やる。かな。

配列のほうが、実装しやすいかな。以外に場合分けが大変だったよ。。。

one passソリューションをながめましょう。

https://leetcode.com/problems/remove-nth-node-from-end-of-list/discuss/392049/Python-one-pass-solution-easy-to-understand-faster-than-96 。およ、パット見てわからん。別の機会にもう一度、ながめよう。

上ににたようなjava https://leetcode.com/problems/remove-nth-node-from-end-of-list/discuss/384628/Simple-Java-O(n)-solution-one-pass-for-slow-learners-like-myself

今日はしつれいします。

まとめ

以上です