dcq.jpeg

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

Output: 7 -> 0 -> 8

​
这个问题比较核心的一点是对进位(carry)的处理，处理好了进位(carry)也就没什么难度了。
同时，还要注意一下几个特殊的链表

1. 两个不一样长的

   l1 = [0, 1];

   l2 = [0, 1, 2];

2. 有一个是空列表的情况

   l1 = []

   l2 = [0, 1]

3. 多次进位的情况（这个状况是最容易被遗漏的）

   l1 ＝[9, 9]

   l2 = [1]

直接上代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if (l1 == null)
                if(l2 != null) {
                    return addTwoNumbers(l2, new ListNode(0));
                } else {
                    return null;
                }
            if (l2 == null) {
                if(l1!=null) {
                    return addTwoNumbers(l1, new ListNode(0));
                } else {
                    return null;
                }
            }
            int val = l1.val + l2.val;
            ListNode head = new ListNode(val%10);
            int carry = val / 10;
            if(carry > 0) {
                if(l1.next == null) {
                    l1.next = new ListNode(carry);
                } else {
                    l1.next.val += carry;
                }
            }
            head.next = addTwoNumbers(l1.next, l2.next);
            return head;
      }

扩展一下

Given two binary strings, return their sum (also a binary string).

For example,

a = "11"

b = "1"

Return "100".

类似于二进制的加法核心跟上一个算法没有太多区别。

 public String addBinary(String a, String b) {
        if(a == null || a.equals(""))return b;
        if(b == null || b.equals(""))return a;
        StringBuilder stringBuilder = newStringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if(i >= 0) sum += a.charAt(i--)- '0';
            if(j >= 0) sum += b.charAt(j--)- '0';
            stringBuilder.append(sum%2);
            carry = sum / 2;
        }
        if(carry != 0)stringBuilder.append(carry);
        return stringBuilder.reverse().toString();
    }

结束了加法，我们来看看乘法

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note:

• The numbers can be arbitrarily large and are non-negative.
• Converting the input string to integer is NOT allowed.
• You should NOT use internal library such as BigInteger.

这里我们观察一下，能得到结论：

num1[i] 和num2[j] 的乘积会放置在indices[i+j, i+j+1]的位置

说起来比较抽象，我们看图：

字符串乘法演示.jpg

代码实现如下：

public String multiply(String num1, String num2) {
    int m = num1.length(), n = num2.length();
    int[] pos = new int[m + n];
   
    for(int i = m - 1; i >= 0; i--) {
        for(int j = n - 1; j >= 0; j--) {
            //错位相加
            int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); 
            int p1 = i + j, p2 = i + j + 1;
            int sum = mul + pos[p2];
            pos[p1] += sum / 10;
            pos[p2] = (sum) % 10;
        }
    }  
    
    StringBuilder sb = new StringBuilder();
    for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
    return sb.length() == 0 ? "0" : sb.toString();
}

更清晰的代码实现：

public Stringmultiply(String num1, String num2) {
        char[] s1 = num1.toCharArray();
        char[] s2 = num2.toCharArray();
        int len1 = s1.length;
        int len2 = s2.length;
        int[] ans = new int[len1 + len2];
        for (int i = len2 - 1; i >= 0; i--){
            for (int j = len1 - 1; j >= 0;j--) {
                ans[len1 + len2 - i - j - 2] +=(s2[i] - '0') * (s1[j] - '0');
            }
        }

        for (int i = 0; i < len1 + len2 - 1;i++) {
            ans[i + 1] += ans[i] / 10;
            ans[i] %= 10;
        }

        StringBuilder stringBuilder = newStringBuilder();
        int i = len1 + len2 - 1;
        while (i >= 0 && ans[i] ==0)
            i--;
        if (i < 0)
            return "0";
        while (i >= 0) {
            stringBuilder.append(ans[i]);
            i--;
        }
        return stringBuilder.toString();

    }