题解 | #给数组加一#
给数组加一
http://www.nowcoder.com/practice/e20d6e18e75941b6a5b7b33ffa7b8d4d
题意：
给定一个用数组表示的数字，即数组中每个数表示一个数位上的数，例如 [1,2,3]，表示 123 ，请问给这个数字加一后得到的结果（结果同样以数组的形式返回）。
注意：数组中不可能出现负数，且保证数组的首位即数字的首位不可能是 0 。
方法一：
直接模拟
思路：将数组逆序遍历，模拟加一操作。
要新增一个数组实现。
class Solution {
public:
vector<int> plusOne(vector<int>& nums) {
vector<int> res;
int flag=1;//进位
for(int i=nums.size()-1;i>=0;i--){//逆向遍历
res.push_back((nums[i]+flag)%10);
if(nums[i]+flag>9){//判断进位
flag=1;
}else{
flag=0;
}
}
if(flag){//判断进位
res.push_back(1);
}
reverse(res.begin(),res.end());//逆序
return res;
}
};
时间复杂度：%2C%E9%81%8D%E5%8E%86%E6%95%B0%E7%BB%84%E3%80%82)
空间复杂度：%2C%E4%B8%80%E7%BB%B4%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
方法二：
原地模拟
思路：原地操作原数组模拟加法操作。
特殊之处：最后需要逆序，判断进位，再逆序。
class Solution {
public:
vector<int> plusOne(vector<int>& nums) {
int flag=1;//进位
for(int i=nums.size()-1;i>=0;i--){//逆向遍历
if(nums[i]+flag>9){//判断进位
nums[i]=(nums[i]+flag)%10;
flag=1;
}else{
nums[i]=(nums[i]+flag)%10;
flag=0;
}
}
reverse(nums.begin(),nums.end());//逆序
if(flag){//判断进位
nums.push_back(1);
}
reverse(nums.begin(),nums.end());//逆序
return nums;
}
};
时间复杂度：空间复杂度：%2C%E5%B8%B8%E6%95%B0%E7%BA%A7%E5%88%AB%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
上海得物信息集团有限公司公司福利 1166人发布
