LeetCode 415
int x = i >= 0 ? num1.charAt(i) - '0' : 0;
int y = j >= 0 ? num2.charAt(j) - '0' : 0;
int result = x + y + add;
ans.append(result % 10);
add = result / 10;
i--;
j--;
}
// 计算完以后的答案需要翻转过来
ans.reverse();
return ans.toString();
}
}
* 时间复杂度：
O
(
max
(
len
1
,
len
2
)
)
O(\max(\textit{len}\_1,\textit{len}\_2))
O(max(len1,len2))，其中
len
1
=
num
1
.
length
\textit{len}\_1=\textit{num}\_1.\text{length}
len1=num1.length，
len
2
=
num
2
.
length
\textit{len}\_2=\textit{num}\_2.\text{length}
len2=num2.length。竖式加法的次数取决于较大数的位数。
* 空间复杂度：
O
(
n
)
O(n)
O(n)。在 `Java` 解法中使用到了 `StringBuffer`，故 `Java` 解法的空间复杂度为
O
(
n
)
O(n)
O(n)。
## 补充：字符串相加（36进制）
### 题目
### 模拟
掌握十进制的大数相加后，那本题只需要注意将`10`变成`36`，以及`36`进制字符与数值的转换。
使用了`getChar(int n)`和`getInt(char ch)`两个辅助函数来完成`36`进制字符与数值的转换
// 数值 -> 36进制字符
public char getChar(int n) {
if (n <= 9) {
return (char)(n + ‘0’);
} else {
return (char)(n - 10 + ‘a’);
}
}
// 36进制字符 -> 数值
public int getInt(char ch) {
if (‘0’ <= ch && ch <= ‘9’) {
return ch-‘0’;
} else {
return ch-‘a’+10;
}
}
public String add36Strings(String num1, String num2) {
char[] chars1 = num1.toCharArray();
char[] chars2 = num2.toCharArray();
// 双指针分别指向末尾，即最低位
int i = chars1.length - 1;
int j = chars2.length - 1;
// 进位
int carry = 0;
StringBuilder sb = new StringBuilder();
while (i >= 0 || j >= 0 || carry != 0) {
// 对位数较短的数字进行补零操作
int x = i >= 0 ? getInt(chars1[i]) : 0;
int y = j >= 0 ? getInt(chars2[j]) : 0;
int sum = x + y + carry;
sb.append(getChar(sum % 36));
carry = sum / 36;
i–;
j–;
}
// 计算完以后的答案需要翻转过来
sb.reverse();
return sb.toString();
}
## 补充：字符串相减（10进制）
### 题目
### 模拟
两个非负整数相减的结果可能为负。
因此，首先比较两个数的大小。**由于是大数，肯定不能直接转成`int`比较。可以比较两个字符串的长度**。长度更长的字符串，数一定更大；当长度一样的就去比较字典序。
当小减大时，需将两个参数调换一下位置执行减法，在结果前填上`负号`即可注意：结果为0时不加负号。
public class SubString {
/**
* 若a字符串表示的数字小于b字符串表示的数字则返回true
*
* @param a
* @param b
* @return
*/
public static boolean isLess(String a, String b) {
// 由于是大数，考虑转成字符串处理
// 长度更长的字符串，数一定更大
// 当长度一样的就去比较字典序
if (a.length() == b.length()) {
if (a.compareTo(b) < 0) {
return true;
} else if (a.compareTo(b) >= 0) {
return false;
}
}
return a.length() < b.length();
}
/\*\*
* 大数减小数
* @param a
* @param b
* @return
*/
public static String sub(String a, String b) {
StringBuilder ans = new StringBuilder();
int borrow = 0;
int i = a.length() - 1, j = b.length() - 1;
while (i >= 0 || j >= 0) {
int x = i >= 0 ? (a.charAt(i) - ‘0’) : 0;
int y = j >= 0 ? (b.charAt(j) - ‘0’) : 0;
int z = (x - borrow - y + 10) % 10;
ans.append(z);
borrow = x - borrow - y < 0 ? 1 : 0;
i--;
j--;
}
ans.reverse();
// 删除前导零，边界是 ans.length()-1, 防止当 ans 为 "0000" 时，清空
// 121-120=001 需要删除前导0
// 121-121=000 不能把所有 0 都删掉
int pos = 0;
while (pos < ans.length()-1 && ans.charAt(pos) == '0') {
pos++;
}
return ans.toString().substring(pos);
}
/\*\*
* 给定两个字符串形式的非负整数num1和num2，计算它们的差
* 注意：
* num1 和num2 都只会包含数字 0-9
* num1 和num2 都不包含任何前导零
* 你不能使用任何內建 BigInteger 库
* @param a
* @param b
* @return
*/
public static String subString(String a, String b) {
String res;
if (isLess(a, b)) {
res = sub(b, a);
// 结果为 0 时，不加负号
if (res != “0”) {
res = “-” + res;
}
} else {
res = sub(a, b);
}
return res;
}
public static void main(String[] args) {
System.out.println(subString("121", "120"));
System.out.println(subString("121", "121"));
}
}
## 补充：字符串相减（36进制）
### 题目
### 模拟
整体思路与10进制的字符串相减类似
public class Sub36 {
public char getChar(int n) {
if (n <= 9) {
return (char)(n + ‘0’);
} else {
return (char)(n - 10 + ‘a’);
}
}
public int getInt(char c) {
if (c >= '0' && c <= '9') {
return c - '0';
} else {
return c - 'a' + 10;
}
}
public String sub(String a, String b) {
int borrow = 0;
int i = a.length() - 1;
int j = b.length() - 1;
char[] ca = a.toCharArray();
char[] cb = b.toCharArray();
StringBuilder res = new StringBuilder();
while (i >= 0 || j >= 0) {
int x = i >= 0 ? getInt(ca[i]) : 0;
int y = j >= 0 ? getInt(cb[i]) : 0;
int z = (x - borrow - y + 36) % 36;
res.append(getChar(z));
borrow = x - borrow - y < 0 ? 1 : 0;
i--;
j--;
}
res.reverse();
// 删除前导0。注意：循环条件是res.size()-1是为防止"0000"的情况
int pos;
for (pos = 0; pos < res.length() - 1; pos++) {
if (res.charAt(pos) != '0') {
break;
}
}
return res.toString().substring(pos);
}
boolean isLess(String a, String b) {
if (a.length() == b.length()) {
return a.compareTo(b) < 0;
}