加一
难度:
标签:
题目描述
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入：digits = [1,2,3] 输出：[1,2,4] 解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1] 输出：[4,3,2,2] 解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0] 输出：[1]
提示：
1 <= digits.length <= 1000 <= digits[i] <= 9
代码结果
运行时间: 40 ms, 内存: 14.8 MB
/*
* 题目思路：
* 使用Java Stream实现加一操作。
* 由于Stream不支持原地修改，需要将结果收集为新的数组。
* 依然需要从后向前处理数组元素，并考虑进位问题。
*/
import java.util.stream.IntStream;
public int[] plusOne(int[] digits) {
int carry = 1;
for (int i = digits.length - 1; i >= 0; i--) {
int sum = digits[i] + carry;
digits[i] = sum % 10;
carry = sum / 10;
}
if (carry == 0) {
return digits;
}
int[] newNumber = new int[digits.length + 1];
newNumber[0] = 1;
return newNumber;
}解释
方法:
这个题解的思路是先在数组最前面添加一个0作为进位标志，然后从数组末尾开始遍历。如果当前位不为9，直接加1然后结束遍历；如果当前位为9，则将其置为0，继续遍历前一位。最后根据最前面的进位标志是否为0，决定是否要将其去掉。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么需要在数组最前面添加一个0作为进位标志，而不是直接在原数组上进行操作？
▷🦆
在处理最高位进位时，如果数字全部是9（例如[9,9,9]），这种方法是否能正确处理并返回正确的结果，如[1,0,0,0]？
▷🦆
代码中有一个break语句，在某些情况下直接终止循环。这是否意味着不是所有的元素都需要检查或修改？请解释这种情况。
▷🦆
如果初始数组的所有位都是9，如[9, 9, 9, 9]，请详细说明算法是如何处理这种情况的。
▷相关问题
字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3" 输出: "6"
示例 2:
输入: num1 = "123", num2 = "456" 输出: "56088"
提示：
1 <= num1.length, num2.length <= 200num1和num2只能由数字组成。num1和num2都不包含任何前导零，除了数字0本身。
二进制求和
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
输入:a = "11", b = "1" 输出："100"
示例 2：
输入：a = "1010", b = "1011" 输出："10101"
提示：
1 <= a.length, b.length <= 104a和b仅由字符'0'或'1'组成- 字符串如果不是
"0"，就不含前导零
数组形式的整数加法
整数的 数组形式 num 是按照从左到右的顺序表示其数字的数组。
- 例如，对于
num = 1321，数组形式是[1,3,2,1]。
给定 num ，整数的 数组形式 ，和整数 k ，返回 整数 num + k 的 数组形式 。
示例 1：
输入：num = [1,2,0,0], k = 34 输出：[1,2,3,4] 解释：1200 + 34 = 1234
示例 2：
输入：num = [2,7,4], k = 181 输出：[4,5,5] 解释：274 + 181 = 455
示例 3：
输入：num = [2,1,5], k = 806 输出：[1,0,2,1] 解释：215 + 806 = 1021
提示：
1 <= num.length <= 1040 <= num[i] <= 9num不包含任何前导零，除了零本身1 <= k <= 104