4

108 ページのゲイル・ラークマンによるCrack The Coding Interviewという本から、リンクされたリストで表される 2 つの数値を加算するアルゴリズムを読んでいました。本を持っていない場合、質問、アルゴリズム、およびコードは次のとおりです。

質問

リンクされたリストで表される 2 つの数値があり、各ノードには 1 つの数字が含まれています。数字は逆順で格納され、1 の数字がリストの先頭になります。2 つの数値を加算し、連結リストとして um を返す関数を作成します。

例

入力：(3->1->5),(5->9->2)

出力：8->0->8

アルゴリズム

  1. result.data = (node1 + node2 +以前のキャリー) % 10
  2. node1 + node2 > 10 の場合、次の加算に 1 を繰り越します
  3. 2 つのノードのテールを追加し、キャリーを渡します

コード

LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2, int carry) {  
if (l1 == null && l2 == null) {     
    return null;    
}   
LinkedListNode result = new LinkedListNode(carry, null, null);  
int value = carry;  
if (l1 != null) {       
    value += l1.data;   
}   
if (l2 != null) {       
    value += l2.data;   
}   
result.data = value % 10;   
LinkedListNode more = addLists(l1 == null ? null : l1.next, l2 == null ? null : l2.next, value > 10 ? 1 : 0);   
result.setNext(more);   
return result;
}

見た後に頭に浮かぶ明らかなことはif (l1 == null && l2 == null)、両方の数字がヌルで、999 + 999 を追加するときのようにキャリーがまだある場合はどうなるかということです。それは間違った答えになるのでしょうか? それが正しい答えである場合、私にはその方法がわかりません。それが間違った答えである場合、どうすれば正しい答えを得ることができますか? 最初の数行を

LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2, int carry = null) {   
if (l1 == null && l2 == null) {     
    return carry;   
}

トリックをしますか？

4

5 に答える 5

1

DListを使用した私のソリューション！

public class DListNode {
public int item;
public DListNode prev;
public DListNode next;

 DListNode() {
    item = 0;
    prev = null;
    next = null;
}

public DListNode(int i){
    item = i;
    prev = null;
    next = null;

}

}

セカンドクラス:

public class DList {
protected DListNode head;
protected DListNode tail;``
protected long size;

public DList() {
    head = null;
    tail = null;
    size = 0;
}

public DList(int a) {
    head = new DListNode();
    tail = head;
    head.item = a;
    size = 1;

}

public DList(int a, int b) {
    head = new DListNode();
    head.item = a;
    tail = new DListNode();
    tail.item = b;
    head.next = tail;
    tail.prev = head;
    size = 2;

}

public void insertFront(int i) {
    if (size == 0) {
        head = new DListNode(i);
        tail = head;
    } else {
        DListNode temp = new DListNode(i);
        head.prev = temp;
        temp.next = head;
        head = temp;
    }
    size++;
}

public String toString() {
    String result = "[  ";
    DListNode current = head;
    while (current != null) {
        result = result + current.item + "  ";
        current = current.next;
    }
    return result + "]";
}

public long getSize() {
    return size;
}

public DListNode getHead() {
    return head;
}

public DListNode getTail() {
    return tail;
}

public DList addList(DList lst1, DList lst2) {
    DList result = new DList();

    DListNode tail1 = lst1.getTail();
    DListNode tail2 = lst2.getTail();
    int carry = 0;

    if (lst1 == null || lst2 == null) {
        return null;
    }

    if (lst1.getSize() != lst2.getSize()) {
        if (lst1.getSize() < lst2.getSize()) {
            long diff = lst2.getSize() - lst1.getSize();
            long a = 0;
            while (a < diff) {
                lst1.insertFront(0);
                a++;
            }

        } else {
            long diff = lst1.getSize() - lst2.getSize();
            long a = 0;
            while (a < diff) {
                lst2.insertFront(0);
                a++;
            }

        }
    }
    int a = 0;
    int resultValue;
    while (a <= lst1.getSize()) {
        if (tail1 != null && tail2 != null) {
            int l1 = tail1.item;
            int l2 = tail2.item;
            int sum = carry + l1 + l2;

            if (a == lst1.getSize() - 1) {
                resultValue = sum % 10;
                carry = 1;
                result.insertFront(carry);
                result.insertFront(resultValue);

            } else if (sum >= 10) {
                resultValue = sum % 10;
                carry = 1;
                result.insertFront(resultValue);

            }

            else {
                resultValue = sum;
                carry = 0;
                result.insertFront(resultValue);

            }
            //result.insertFront(resultValue);
            tail1 = tail1.prev;
            tail2 = tail2.prev;

        }
        a++;
    }

    System.out.println("List1 is: " + lst1.toString());
    System.out.println("List2 is: " + lst2.toString());

    return result;
}

public static void main(String[] args) {
    DList d1 = new DList();
    DList d2 = new DList();

    d1.insertFront(1);
    d1.insertFront(5);
    d1.insertFront(3);

    d2.insertFront(4);
    d2.insertFront(5);
    d2.insertFront(7);

    DList d3 = new DList();
    System.out.println(d3.addList(d1, d2));

}

}

于 2016-11-20T04:17:53.133 に答える
1

動作する私のソリューションは次のとおりです。

public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    return addTwoNumbers(l1, l2, 0);
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2, int carry) {
    int value;
    if(carry > 0) {
        // handle negative values for carry
       value = carry;
    } else {
       value = 0; 
    }
    if(l1 == null && l2 == null){
        if(value > 0) {
            // here we have only carry to bother.
            // if it is zero, no need to create node
            return new ListNode(value);
        } else {
            return null;
        }
    }
    if(l1 != null){
        value += l1.val;
    }
    if(l2 != null){
        value += l2.val;
    }
    carry = value/10;
    ListNode n1 = new ListNode(value%10);
    n1.next = addTwoNumbers(l1 != null ? l1.next : null, l2 != null ? l2.next : null, carry);
    return n1;
}

}

于 2015-01-14T18:03:58.573 に答える