Help us understand the problem. What is going on with this article?

LeetCode / Plus One

More than 1 year has passed since last update.

ブログ記事からの転載)

[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) と処理します。

mhiro216
経営コンサルタント→データサイエンティスト→データサイエンスの当たり前化を目指すベンチャーのCTO。工学修士/経営学修士。 好きな言葉: Live as if you were to die tomorrow. Learn as if you were to live forever.
https://mhiro216.hatenablog.com/
nishika
データサイエンスコンペティションを軸に、データサイエンティストと、データサイエンスを必要とする人をつなぐコミュニティプラットフォームを提供
https://www.nishika.com
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away