LeetCode 415.字符串相加（大数相加减 10进制/36进制）

LeetCode 415. 字符串相加（10进制）

题目

• 415. 字符串相加

模拟

只需要对两个大整数模拟「竖式加法」的过程。竖式加法就是平常学习生活中常用的对两个整数相加的方法

在纸上对两个整数相加的操作：将相同数位对齐，从低到高逐位相加，如果当前位和超过 10，则向高位进一位

因此只要将这个过程用代码写出来即可

class Solution {public String addStrings(String num1, String num2) {// 双指针分别指向末尾，即最低位，add代表进位int i = num1.length() - 1, j = num2.length() - 1, add = 0;StringBuffer ans = new StringBuffer();while (i >= 0 || j >= 0 || add != 0) {// 对位数较短的数字进行补零操作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 ({\text{len}}_1,{\text{len}}_2))$，其中 ${\text{len}}_1={\text{num}}_1.\text{length}$，${\text{len}}_2={\text{num}}_2.\text{length}$。竖式加法的次数取决于较大数的位数。

• 空间复杂度：$O(n)$。在 Java 解法中使用到了 StringBuffer，故 Java 解法的空间复杂度为 $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;}return a.length() < b.length();}public String subString(String num1, String num2) {if (isLess(num1, num2)) {String res = sub(num2, num1);return "-" + res;}return sub(num1, num2);}public static void main(String[] args) {String num1 = "48";String num2 = "2x";Sub36 sub36 = new Sub36();System.out.println(sub36.subString(num1, num2));}
}

Reference

• 字符串相加

• 36进制加法

• 字符串相减（大数相减）

• 36进制减法