# LeetCode Easy 66. Plus One

tags: leetcode

問題

• Explore
• Problems

アイデア

空でない配列のそれぞれの要素が1つの非負整数を表現しているとします．このとき，この配列に1を足した数を表現する配列を返せという問題です．ただし，配列の先頭の要素が最上位の数を表します．

例えば，[1, 2, 3]は123という整数を表し，この配列が与えられた時は[1, 2, 4]を返します．

0以外で先頭に0が来ることはないと仮定して良いです．

条件分岐に気を付けて解きます．

解法

• 桁上がりを保持する変数を用意します．
  • carryなどと名前を付け，1で初期化します．
• 最下位の要素から見ていきます．
  • 9以外ならば，それより先で桁上がりは起きないのでcarryに0を代入します.そして，ここで値の変化は終わりです
  • 9ならば，その値を0にして上位の要素を見ます．
• 最後に桁上がりの変数に1が入っていた場合，先頭に1を追加します．
  • 9が10になる場合など

計算量

配列の大きさをNとします．

• 時間計算量
  • 最悪，全ての要素を調べることに成るので$O(N)$
• 空間計算量
  • 新しい新たな配列を使用しないので$O(1)$

C++

class Solution {
public:
  vector<int> plusOne(vector<int>& digits) {
    int carry = 1;
    for (auto iter = digits.rbegin(); iter != digits.rend(); iter++) {
      if (*iter != 9) {
        (*iter)++;
        carry = 0;
        break;
      } else {
        *iter = 0;
      }
    }
    if (carry)
      digits.insert(digits.begin(), 1);
    return digits;
  }
};