NC180. 给数组加一
描述
示例1
输入:
[1,2,3]
输出:
[1,2,4]
示例2
输入:
[1,9]
输出:
[2,0]
示例3
输入:
[9]
输出:
[1,0]
C++ 解法, 执行用时: 2ms, 内存消耗: 412KB, 提交时间: 2021-11-29
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型vector
*/
vector<int> plusOne(vector<int>& nums) {
// write code here
int n=nums.size()-1;
while(nums[n]==9&&n>=0){
nums[n]=0;
--n;
}
if(n>=0) nums[n]+=1;
else nums.insert(nums.begin(),1);
return nums;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 384KB, 提交时间: 2022-01-28
class Solution {
public:
/*
方法一：找出最长的后缀 9 - 思路清晰
思路
当我们对数组 digits 加一时，我们只需要关注 digits 的末尾出现了多少个 9 即可。
我们可以考虑如下的三种情况：
1. 如果 digits 的末尾没有 9，例如 [1,2,3]，那么我们直接将末尾的数加一，得到 [1,2,4] 并返回；
2. 如果 digits 的末尾有若干个 9，例如 [1,2,3,9,9]，那么我们只需要找出从末尾开始的第一个不为 9 的元素，即 3，
将该元素加一，得到 [1,2,4,9,9]。随后将末尾的 9 全部置零，得到 [1,2,4,0,0] 并返回。
3. 如果 digits 的所有元素都是 9，例如 [9,9,9,9,9]，那么答案为 [1,0,0,0,0,0]。
我们只需要构造一个长度比 digits 多 1 的新数组，将首元素置为 1，其余元素置为 0 即可。
复杂度分析
时间复杂度：O(n)，其中 n 是数组 digits 的长度。
空间复杂度：O(1)。返回值不计入空间复杂度。
*/
vector<int> plusOne(vector<int>& digits) {
int n = digits.size();
for (int i = n - 1; i >= 0; --i) {
if (digits[i] != 9) {
++digits[i];
for (int j = i + 1; j < n; ++j) {
digits[j] = 0;
}
return digits;
}
}
// digits 中所有的元素均为 9
vector<int> ans(n + 1);
ans[0] = 1;
return ans;
}
/*
方法二：进位计算 - 太妙了！
加一的所有可能的情况就只有两种：
1. 除 9 之外的数字加一；
2. 数字 9。
思路
1. 加一得十进一位个位数为 0 加法运算如不出现进位就运算结束了且进位只会是一。
2. 所以只需要判断有没有进位并模拟出它的进位方式，如十位数加 1 个位数置为 0，
如此循环直到判断没有再进位就退出循环返回结果。
3. 然后还有一些特殊情况就是当出现 99、999 之类的数字时，
循环到最后也需要进位，出现这种情况时需要手动将它进一位。
复杂度分析
时间复杂度：O(n)，其中 n 是数组 digits 的长度。
空间复杂度：O(1)。返回值不计入空间复杂度。
*/
vector<int> plusOne2(vector<int>& digits) {
for (int i = digits.size() - 1; i >= 0; i--) {
digits[i]++;
digits[i] = digits[i] % 10;
if (digits[i] != 0) return digits;
}
vector<int> ans(digits.size() + 1);
ans[0] = 1;
return ans;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 388KB, 提交时间: 2021-11-27
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型vector
*/
vector<int> plusOne(vector<int>& nums) {
// write code here
int n=nums.size()-1;
while(nums[n]==9&&n>=0){
nums[n]=0;
--n;
}
if(n>=0) nums[n]+=1;
else nums.insert(nums.begin(),1);
return nums;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2022-07-29
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型vector
*/
vector<int> plusOne(vector<int>& nums) {
// write code here
int size = nums.size() - 1;
int flag = 1;
do {
int sum = nums[size] + flag;
flag = sum / 10;
nums[size] = sum % 10;
size--;
} while (flag > 0 && size >= 0);
if (flag) {
vector<int> result;
result.push_back(flag);
for (int i = 0 ; i < nums.size(); i++) {
result.push_back(nums[i]);
}
return result;
}
return nums;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2022-01-24
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型vector
*/
vector<int> plusOne(vector<int>& nums) {
// write code here
for(int i=nums.size()-1;i>=0;i--){
if(nums[i]==9)
nums[i]=0;
else{
nums[i]++;
break;
}
}
if(nums[0]==0)
nums.insert(nums.begin(), 1);
return nums;
}
};