【名前がわからない】PlusOneアルゴリズムを理解した

解いた問題

LeetCode 66. Plus One
123のような数値が[1,2,3]というリスト形式で渡されるからそれに1を足して[1,2,4]を返してねって問題
数字が9だった時どうしよっかを考える必要がある。

最初考えた解法

python before.py

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        if not digits:
            return 0

        i = len(digits) - 1
        if digits[i] != 9:
            digits[i] += 1
            return digits
        else:
            digits[i] = 0
            while digits[i-1] == 9:
                digits[i-1] = 0
                i -= 1
                if i < 0:
                    digits.insert(0, 1)
            digits[i-1] += 1
        return digits

最後尾インデックスの値が9か9以外かで場合分けして、9以外なら単純に1足してreturn、9なら一個前のインデックスを見て同様の判断を下し、全部9だったらリストの一番最初に1を挿入、他を0にしてreturnという処理をしたくて書いた。

しかし[9]のようなものが来たとき[1,0]になるよう作ったつもりが、そもそもiの1個前のインデックスがないときwhile文が回らずdigits[i-1]がdigits[-1]となり、最後尾インデックスに+1するというコードになっているから[1]が出力されるという間抜けなコード。

最適解

python after.py

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        i = len(digits) - 1

        while i >= 0:
            if digits[i] < 9:
                digits[i] += 1
                return digits
            digits[i] = 0
            i -= 1
        return [1] + digits

発想は同じだが最小コードで実現している。

俺のコードとの違いはwhile内ですべての処理が完結していること、リストの扱いとして+でつなげば簡単に頭とケツには結合ができること。
あとは9以外を!=ではなく<で表していること。こっちのほうが文字数が少ないしぱっと見何しているかわかりやすいなと。

自分で書いたときwhileの条件をどうしようか迷ったが、「起きてはいけない状態」を考えて、それが起きないぎりぎりまで処理を回すことを考えるとスッと出てくるものなのかなと仮説。

感想

美しいと思った。
自分が書いたコードと比較して無駄が一切なく、洗練されている印象。

自分で書けるようになりて～