高精度计算
文章目录
- 1. 高精度加法(67)
- 2. 高精度乘法(43)
1. 高精度加法(67)
题目描述:
代码如下:
class Solution {
public String addBinary(String a, String b) {
int cur1 = a.length() - 1;
int cur2 = b.length() - 1;
int t = 0;
StringBuilder ret = new StringBuilder();
while (cur1 >= 0 || cur2 >= 0 || t > 0) {
if (cur1 >= 0) {
t += a.charAt(cur1) - '0';
cur1--;
}
if (cur2 >= 0) {
t += b.charAt(cur2) - '0';
cur2--;
}
ret.append(t % 2);
t /= 2;
}
return ret.reverse().toString();
}
}
题目链接
2. 高精度乘法(43)
题目描述:
算法原理:
处理这类问题有个简单的方式就是先使用无进位乘法得到结果后再去处理进位,代码清晰。
代码如下:
class Solution {
public String multiply(String s, String ss) {
// 1、准备工作
int m = s.length(), n = ss.length();
char[] num1 = new StringBuilder(s).reverse().toString().toCharArray();
char[] num2 = new StringBuilder(ss).reverse().toString().toCharArray();
int[] temp = new int[m + n - 1];
// 2、无进位相乘
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
temp[i + j] += (num1[i] - '0') * (num2[j] - '0');
}
}
// 3、处理进位
int cur = 0, carry = 0;
StringBuilder ret = new StringBuilder();
while (cur < n + m - 1 || carry != 0) {
if (cur < n + m - 1) {
carry += temp[cur++];
}
ret.append(carry % 10);
carry /= 10;
}
// 4、处理前导0
while (ret.length() > 1 && ret.charAt(ret.length() - 1) == '0') {
ret.deleteCharAt(ret.length() - 1);
}
return ret.reverse().toString();
}
}
题目链接