目录
今日良言：花有重开日，人无再少年
一、字符串相加
1.问题描述
给定两个字符串形式的非负整数?num1 和num2?，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger），?也不能直接将输入的字符串转换为整数形式。
例如：
输入：num1 = "11", num2 = "123" 输出："134"
2.解决思路
a. 题目要求不可以使用库，以及不能直接将输入的字符串换成整数形式，所以说我们放弃这种思路。
b.首先针对相加问题，我们要先考虑进位的问题，从后向前进位，那么我们不妨将两个字符串从后向前加，每次拿到两个字符串的下标的字符，然后转成整数，注意：我们需要考虑两个字符串不相等的情况，所以用一个下表来表示两个字符串显然是不行的，那么我们使用 i 和 j 两个变量来表示下标，i 和 j? 的初始值就是两个字符串的长度-1 。
c.那么确定了下标以后，我们需要考虑，如果有一个字符串为空了，该如何计算？? 实际上，我们可以将为空的那个字符串（也就是 i 或者 j? < 0）的字符直接当作0即可，即使参与运算也不会影响结果。
d.假设此时两个字符串的下标都合法，对应的值为x和y，那么将其转换成数字以后，我们需要考虑进位，因此我们设置一个变量 add 表示每次需要向前进位的数字，也就是 add =（x + y）/ 10 。
e.我们使用StringBuffer来进行字符串拼接，那么我们每次拼接的值是多少呢？实际上当前x+y+add（向前进位的值）% 10 就是我们需要拼接的值。
f.不难看出，上述操作实际上是一个循环，条件是 i >=0 || j>=0 || add > 0? ? ?add这个条件存在的意思是：可能最后相加的结果还是要向前进位，我们不能舍去这个进位的值。
3.代码实现
class Solution {
public String addStrings(String num1, String num2) {
// 从下标最高位开始计算，用add记录两数相加的结果是否需要进位
int i = num1.length() - 1;
int j = num2.length() - 1;
int add = 0;
// 如果有一个下标不为0或者add也就是需要进位 就一直循环
StringBuffer str = 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; // 需要加上进位的数字
str.append(result % 10);
add = result / 10;
i--;
j--;
}
// 计算后要翻转
str.reverse();
return str.toString();
}4.题目链接
5.相似题目
解法：
class Solution {
public String addBinary(String a, String b) {
int i = a.length() - 1;
int j = b.length() - 1; // i j都是下标
int add = 0; // 进位的数字
StringBuffer str = new StringBuffer();
while (i >= 0 || j >= 0 || add > 0) {
int x = i >= 0 ? a.charAt(i) - '0' : 0;
int y = j >= 0 ? b.charAt(j) - '0' : 0;
int result = x + y +add;
str.append(result % 2);
add = result / 2;
i--;
j--;
}
str.reverse();
return str.toString();
}
}二、字符串相乘
1.问题描述
给定两个以字符串形式表示的非负整数?num1?和?num2，返回?num1?和?num2?的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
例如：
输入: num1 = "123", num2 = "456" 输出: "56088"
2.解决思路
a.字符串相乘无法直接使用字符串相加的计算方式。首先，我们需要观察一个规律，如下图：
?这里num1和num2是需要计算的字符串中的数字，result是我们创建的需要存储的计算结果。观察上述下标，有什么发现？? 假设 i 是num1的下标，j 是 num2的下标， num1[i] * num2[j] 的结果在result[i+j] 中。
b.首先我们可以创建一个两个字符串长度相加的长度的数组result用于存储计算结果，假设num1的长度为n，num2的长度为m，那么创建的result容纳的数据就是m+n 个，为什么创建m+n呢？因为，假设都是多大的两位数99相乘，他们的计算结果的长度一定不比m+n大。
c.如果只是将两个字符串每个位置的计算结果都放在 result的 i + j 下标处的话，那么最高位的进位就会被忽略，所以说，我们不妨空出来一个位置存放需要像最高位进的那个值。 用代码实现就是：? result[i + j + 1] = num1[i] + num2[j];? ?
d.然后我们需要考虑进位的问题，从后向前遍历result数组，满10就进位。
e.进位结束后，我们创建一个 StringBuffer 类型的 str 用来拼接result中的计算结果，但是，由于之前我们将result的0下标空了出来，如果没有向0下标进位，那么该位置就应该删除，所以我们需要考虑是否删除该下标处的值。
f.最后将其转换成字符串返回即可?
3.代码实现
class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0"))
return "0";
char[] arr1 = num1.toCharArray();
char[] arr2 = num2.toCharArray();
int n = arr1.length;
int m = arr2.length;
int[] result = new int[m+n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
result[i+j+1] += ((arr1[i]-'0')*(arr2[j]-'0'));
}
}
// 从后往前处理进位
for(int j = result.length-1; j > 0; j--) {
if (result[j] >= 10) {
result[j-1] += result[j]/10;
result[j] = result[j] % 10;
}
}
// 如果没有进位的话，我们需要去掉0
StringBuilder str = new StringBuilder();
for (int i : result) {
str.append(i);
}
if (str.charAt(0) == '0') {
str.deleteCharAt(0);
}
return str.toString();
}
}4.题目链接