【每日算法Day 25】算术基础2
求整数的数根；不论是二进制还是十进制，用字符串模拟竖式来解决可能的大数加法、乘法的问题。
# LeetCode 258. 各位相加 (opens new window)
# 题目描述
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
# 示例
输入: 38
输出: 2
解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
2
3
# 解题思路
可以使用递归或迭代来完成：
递归解法：
public int addDigits(int num) {
if (num < 10) return num;
int n=0;
while (num!= 0) {
n+=num%10;
num/=10;
}
return addDigits(n);
}
2
3
4
5
6
7
8
9
迭代解法：
public int addDigits(int num) {
while (num >= 10) {
int n = 0;
while (num != 0) {
n+= num % 10;
num /= 10;
}
num = n;
}
return num;
}
2
3
4
5
6
7
8
9
10
11
此外，还有一种纯数学推导的解法（摘自知乎）：
证明了对原数做一个 f 操作，也就是各个位上的数相加，然后不停的做 f 操作，最终的结果对 9 取余和原数 x 对 9 取余是相等的。
不考虑 0这种特殊情况，不停的做 f 操作，最终得到的数就是 1 - 9，对 9取余的结果是 1 - 8 和 0。结果是 0 的话对应数根就是 9，其他情况的数根就是取余结果。
n 是 0 ，数根就是 0。 n 不是 9 的倍数，数根就是 n 对 9 取余，即 n mod 9。 n 是 9 的倍数，数根就是 9。
我们可以通过 (n-1) mod 9 + 1 这个式子把上边的几种情况统一起来。
# LeetCode 67. 二进制求和 (opens new window)
# 题目描述
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
# 示例
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
2
3
4
5
6
7
# 解题思路
模拟加法竖式，从两个字符的最高位（等价于二进制数的最低位）开始相加，遇到其中一个字符串结束后就补0。每次将进位和两个数组对应位置的值相加，将计算结果的最后一位转成字符添加到结果中，再将该结果右移一位以保存进位。如果加完之后进位不为0则补1，将结果字符串翻转输出。
public String addBinary(String a, String b) {
StringBuilder ans = new StringBuilder();
int n = Math.max(a.length(), b.length()), carry = 0;
for (int i = 0; i < n; ++i) {
carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
ans.append((char) (carry % 2 + '0'));
carry >>=1;
}
if (carry > 0) {
ans.append('1');
}
return ans.reverse().toString();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
时间复杂度：O(n)，这里的时间复杂度来源于顺序遍历 a 和 b。 空间复杂度：O(1)，除去答案所占用的空间，这里使用了常数个临时变量。
此外，在字符串长度不是特别长时，还可以使用API解析成整数相加再输出二进制形式：
public String addBinary(String a, String b) {
return Integer.toBinaryString(
Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
);
}
2
3
4
5
# LeetCode 43. 字符串相乘 (opens new window)
# 题目描述
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。说明：
- num1 和 num2 的长度小于110。
- num1 和 num2 只包含数字 0-9。
- num1 和 num2 均不以零开头，除非是数字 0 本身。
- 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
# 示例
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
2
3
4
5
6
7
# 解题思路
和两字符串求和相比，这一题增加了乘法，会更加复杂一些。不过同样也可以模拟竖式，把乘法的结果存起来再相加。
- 把两个数从个位开始乘
- 对于 a 的第 i 位 和 b 的第 j 位相乘的结果存储在 result[i + j] 上，即 result[i + j] += a[i] * b[j];这里用加号是因为有多种情况都会映射到 i + j 位上。例如a[0]*b[1]和a[1]*b[0]都会存储到result[1]处。
- 最后，从 result 的低位向高位整理，result[i-1] = result[i] / 10, result[i] %= 10;
- 整理完之后还有进位，则把进位也添加到最后的结果中。
一个乘法的例子：
1 2 3
乘 4 5 6
————————————————————
6 12 18
5 10 15
4 8 12
————————————————————
4 13 28 27 18
整理结果， 从低位开始：
step 0: 4 13 28 27 18
step 1: 4 13 28 28 8
step 2: 4 13 30 8 8
step 3: 4 16 0 8 8
step 4: 5 6 0 8 8
2
3
4
5
6
7
8
9
10
11
12
13
14
public String multiply(String num1, String num2) {
//如果不对输入有"0"做处理则返回"000...0"而不是"0"
if("0".equals(num1)||"0".equals(num2)) return "0";
int l1=num1.length(),l2=num2.length();
int[] result = new int[l1+l2-1];
//计算乘积并存储到数组中
for (int i = 0; i < l1; i++) {
for (int j = 0; j < l2; j++) {
result[i+j]+=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
}
}
//整理数组中结果到最终的字符串中
StringBuilder sb = new StringBuilder();
int carry=0;
for (int i = l1 + l2 - 2; i >= 0; i--) {
sb.append((result[i]+carry)%10);
carry=(result[i]+carry)/10;
}
while (carry != 0) {
sb.append(carry%10);
carry/=10;
}
return sb.reverse().toString();
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26