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: overflow

总体的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.

这里的num1和num2相乘会有overflow. 遇到相乘的问题一定要考虑overflow啊!

  • 然后用一个int[]来存product,之前想用int[]每一位存实际的相乘的数值,也是会overflow的.
  • 所以每一个int[]里面只存一位数字相乘的积,这样就不会overflow了.

我的思路是跟着老师教的乘法原则来的: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) {
//len1+len2就够了,不需要再加1 
int[] values = new int[num1.length() + num2.length()];
 int n1 = 0, n2 = 0;
 for (int i = 0; i < num1.length(); i ++){
 n1 = num1.charAt(num1.length() - 1 - i) - '0';
 if (n1 == 0) continue;
 for (int j = 0; j < num2.length(); j ++){
 n2 = num2.charAt(num2.length() - 1- j) - '0';
 if (n2 == 0) continue;
 values[i + j] += n1 * n2;
 } }
 //这里不能够直接乘以10相加,依旧会overflow,甚至会overflow long.
 int value = 0;
 for (int i = 0; i < values.length; i ++){
 value += values[i];
 values[i] = value % 10;
 value = value / 10;
 }
//转换为String,同时要注意不要放首位的0.
//第一种方法是:如果sb长为0且当前值为0的话,就append.
for (int i = values.length - 1; i >= 0; i --){
 if (values[i] == 0 && sb.length() == 0)
 continue;
 sb.append(values[i]);
 }
        
//或者把所有的值都append到sb里面,然后不停的删除首位的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: