# String / LinkedList 大数运算

## [Add Binary](https://leetcode.com/problems/add-binary/)

* **当问题非常简单的时候，解题重点就从优化时间复杂度变成了优化代码简洁性。**

我就不回头看自己那么挫的第一个 AC 答案了。。贴个论坛的(加上我自己的改动)里面有几个很巧妙的优化使代码变得简洁易懂。

这题代码简洁的重点在于处理“终止条件”，因为两个 string 很可能长度不一，也有可能两个 string 加完了之后还有进位没处理。

这段代码给出的答案是：

* **输入长短不一就都放在 while loop 里，在读取字符时把短的做 padding.**
* **While loop 里三个 'OR' 的条件保证了三种不同情况下都会继续读取，而其他两个自动 pad 0.**

```java
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();
    }
}
```

## [Add Two Numbers](https://leetcode.com/problems/add-two-numbers/)

上题完全一样的思路应用在链表上就是这样了。

```java
/**
 * 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;
    }
}
```

## [Multiply Strings](https://leetcode.com/problems/multiply-strings/)

又进阶了， 这次是乘法，比加法复杂。下面的代码是我写的略为粗糙的第一版。

这题的时间复杂度不会低于 $$O(mn)$$ ，因为毕竟每个 digit 都要和另外的 string 相乘一次。 所以把运算拆成两部分，一部分是 longer string 与单数位乘法，另一个是一个数位结束之后，两数相加。每一个数位上的结果乘出来之后要对应的做 0 padding，代表左位移。

提交时候遇到的一个 bug 是 "9133" x "0" 的情况，要记得在 multiply() 函数中如果输入是 0 就直接返回 "0"，这是乘法和加法运算的一个不同之处，否则会返回“0000”.

```java
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\[ ].**

```java
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();
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/stringff0c_zi_fu_chuan_lei/525_string_za_ti.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.