题目:
解题思路:
最初思路是打算将数组中的数提出来,加一,再放回另一数组中。后来发现数组最大长度100,而100位的数字太大了。
所有在数组上实现加一。
利用 carry 标记每一位是否进位,即该位数加 carry ,再对10取余作该位新数,同时除以10作新 carry 再判断上一位。 最终对首位需要分两种情况。
- 首位无进位,新的 carry 就是加一后的结果
- 首位有进位,定义新数组,比 digits 要多一个元素,且首位为1
时间复杂度: ,其中 n 是数组的长度
空间复杂度:
int* plusOne(int* digits, int digitsSize, int* returnSize) {int carry = 1; for (int i = digitsSize - 1; i >= 0; i--) {int sum = digits[i] + carry;digits[i] = sum % 10;carry = sum / 10;}if (carry == 0) {*returnSize = digitsSize;return digits;}*returnSize = digitsSize + 1;int *res = (int *)malloc(*returnSize * sizeof(int));res[0] = carry;for (int i = 1; i < *returnSize; i++) {res[i] = digits[i - 1];}return res;
}