LeetCode / Plus One

https://leetcode.com/problems/plus-one/

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:
Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

これまで解説してきた中では一番簡単な問題？listを結合させたintegerに+1し、listに戻して返す問題です。
あまり意識しなくても解けますが、You may assume the integer does not contain any leading zero, except the number 0 itself.は、leading zeroが桁数を揃えるための0の意味（042とか035とか）なので、そのような0はないよ、と言っています。

解答・解説

解法1

まずは私の解答を示します。

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        return [int(i) for i in str(int(''.join([str(j) for j in digits]))+1)]

見たまんまですが、listをintに変換し+1して、一旦strにしてlistに分解した後に、各要素をintに戻してやっています。
[1, 2, 3] -> 123 -> 124 -> '124' -> ['1', '2', '4'] -> [1, 2, 4]
という順序ですね。

Pythonらしくmapで型変換することも当然できます。

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        return map(int, list(str(int(''.join(map(str, digits))) + 1)))

ただ、何度かsubmitしてみた感じでは型変換の方が計算は若干遅いみたいです。

解法2

解法1はlistの全要素を変換していますが、実際には下一桁の要素が8以下なら+1して変化するのは下一桁の要素1つだけなので、以下のように計算量を減らすことができます。

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits)):
            if digits[~i] < 9:
                digits[~i] += 1
                return digits
            digits[~i] = 0
        return [1] + [0] * len(digits)

例外処理について、値が9の桁は+1することで繰り上がりその桁は0になるので、digits[~i] = 0　と処理します。
999のように全ての桁が9の場合、桁が増えるので、return [1] + [0] * len(digits)　と処理します。