Add Binary || Add Two Numbers

发表于

Add Binary

Question

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

For example,
a = “11”
b = “1”
Return “100”.

Analysis

加数的过程是从最低位开始加，假如两个数字位数不同的话高位以0补齐。首先在其中一个数字为0的情况下返回另外一个数字。在经过所有的判断之后，两个指向最高位的游标同时像低位扫描，判断为0/1，同时给temp赋值，取得两个temp与flag的和后判断是否需要进位。在全部扫描过后再看flag是否为1，决定是否需要在加1位。stringbuilder 的 append 可以提高空间利用率，最后将整个字符串倒转即可。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {
    public String addBinary(String a, String b) {
        if(a.length()==0||a==null)
            return b;
        if(b.length()==0||b==null)
            return a;
       
        int flag=0; 
        int pa=a.length()-1;
        int pb=b.length()-1;
        StringBuilder num=new StringBuilder();
        
        while(pa>=0||pb>=0){//pa,pb为最低位下标
            int tmpa=0;
            int tmpb=0;
            
            if(pa>=0){
                tmpa=(a.charAt(pa)=='0')?0:1;
                pa--;
            }
            if(pb>=0){
                tmpb=(b.charAt(pb)=='0')?0:1;
                pb--;
            }
            
            int sum=tmpa+tmpb+flag;
            if(sum>=2){
                flag=1;
                num.append(String.valueOf(sum-2));
            }
            else{
                num.append(String.valueOf(sum));
                flag=0;
            }
        }
        
        if(flag==1)
            num.append('1');
            
        String reverse=num.reverse().toString();
        return reverse;
    }
}

Add Two Numbers

Question

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

Analysis

思路跟上面的类似，不过处理的方式变成链表的指针移动。除此之外，还有进位的问题，假如对进位和所录入数字的计算变为求余和求除数的话，就不用假如if来判断sum是否超过10了。

ListNode每次有新节点的时候都需要new，否则会造成 java.lang.NullPointerException

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 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) {
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
            
        ListNode result=new ListNode(0);
        ListNode p1=l1,p2=l2,p3=result;
        int carry=0;
        while(p1!=null||p2!=null){
            int tmp1=0,tmp2=0;
            if(p1!=null){
                tmp1=p1.val;
                p1=p1.next;
            }
            
            if(p2!=null){
                tmp2=p2.val;
                p2=p2.next;
            }
            
            int sum=tmp1+tmp2+carry;
            p3.next=new ListNode(sum%10);
            carry=sum/10;
            p3=p3.next;
        }
        
        if(carry==1)
            p3.next=new ListNode(1);
            
        return result.next;
    }
}