String / LinkedList 大数运算
当问题非常简单的时候,解题重点就从优化时间复杂度变成了优化代码简洁性。
我就不回头看自己那么挫的第一个 AC 答案了。。贴个论坛的(加上我自己的改动)里面有几个很巧妙的优化使代码变得简洁易懂。
这题代码简洁的重点在于处理“终止条件”,因为两个 string 很可能长度不一,也有可能两个 string 加完了之后还有进位没处理。
这段代码给出的答案是:
输入长短不一就都放在 while loop 里,在读取字符时把短的做 padding.
While loop 里三个 'OR' 的条件保证了三种不同情况下都会继续读取,而其他两个自动 pad 0.
public class Solution {
public String addBinary(String a, String b) {
StringBuilder sum = new StringBuilder();
int i = a.length() - 1;
int j = b.length() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry == 1) {
int digitA = i < 0 ? 0 : a.charAt(i--) - '0';
int digitB = j < 0 ? 0 : b.charAt(j--) - '0';
sum.append((digitA + digitB + carry) % 2);
carry = (digitA + digitB + carry) / 2;
}
return sum.reverse().toString();
}
}
上题完全一样的思路应用在链表上就是这样了。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode head = dummy;
int carry = 0;
while(l1 != null || l2 != null || carry > 0){
int num1 = (l1 == null) ? 0 : l1.val;
int num2 = (l2 == null) ? 0 : l2.val;
ListNode node = new ListNode((num1 + num2 + carry) % 10);
carry = (num1 + num2 + carry) / 10;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
head.next = node;
head = head.next;
}
return dummy.next;
}
}
又进阶了, 这次是乘法,比加法复杂。下面的代码是我写的略为粗糙的第一版。
这题的时间复杂度不会低于 ,因为毕竟每个 digit 都要和另外的 string 相乘一次。 所以把运算拆成两部分,一部分是 longer string 与单数位乘法,另一个是一个数位结束之后,两数相加。每一个数位上的结果乘出来之后要对应的做 0 padding,代表左位移。
提交时候遇到的一个 bug 是 "9133" x "0" 的情况,要记得在 multiply() 函数中如果输入是 0 就直接返回 "0",这是乘法和加法运算的一个不同之处,否则会返回“0000”.
public class Solution {
public String multiply(String num1, String num2) {
String longStr = (num1.length() > num2.length()) ? num1 : num2;
String shortStr = (num1.length() > num2.length()) ? num2 : num1;
String rst = "";
int index = 0;
while(shortStr.length() - 1 - index >= 0){
int num = shortStr.charAt(shortStr.length() - 1 - index) - '0';
String cur = multiplyOne(longStr, num);
for(int i = index; i > 0; i--){
cur += "0";
}
rst = addTwo(rst, cur);
index ++;
}
return rst;
}
private String multiplyOne(String src, int num){
if(num == 0) return "0";
StringBuilder sb = new StringBuilder();
int carry = 0;
for(int i = src.length() - 1; i >= 0; i--){
int digit = src.charAt(i) - '0';
sb.append((digit * num + carry) % 10);
carry = (digit * num + carry) / 10;
}
if(carry > 0) sb.append(carry);
return sb.reverse().toString();
}
private String addTwo(String num1, String num2){
StringBuilder sb = new StringBuilder();
int i = num1.length() - 1;
int j = num2.length() - 1;
int carry = 0;
while(i >= 0 || j >= 0 || carry > 0){
int digit1 = (i >= 0) ? num1.charAt(i--) - '0': 0;
int digit2 = (j >= 0) ? num2.charAt(j--) - '0': 0;
sb.append((digit1 + digit2 + carry) % 10);
carry = (digit1 + digit2 + carry) / 10;
}
return sb.reverse().toString();
}
}
前面的做法对于每一个 digit 都做了一个乘法和加法操作,并没有特别好的利用到乘法的特点,中间操作过多而且生成了好多不必要的 String.
下面的解法是九章算法的,简洁高效。
两个位数为 m 和 n 的数字相乘,乘积不会超过 m + n 位。
乘法操作从右往左计算时,每次完成相加就确定了当前 digit.
同一个 digit 多次修改,用 int[ ].
public class Solution {
public String multiply(String num1, String num2) {
if(num1 == null || num2 == null) return null;
int maxLength = num1.length() + num2.length();
int[] nums = new int[maxLength];
int i, j, product, carry;
for(i = num1.length() - 1; i >= 0; i--){
// 中间部分相当于多位数乘一位数,起始 carry 为 0
carry = 0;
for(j = num2.length() - 1; j >= 0; j--){
int a = num1.charAt(i) - '0';
int b = num2.charAt(j) - '0';
product = nums[i + j + 1] + a * b + carry;
nums[i + j + 1] = product % 10;
carry = product / 10;
}
// 循环结束,最左面为当前最高位数,如果 carry 还有就设过去
nums[i + j + 1] = carry;
}
StringBuilder sb = new StringBuilder();
int index = 0;
while(index < maxLength - 1 && nums[index] == 0) index ++;
while(index < maxLength) sb.append(nums[index++]);
return sb.toString();
}
}
Last updated
Was this helpful?