LeetCodeに毎日挑戦してみた 66. Plus One(Python、Go)


はじめに

無料英単語サイトE-tanを運営中の@ishishowです。

プログラマとしての能力を上げるために毎日leetcodeに取り組み、自分なりの解き方を挙げていきたいと思います。

Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

golang入門+アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

14問目(問題66)

66. Plus One

問題内容

Given a non-empty array of decimal digits representing a non-negative integer, increment 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 contains a single digit.

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

(日本語訳)

非負の整数を表す空でない10進数の配列が与えられた場合、1を整数にインクリメントします。

数字は、最上位桁がリストの先頭になるように格納され、配列の各要素には1桁が含まれます。

整数には、数値0自体を除いて、先行ゼロは含まれていないと想定できます。

Example 1:

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

Example 2:

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

Example 3:

  Input: digits = [0]
  Output: [1]

考え方

  1. 最後の数字が9か9以外かで判断する

  2. 9以外だったらそのまま、9だったら再帰処理に進む

  3. 再帰処理の値の受け渡しは最後の文字を除いた文字列にする

  4. その後、末尾に0を代入する

  • 解答コード
class Solution(object):
    def plusOne(self, digits):
        if len(digits) == 0:
            digits = [1]
        elif digits[-1] == 9:
            digits = self.plusOne(digits[:-1])
            digits.extend([0])
        else:
            digits[-1] += 1
        return digits
  • Goでも書いてみます!
func plusOne(digits []int) []int {
    if digits[len(digits)-1] != 9 {
        digits[len(digits)-1] += 1
    } else if len(digits) != 1 {
        digits = plusOne(digits[0 : len(digits)-1])
        digits = append(digits, 0)
    } else {
        digits[0] = 1
        digits = append(digits, 0)
    }
    return digits
}