LeetCode 补充题 21. 字符串相减
题目描述
给定两个表示非负十进制整数的字符串
num1和num2，请计算num1 - num2，并以字符串形式返回结果。结果为负时添加
-，相等时返回"0"，其他结果不保留多余前导零。不能使用内置大整数类型或把整个字符串转换为固定宽度整数后相减。
示例 1：
输入：num1 = "1000", num2 = "1"
输出："999"
示例 2：
输入：num1 = "7", num2 = "20"
输出："-13"
提示：
- 两个输入均为非空字符串，只包含字符
0到9。 - 输入不含多余前导零，不允许使用
BigInteger等内置大整数库。
题意分析
输入两个表示非负整数的十进制字符串，计算第一个数减去第二个数的结果。原题输入为不含多余前导零的非空数字串；本实现额外兼容前导零，输出允许负号，但不保留多余前导零。数值可能超过整数类型范围，因此只转换单个数位，不能整体转成整数。
解法：逐位借位模拟
核心思路
[!blue]
先确定结果符号，再统一计算较大数减较小数。去掉输入的多余前导零后，位数较多的数更大；位数相同时，第一个不同的高位决定大小，所以可以按字典序比较。两数相等直接返回
"0"，否则必要时交换两数，并记录负号。从最低位向最高位计算。
borrow表示低位已经向当前位借走了多少：只能是 0 或 1。因此本位实际要算的是“被减数数位 −borrow− 减数数位”，短串没有的高位按 0 处理。若结果为负，就向更高位借 1，在本位补上 10，并把下一轮的
borrow设为 1；否则设为 0。借出的一个高位单位恰好等于本位的十个单位，数值不变，且得到的当前数位一定在0..9内。已处理的低位不再改变，只需将借位传给下一位，因此连续借位也遵循同一规则。因为已经保证较大数减较小数，处理完较大数的所有位后不会剩余借位。缓冲区按低位到高位写入，最后反转并去掉多余前导零，再根据记录添加负号。去零始终保留至少一位，相等情况又已提前返回，因此不会产生空串或负零。
解题步骤
- 去掉两个输入的前导零；相等则返回
"0"。- 先按长度、再按字典序比较。若第一个数较小，交换两数并记录结果为负。
- 从右向左逐位相减，短串缺失的高位按 0 处理；当前位不够减就加 10，并令
borrow = 1。- 反转缓冲区，去掉结果前导零，最后按标记添加负号。
代码实现
class Solution {
public String subtract(String num1, String num2) {
num1 = stripLeadingZeros(num1);
num2 = stripLeadingZeros(num2);
if (num1.equals(num2)) {
return "0";
}
boolean negative = false;
// 规范前导零后比较大小，统一用大数减小数，符号留到最后。
if (compare(num1, num2) < 0) {
String value = num1;
num1 = num2;
num2 = value;
negative = true;
}
StringBuilder builder = new StringBuilder();
int i = num1.length() - 1;
int j = num2.length() - 1;
int borrow = 0;
while (i >= 0) {
int digit = num1.charAt(i) - '0' - borrow;
int subtrahend = j >= 0 ? num2.charAt(j) - '0' : 0;
// 当前位不够减时向高位借 1，本位实际加 10。
if (digit < subtrahend) {
digit += 10;
borrow = 1;
} else {
borrow = 0;
}
builder.append(digit - subtrahend);
i--;
j--;
}
String result = stripLeadingZeros(builder.reverse().toString());
if (negative) {
return "-" + result;
}
return result;
}
private int compare(String first, String second) {
if (first.length() != second.length()) {
return first.length() - second.length();
}
return first.compareTo(second);
}
private String stripLeadingZeros(String value) {
int idx = 0;
while (idx + 1 < value.length() && value.charAt(idx) == '0') {
idx++;
}
return value.substring(idx);
}
}
func subtract(num1 string, num2 string) string {
num1 = stripLeadingZeros(num1)
num2 = stripLeadingZeros(num2)
if num1 == num2 {
return "0"
}
negative := false
// 规范前导零后比较大小，统一用大数减小数，符号留到最后。
if compareDecimalStrings(num1, num2) < 0 {
num1, num2 = num2, num1
negative = true
}
digits := make([]byte, 0, len(num1))
i, j := len(num1)-1, len(num2)-1
borrow := 0
for i >= 0 {
digit := int(num1[i]-'0') - borrow
subtrahend := 0
if j >= 0 {
subtrahend = int(num2[j] - '0')
}
// 当前位不够减时向高位借 1，本位实际加 10。
if digit < subtrahend {
digit += 10
borrow = 1
} else {
borrow = 0
}
digits = append(digits, byte(digit-subtrahend)+'0')
i--
j--
}
for left, right := 0, len(digits)-1; left < right; left, right = left+1, right-1 {
digits[left], digits[right] = digits[right], digits[left]
}
result := stripLeadingZeros(string(digits))
if negative {
return "-" + result
}
return result
}
func compareDecimalStrings(first string, second string) int {
if len(first) != len(second) {
return len(first) - len(second)
}
for idx := 0; idx < len(first); idx++ {
if first[idx] != second[idx] {
return int(first[idx]) - int(second[idx])
}
}
return 0
}
func stripLeadingZeros(value string) string {
idx := 0
for idx+1 < len(value) && value[idx] == '0' {
idx++
}
return value[idx:]
}
复杂度分析
- 时间复杂度：$O(n + m)$，
n、m为两个输入串的长度，规范化、比较和逐位相减都只需线性扫描。- 空间复杂度：$O(\max(n,m))$，用于结果缓冲区。
关键点总结
[!green]
- 比较大小前先去掉前导零，才能用长度和字典序判断数值大小。
- 借位从低位传向高位，当前位先扣旧借位，再决定下一位的新借位。
- 输入去零服务于数值比较，输出去零服务于结果规范化，二者目的不同。
易错点总结
[!yellow]
- 用
long转换会在超长输入上溢出，失去字符串运算的意义。- 长度不等时直接按字典序比较，可能把数值大小判断反。
- 每轮都要重新设置
borrow；既不能漏扣低位传来的借位，也不能让已经结束的借位继续传播。- 去前导零时至少保留一个字符，否则
"0"会变成空串。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 415. 字符串相加 | 简单 | 同样从低位处理，本题需要先比较大小并模拟借位，原题模拟进位。 |
| 补充题 10. 36 进制减法 | 中等 | 框架相同，三十六进制版本只改变数码映射和借位基数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！