LeetCode66. 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:

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

Example 2:

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

思路

  1. 最后一位不是9,不会进位,直接加1
  2. 最后一位是9,变0 ,看倒数第二位,所以可能要递归?

My code in c++

16 ms 9.8 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 vector<int> plusOne(vector<int>& digits) {
//3.忘了考虑首位是9的情况!
if (digits.size() == 1&& digits.back() == 9)
{
return{ 1,0 };
}

if (digits.back() != 9)
{
digits.back() += 1;
return digits;
}
else
{
digits.erase(digits.end() - 1);//1.是迭代器啊!!不是左值!!

digits=plusOne(digits);//2.只是算前面进位的数
digits.push_back(0);//最后0添上
return digits;
}
}

细节

  1. v.erase(auto it)不是左值,是返回迭代器,不要乱用!
  2. 递归只是算的前面的值,不能直接返回,会错的,还要加上后面的0!
  3. 开始忘了考虑首位是9的情况,后来想了一个聪明的方法,开始就判断是不是只有一位而且是9,如果是的话,返回{1,0}就好了!!
  4. 因为用到了递归,所以性能不好。

LC in c++

12 ms 8.5 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> plusOne(vector<int> &digits) {   //未考虑前缀0的情况
for(int i = digits.size() - 1; i >= 0; i--)
{
if(digits[i] != 9)
{
digits[i] ++;
break;
}
digits[i] = 0;
}
if(digits[0] == 0)
digits.insert(digits.begin(), 1);//3.
return digits;
}

细节

  1. 这个方法是用迭代做的
  2. 从最后一个数开始往前,如果不是9就直接+1;是9就要设0,迭代;直到index==0为止
  3. 最后检查,如果digits[0],说明最高位是9,进位了,所以在前面插入一个1就好。注意插入语法是v.insert(it,val);在it前面插入val

总结

  • 看到lc上的好多回答都是按数学的方法做的,又要取余乘10啊,不机智啊。
  • 我的方法直接当作动态数组就好了,但是缺点是要用到递归
  • LC的高手方法是用迭代,比我的方法好!!
Thanks for Support.