列表以及字符串加法

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();

    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,941评论 0 23
  • 中午起床的孩子不想吃饭可以试试这个白粥你,是感冒没胃口最好的食粮了! 首先将猪肉剁成肉沫,根据个人喜好调整肉沫的细...
    kanoko阅读 254评论 3 1
  • 高中过后,舒服自由的日子就来了,没有繁重的作业,没有家长老师的叮咛,一切生活随心所欲。迎来生命第二春(第一春在襁褓...
    子暮言阅读 396评论 4 2
  • 我从未如此认真的感到荣幸 虔诚翘首,顶礼膜拜 一步一叩头 一步一作揖 唐卡之上的风马旗咧咧作响 我则如同一个喇嘛 ...
    Mr橘子阅读 364评论 4 2