[LeetCode] 66. 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:
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Example 2:
Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
一个非负数字存在一个数组里,高位在前面,给这个数加一。
解法1:从数组的最后一位开始加1,如果是不是9,就直接加1后返回目前的数就可以了。如果是9,最后一位加1后为0进位为1,下一个数也是9加1后为0进位为1,如果在加的过程中有哪一位不是9,那么就加1后返回当前数。如果一直到最高位都是9,当前位变成了0,然后在前面多加个1。由于数组只能在后面添加数字,所以可以把第一个数变为1,最后加一个0;也可以在建一个数组长度比原来多1的数组,第一个元素为1, 其它元素为0。
解法2:由于数组添加一位数字要在最后,为了方便操作先把数字逆序,然后用取余、取模操作来算当前位的值和进位,最后在逆序输出返回。
Java:
public int[] plusOne(int[] digits) { int n = digits.length;
for(int i=n-1; i>=0; i--) {
if(digits[i] < 9) {
digits[i]++;
return digits;
} digits[i] = 0;
} int[] newNumber = new int [n+1];
newNumber[0] = 1; return newNumber;
}
Java:
public class Solution {
public int[] plusOne(int[] digits) {
int n = digits.length;
for (int i = digits.length - 1; i >= 0; --i) {
if (digits[i] < 9) {
++digits[i];
return digits;
}
digits[i] = 0;
}
int[] res = new int[n + 1];
res[0] = 1;
return res;
}
}
Java:
class Solution {
public int[] plusOne(int[] digits) {
if (digits.length == 0) return digits;
int carry = 1;
for (int i = digits.length - 1; i >= 0; --i) {
if (carry == 0) return digits;
int sum = digits[i] + carry;
digits[i] = sum % 10;
carry = sum / 10;
} if (carry == 0) return digits; int[] res = new int[digits.length + 1];
res[0] = 1;
for (int i=1, i < res.length; i++) {
rest[i] = digits[i - 1];
} return res;
}
}
Python:
# in-place solution
class Solution(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
for i in reversed(xrange(len(digits))):
if digits[i] == 9:
digits[i] = 0
else:
digits[i] += 1
return digits
digits[0] = 1
digits.append(0)
return digits
Python:
# Time: O(n)
# Space: O(n)
class Solution2(object):
def plusOne(self, digits):
"""
:type digits: List[int]
:rtype: List[int]
"""
result = digits[::-1]
carry = 1
for i in xrange(len(result)):
result[i] += carry
carry, result[i] = divmod(result[i], 10)
if carry:
result.append(carry)
return result[::-1]
C++: In place, Time: O(n), Space: O(1)
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
for (int i = digits.size() - 1; i >= 0; --i) {
if (digits[i] == 9) {
digits[i] = 0;
} else {
++digits[i];
return digits;
}
}
digits[0] = 1;
digits.emplace_back(0);
return digits;
}
};
C++: Time: O(n), Space: O(n)
class Solution2 {
public:
vector<int> plusOne(vector<int>& digits) {
vector<int> result(digits.rbegin(), digits.rend());
int carry = 1;
for (auto& num : result) {
num += carry;
carry = num / 10;
num %= 10;
}
if (carry == 1) {
result.emplace_back(carry);
}
reverse(result.begin(), result.end());
return result;
}
};
类似题目:
[LeetCode] 67. Add Binary 二进制数相加
[LeetCode] 369. Plus One Linked List 链表加一运算
All LeetCode Questions List 题目汇总
最新文章
- 【原创】SQL审核系统
- Apache FtpServer扩展【动手实现自己的业务】
- maven缺少依赖包,强制更新命令
- [iOS 多线程 &; 网络 - 1.2] - 多线程GCD
- UVa 10900 So you want to be a 2n-aire? (概率DP,数学)
- string 对象及其操作
- 【BZOJ2318】【spoj4060】game with probability Problem 概率DP
- Struts2 ValueStack
- 在Wamp 添加站点和域名
- OpenGL教程(2)——第一个窗口
- JAVA字符串操作 (转)
- Android 内存暴减的秘密?!
- springboot情操陶冶-web配置(二)
- day3-->;深浅拷贝
- sqlserver添加查询 表、字段注释(转)
- 基于HttpClient JSONObject与JSONArray的使用
- [COGS 2064]爬山
- struts2学习(9)struts标签2(界面标签、其他标签)
- Python 抓取html所有特定元素的方法
- es6 数组扩展方法