leetcode easy remove duplicate from sorted array ii

こんにちは

今回の学びは

・紙の上のデバッグも形式化することと練習反復でスペードを上げよう

問題は前回のleetcode easy remove duplicate from sorted array　の条件がすこしかわっただけ

なので少しの修正が行けるような気がします

がなかなか腰がおもかったですw

実装前後でこれは毎回書きましょう。timespace anaylysis (時間とスペースの分析）は　操作パス一発なのでO(n)です

メモリはi, jの変数くらいなのでO(1)です

pseudocode（擬似コード）をかいてみますか。

j = 0 # write pointer
pre = S[0]
for i, x in S:
  if x == pre: # duplicate
     pass
  else:
     S[j] = x
     j+=1

シンプルですね。たぶん動くでしょう。

で、最初に提出したコードはこちら、ですがサンプルケースで通りません。なにが問題かわかりますでしょうか。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 1 # write pointer
        if nums == None or len(nums) == 0: return 0
        pre = nums[0]
        dup = 0
        dup_pre = None
        for i, x in enumerate(nums):
            if i == 0:
                pass
            elif x == pre: # duplicate
                if x != dup_pre:
                    dup += 1
                dup_pre = x
            else:
                nums[j] = x
                j+=1
            pre = x
        return dup

間違いは、重複の数をかえすのではなく、重複を取り除いたあとの配列の長さをかえすべきだったのです。

前回のコードで未使用変数とかは削除して

すこしスッキリした感じでかけました。

しかしながら一発でサンプルケースはとおらず

最後の書き換えが上手くいっていませんでした。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 0 # write pointer
        if nums == None or len(nums) == 0: return 0
        pre = None
        dup = 0
        for i in range(len(nums)):
            if nums[i] == pre: # duplicate
                dup += 1
                if dup < 2:
                    j+=1
                nums[j] = nums[i]
            else:
                dup = 0
                nums[j] = nums[i]
                j+=1
            pre = nums[i]
        return j

samples = [
    #[1,1,1,2,2,3],
    [0,0,1,1,1,1,2,3,3],
]


for sample in samples:
    ans = Solution().removeDuplicates(sample)
    print("ans:%s" % ans)
    print("new array: %s" % sample[:ans])

本番では当然でデバッガーが使えないので、紙の上で

変数をたどることでデバッグしてみました。

すると時間はかかりましたが、

一個一個このひょうを埋めていくのは、頭の回転が遅く牛歩な感じで

自分自身でもおせーな、とつっこみたくなる感じではありましたがなんとかバグをみつけることができました

このように紙の上のデバッグも形式化することと練習反復でスペードを上げれるのではという

ヒントはつかんだので良しとしよう。

はい、ということでjの更新がワンステップはやかったという

ことがわかり、jの繰り上げのif dup < 2を後ろにずらして全てのテストケースが通りパスしました

lass Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 0 # write pointer
        if nums == None or len(nums) == 0: return 0
        pre = None
        dup = 0
        for i in range(len(nums)):
            if nums[i] == pre: # duplicate
                dup += 1
                nums[j] = nums[i]
                if dup < 2:
                    j+=1
            else:
                dup = 0
                nums[j] = nums[i]
                j+=1
            pre = nums[i]
        return j

実装後です。timespace anaylysis (時間とスペースの分析）は　◯◯　O(n) and space is O(1)

以上です