ゼロから始めるLeetCode Day17「66. Plus One」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインでだそうです。

その対策としてLeetCodeなるサイトで対策を行うようです。

※LeetCodeとは
本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトです。

せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていきます。

LeetCode

問題

66. Plus One

整数がdigitsという配列で渡されます。
桁は左から右へ、最上位の桁から最下位の桁の順に並んでいます。
これに1を加えた結果を返す問題。

Example 1:
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:
Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:
Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:
・1 <= digits.length <= 100
・0 <= digits[i] <= 9
・digits does not contain any leading 0's.

解答

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

        for i in range(n - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits
            else:
                digits[i] = 0

        return [1] + digits

解説

for i in range(n - 1, -1, -1)
配列の最後の要素から始まり、最初の要素まで逆順に処理を進める。
引数1番目「n - 1」開始インデックス。
引数2番目「-1」終了インデックス（0まで処理するため）。
引数3番目「-1」1つずつ減少。
if digits[i] < 9:
現在の桁の数字が9より小さい場合
digits[i] += 1
その桁に1を足す。繰り上がりは発生しない。
return digits
結果の配列を返す。

else:
現在の桁が9の場合
digits[i] = 0
1を足すと0になり、1の繰り上がりが発生するので、その桁を0に設定する。

return [1] + digits
新しい要素「1」を配列の先頭に追加して返す。

例①

Input: digits = [4,3,2,1]

i	if digits[i] < 9	digits
0	True → digits[0] += 1	[4,3,2,2]

return digits　→ [4,3,2,2]

例②

Input: digits = [9]

i	if digits[i] < 9	digits
0	False → digits[0] = 0	[0]

return [1] + digits → [1,0]