02
04/2015
[LeetCode] Plus One
Plus One
Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.
解题思路：
这道题倒是挺简单的，但是我最开始没有理解题意（我的英语不好啊），这道题的本意是用一个数组表示一个非负整数，如：[1,0,9]表示109。给这个数组进行加1操作。明白了这个，就容易多了。下面是代码：
class Solution {
public:
vector<int> plusOne(vector<int> &digits) {
int len = digits.size();
vector<int> result;
int over = 1;
for(int i=len-1; i>=0; i--){
int number = digits[i] + over;
over = number / 10;
result.insert(result.begin(), number % 10);
}
if(over>0){
result.insert(result.begin(), over);
}
return result;
}
};注意到vector的insert方法的使用。vector的底层实现是数组，每次给第一个位置加一个元素，就相当于每次都将他后移一位，比较耗时。可以考虑先用栈来保存结果，最后出栈。下面是代码：
class Solution {
public:
vector<int> plusOne(vector<int> &digits) {
int len = digits.size();
int* stack = new int[len+1];
int top = 0;
int over = 1;
for(int i=len-1;i>=0; i--){
int number = digits[i] + over;
over = number/10;
stack[top++] = number%10;
}
if(over>0){
stack[top++] = over;
}
vector<int> result;
while(top>0){
result.push_back(stack[--top]);
}
delete stack;
return result;
}
};二次刷题2015-10-10
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int len = digits.size();
vector<int> result(len);
int over = 1;
for(int i = len-1; i>=0; i--){
int temp = digits[i] + over;
result[i] = temp%10;
over = temp/10;
}
if(over==1){
result.insert(result.begin(), 1);
}
return result;
}
};转载请注明：康瑞部落 » [LeetCode] Plus One
0 条评论