Add/Multiple Numbers

Leave a comment

November 6, 2016 by oneOokay

  • Add Two Numbers I (LinkedList):123:3->2->1
  • Add Two Numbers II (LinkedList): 123: 1->2->3 翻转
  • Plus One Linked List: 123: 1->2->3 翻转
  • Plus One (Array):{1,2,3} <+1的数学规律>
  • *Add Binary(String):10 + 11 Stringbuilder 翻转
  • *Multiply Strings

总体的trick就是:

  • 用carry来记录进位:注意carry一定要在最后更新。
  • 对于两个linkedlist进行遍历的话用while loop (l1 != null || l2 != null)
  • 对于两个string进行遍历的话同样的用while loop(i >=0 || j >=0){i –; j –;} 其中i = a.length() – 1; j = b.length() – 1
  • character to int: char – ‘0’
  • while loop 里面不要忘了对i–,j–,node.next之类的。
  • 如果原来的两个元素是正序排列的话那么可以
    • 用两个stack来翻转他们
    • 或者最终翻转结果
  • 对于数字+1的进位特殊的数学规律
  • stringbuilder.reverse().toString()
  • stringBuilder.deleteCharAt(i)
  • 除去string leading zero的方法
  • int[] product的用法:位置上存的是不同位数的乘积最后所应该在的位数

Add Two Numbers I

You are given two non-empty linked lists representing two non-negative integers. 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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8


对于加法来说,低位数满往高位数进是由右往左的,与其自然顺序相反。

所以如果要求123+456这样的和,如果数字是正序表示的话(1->2->3)反而不方便求解,逆序反而更容易。如果数字是按正序表示,那么reverse一下,处理完之后再reverse回来。下面是处理逆序表示的数字的方法:

主要要注意的是:

  • dummy来标记head用来返回的方法(因为不能确定head)
  • 一个pre来标记之前的一个节点,用来连接nodes
  • 一个int carry来代表进位
  • 一个while loop来处理:while(l1 != null || l2 != null||carry !=0)就不用三个while loop了
    • 要处理一个数字比另外一个数字位数更长的情况
    • 最后存在进位要新建一个点
  • 注意while loop中l1和l2要=l1.next和l2.next,低级错误不能忍啊
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int v1 = l1 == null ? 0 : l1.val;
            int v2 = l2 == null ? 0 : l2.val;
            int sum = v1 + v2 + carry;
            pre.next = new ListNode(sum % 10);            
            carry = sum / 10;
            prev = pre.next;            
            l1 = (l1 == null) ? l1 : l1.next;
            l2 = (l2 == null) ? l2 : l2.next;
        }
        return dummy.next;
    }

Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

如果可以reverse linkedlist的话就比较简单,直接用I的方法往里套就可以了。

如果不reverse的话,那么可以用两个stack来实现同样的效果.

只是连接node的时候需要从后往前连,而且不需要dummy node。

存在stack的时候,pop之前要check isEmpty()

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        Stack s1 = new Stack();
        Stack s2 = new Stack();
        while (l1 != null){
            s1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null){
            s2.push(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode pre = null;
        while(!s1.isEmpty() || !s2.isEmpty() || carry != 0){
            int v1 = s1.isEmpty() ? 0 : s1.pop();
            int v2 = s2.isEmpty() ? 0 : s2.pop();
            int sum = v1 + v2 + carry;
            ListNode node = new ListNode(sum % 10);
            carry = sum / 10;
            node.next = pre;
            pre = node;
        }
        return pre;
    }

Plus One(LinkedList)

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.


和Add Numbers II是一样的其实,就是有些小细节要处理。

public ListNode plusOne(ListNode head) {
        int carry = 0;
        ListNode pre = null;
        Stack stack = new Stack();
        while (head.next != null){
            stack.push(head.val);
            head = head.next;
        }
        stack.push(head.val + 1);
        while (!stack.isEmpty() || carry != 0){
            int sum = (stack.isEmpty() ? 0 : stack.pop()) + carry;
            ListNode node = new ListNode(sum % 10);
            node.next = pre;
            pre = node;
            carry = sum / 10;
        }
        return pre;
    }

Plus One(Array)

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.


这题plus one由LinkedList变成了Array:每个位数都可以由 i access到。的确是可以用前面的stack的方法做,但是有点“兴师动众”。直接运用一个数学规律:在+1的情况下:

  1. 最高位存在进位的情况永远是:9, 99, 999,且进位之后,最高位之后的数字都是0.
  2. 最高位没有进位的话:数字变动就在不等于9的位数+1之后结束。
public int[] plusOne(int[] digits) {
    for (int i = digits.length - 1; i >=0; i--) {
        if (digits[i] != 9) {
            digits[i]++;
            break;
        } else {
            digits[i] = 0;
        }
    }
    if (digits[0] == 0) {
        int[] res = new int[digits.length+1];
        res[0] = 1;
        return res;
    }
    return digits;
}

Add Binary(String)

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

For example,
a = "11"
b = "1"
Return "100".


tricks:

  • string的单个字符遍历:可以用str.charAt(i)或者str.toCharArray()再对char array进行遍历
  • ‘1’和’0’如何转换成int:a.charAt(i) – ‘0’
  • 对于两个string,同时从后往前遍历:
    • i = a.length() – 1;
    • j = b.length() – 1;
    • while (i >= 0 || j >= 0) {i –; j –;}
  • char或者int重新组合成string:
    • StringBuilder
    • sb.reverse():翻转stringbuilder
    • sb.toString()
public String addBinary(String a, String b) {
        if (a == null) return b;
        if (b == null) return a;
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        int sum = 0;
        StringBuilder sb = new StringBuilder();
        while (i >= 0 || j >= 0){
            if (i >= 0 && j >= 0){
                sum = a.charAt(i) - '0' + b.charAt(j) - '0' + carry;
                sb.append(sum % 2);
                carry = sum / 2;
                i --;
                j --;
            }else if (i >= 0){
                sum  = a.charAt(i) - '0' + carry;
                sb.append(sum % 2);
                carry = sum / 2;
                i --;
            }else {
                sum = b.charAt(j) - '0' + carry;
                sb.append(sum % 2);
                carry = sum / 2;
                j --;
            }
        }
        if (carry > 0) sb.append(carry);
        return sb.reverse().toString();
    }

Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

  1. The length of both num1 and num2 is < 110.
  2. Both num1 and num2 contains only digits 0-9.
  3. Both num1 and num2 does not contain any leading zero.
  4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

我的思路是跟着老师教的乘法原则来的:num2从个位开始于num1相乘,所得所有结果相加。是一个笨方法。

最优的是用一个int[] 来存product:右数第一个product存num1和num2的个位数字相乘的积。最终对product这个array进行处理(所以这里的product的每个元素并不代表着一位数)

  • int[] product:长度为num1.length() + num2.length():乘积的长度不会长过两个数的和
  • 从num1和num2的个位开始遍历:i for num1, j for num2的话,他们的乘积所处的位置应该为:product[i + j + 1]:
    • index i:和个位数字相隔:len1 – i – 1;
    • index j:和个位数字相隔:len2 – j – 1;
    • 所以num1的index为i的数字与num2的index为j的数字的乘积的位置:该位置离product的个位数字隔:i和j和个位数字相隔的和。所以乘积的位置对于array的index应该为:len1 + len2 – (len1 – i – 1) – (len2 – j – 1) – 1 = i + j + 1
  • 对product array处理使它成为一个“数字”,每个位置上都是一位数字
  • 按顺序append stringBuilder
  • 除去string leading zero的方法
public String multiply(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        int[] product = new int[len1 + len2];
        for (int i = len1 - 1; i >= 0; i --){
            for (int j = len2 - 1; j >= 0; j --){
                product[i + j + 1] += (num1.charAt(i) - '0') * 
                                      (num2.charAt(j) - '0');
            }
        }
        int carry = 0;
        int sum = 0;
        for(int i = len1 +  len2 - 1; i >= 0; i --){
            int tmp = product[i] + carry;
            product[i] = tmp % 10;
            carry = tmp / 10;
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < product.length; i ++){
            sb.append(product[i]);
        }
        //除去string leading 0
        while (sb.length() != 0 && sb.charAt(0) == '0'){
            sb.deleteCharAt(0);
        }
        return sb.length() == 0? "0" : sb.toString();
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: