跟Integer相关的12,13,38,273我放在后面了。
2. Add Two Numbers
链表的时候我们写过一道题是这样的。回忆一下,然后看下一道题。
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode dummy = new ListNode(0);
ListNode node = dummy;
while (l1 != null && l2 != null) {
int sum = l1.val + l2.val + carry;
node.next = new ListNode(sum % 10);
carry = sum / 10;
l1 = l1.next;
l2 = l2.next;
node = node.next;
}
while (l1 != null) {
int sum = l1.val + carry;
node.next = new ListNode(sum % 10);
carry = sum / 10;
l1 = l1.next;
node = node.next;
}
while (l2 != null) {
int sum = l2.val + carry;
node.next = new ListNode(sum % 10);
carry = sum / 10;
l2 = l2.next;
node = node.next;
}
if (carry != 0) {
node.next = new ListNode(carry);
node = node.next;
node.next = null;
}
return dummy.next;
}
}
67. Add Binary
上题完全一样的思路应用在二进制计算上就行了。十进制和二进制区别也就是%取余时用10和2。进位操作也是完全相同的。
这道题不同的是,当问题非常简单的时候,解题重点就从优化时间复杂度变成了优化代码简洁性。
这题代码简洁的重点在于处理“终止条件”,因为两个 string 很可能长度不一,也有可能两个 string 加完了之后还有进位没处理。
输入长短不一就都放在 while loop 里,在读取字符时把短的做 padding
While loop 里三个 'OR' 的条件保证了三种不同情况下都会继续读取,而其他两个自动 pad 0
public class Solution {
public String addBinary(String a, String b) {
StringBuilder sb = 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';
sb.append((digitA + digitB + carry) % 2);
carry = (digitA + digitB + carry) / 2;
}
return sb.reverse().toString();
}
}
43. Multiply Strings
又进阶了,这次是乘法,比加法复杂。
下面的解法是九章算法的,简洁高效。非常聪明巧妙。
两个位数为 m 和 n 的数字相乘,乘积不会超过 m + n 位。
乘法操作从右往左计算时,每次完成相加就确定了当前 digit.
同一个 digit 多次修改,用 int[]
进位的trick都是一样的。注意最后的index和maxLength,利用长度和下标,简单的规避了任何一个数字为0的corner case,非常的简洁。
public class Solution {
public String multiply(String num1, String num2) {
if (num1 == null || num2 == null) return null;
int maxLength = num1.length() + num2.length();
int[] result = new int[maxLength];
for (int i = num1.length() - 1; i >= 0; --i) {
int j, carry = 0;
for (j = num2.length() - 1; j >= 0; --j) {
int digit1 = num1.charAt(i) - '0';
int digit2 = num2.charAt(j) - '0';
int product = digit1 * digit2 + carry + result[i + j + 1];
result[i + j + 1] = product % 10;
carry = product / 10;
}
result[i + j + 1] = carry;
}
StringBuilder sb = new StringBuilder();
int index = 0;
while (index < maxLength - 1 && result[index] == 0) index++;
while (index < maxLength) sb.append(result[index++]);
return sb.toString();
}
}