本文的目的是记录下一个leetcode算法题的求解过程。
题目：加一
说明：给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3]示例 2:
输入: [4,3,2,1]求解过程：
第一次提交：
class Solution {
public:
vector<int> plusOne(vector<int>& digits)
{
int len = digits.size();
int c = 0;
for(int i = len-1;i >= 0;i--)
{
digits[i] += (1 + c);
if(digits[i] < 10){c=0;break;}
if(digits[i] >= 10)
{
digits[i] -= 10;c=1;
}
if(c)
digits.push_back(c);
for(int i = len;i > 0;i--)
{
digits[i] = digits[i-1];
}
digits[0] = c;
return digits;
}
};
提交之后提示如下：
sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 *(sizeof(size_t))) - 1)) & ~((2 *(sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long) old_end & pagemask) == 0)' failed.
看提示大概的意思是数组越界了，仔细检查，发现了源代码中的红色部分是有问题的，因为只有c为1时，红色部分为len是对的，而c为0时，红色部分是不对的。
第二次提交：
class Solution {
public:
vector<int> plusOne(vector<int>& digits)
{
int len = digits.size();
int c = 0;
for(int i = len-1;i >= 0;i--)
{
digits[i] += (1 + c);
if(digits[i] < 10){c=0;break;}
if(digits[i] >= 10)
{
digits[i] -= 10;c=1;
}
}
if(c)
{
digits.push_back(c);
}
for(int i = digits.size()-1;i > 0;i--)
{
digits[i] = digits[i-1];
}
digits[0] = c;
return digits;
}
};
执行结果提示：
之所以还报错是因为，当c为0的时候，不应该再进行数组元素右移和把c赋值给新数组首元素。
优化后第三次提交：
static int __initialSetup = [] {
ios::sync_with_stdio(false); // toggle off cout & cin, instead, use printf & scanf
cin.tie(nullptr); // untie cin & cout
return 0;
}();
class Solution {
public:
vector<int> plusOne(vector<int>& digits)
{
int len = digits.size();
int c = 0;
for(int i = len-1;i >= 0;i--)
{
digits[i] += (1 + c);
if(digits[i] < 10){c=0;break;}
if(digits[i] >= 10)
{
digits[i] -= 10;c=1;
}
}
if(c)
{
digits.push_back(c);
for(int i = digits.size()-1;i > 0;i--)
{
digits[i] = digits[i-1];
}
digits[0] = c;
}
return digits;
}
};
执行结果提示：
这次的错误出现在了红色部分，只有个位加1就可以了，而红色部分代表的逻辑是每一位都加1。
再次优化提交：
static int __initialSetup = [] {
ios::sync_with_stdio(false); // toggle off cout & cin, instead, use printf & scanf
cin.tie(nullptr); // untie cin & cout
return 0;
}();
class Solution {
public:
vector<int> plusOne(vector<int>& digits)
{
int len = digits.size();
int c = 0;
for(int i = len-1;i >= 0;i--)
{
if(i == len-1)
{
digits[i] += (1 + c);
}else{
digits[i] += (c);
}
if(digits[i] < 10){c=0;break;}
if(digits[i] >= 10)
{
digits[i] -= 10;c=1;
}
}
if(c)
{
digits.push_back(c);
for(int i = digits.size()-1;i > 0;i--)
{
digits[i] = digits[i-1];
}
digits[0] = c;
}
return digits;
}
};
本次执行结果通过：
提示运行时间为0ms。
代码通过后又参考了下别人的代码如下：
class Solution {
public: vector<int> plusOne(vector<int>& digits)
{
int len = digits.size();
for(int i=len-1; i>=0; i--)
{
if (digits[i] == 9)
{
digits[i] = 0;
}
else
{
digits[i]++;
return digits;
}
}
digits[0] = 1;
digits.push_back(0);
return digits;
}
};
该代码的优点是，在最高位需要进位的情况下，没有用移动每一个元素来扩充数组大小。
小结：
本人的代码是基于通用的加法常识来写的，个位数加一个数，这里是 1 ，产生进位则下一位加上进位。
而参考代码是基于本例加法的特点来写的，特点表现，首先，加的是 1，一旦产生进位，则该位就成了 0，不产生进位则加 1 后直接返回；同理，下一位也是如此；
加到最后，如果每一位都产生了进位，那么原数就全是 0 了，那么就要在首部扩充一个数且赋值为 1，只需把首位置 1，尾部添加一个0即可。这样一来就少了移动元素来扩充数组啦，效率提高了。
解决任何问题，都要仔细观察其个性特点，包括技术问题、生活问题..就像本例，我想到的是加法的共性，而参考代码看到了其特性。
联系客服
