6

最近の面接でプログラミングの質問を受けました。

2 つのリンクされたリストがあります。各ノードには、1 ～ 9 の値が格納されます (数値の 1 つのインデックスを示します)。したがって、123 は連結リスト 1->2->3 になります。

タスクは関数を作成することでした:

static LinkedListNode getSum(LinkedListNode a, LinkedListNode b)

これは、2 つのリンクされたリスト引数の値の合計を返します。

配列 a の場合: 1->2->3->4

配列 b は 5->6->7->8 です。

答えは次のようになります: 6->9->1->2

これが私のアルゴリズムです：

a と b の各ノードを調べ、値を整数として取得して加算します。これらの値を使用して新しいリンク リストを作成します。

コードは次のとおりです。おおよそ O(n) の複雑さで実行されます。各配列入力を 1 回通過し、出力配列を作成するために 1 回。

改善点はありますか？より良いアルゴリズム...またはコードの改善

public class LinkedListNode {
        LinkedListNode next;
        int value;

    public LinkedListNode(int value) {
        this.value = value;
        this.next = null;
    }

    static int getValue(LinkedListNode node) {
        int value = node.value;
        while (node.next != null) {
            node = node.next;
            value = value * 10 + node.value;
        }
        return value;
    }

    static LinkedListNode getSum(LinkedListNode a, LinkedListNode b) {
        LinkedListNode answer = new LinkedListNode(0);
        LinkedListNode ans = answer;
        int aval = getValue(a);
        int bval = getValue(b);
        int result = aval + bval;
        while (result > 0) {
            int len = (int) Math.pow((double) 10,
                    (double) String.valueOf(result).length() - 1);
            int val = result / len;
            ans.next = new LinkedListNode(val);
            ans = ans.next;
            result = result - val*len;
            }    
        return answer.next;
    }
}
4

5 に答える 5

3

この問題に対して私が見た他の解決策には、新しいリストに移動するときに各要素を追加すると同時に、両方の入力リストを逆方向に反復することにより、返されたリストを段階的に構築することが含まれます。各要素を追加してキャリーオーバーを処理する必要があるため、その方法はより複雑です。

配列 a の場合: 1->2->3->4

配列 b は 5->6->7->8 です。

逆方向に繰り返す

次に、4 + 8 = 12 (現在の返されるリスト = 2)

1を運ぶ

(1) + 3 + 7 = 11 (返されるリスト = 1-> 2)

1を運ぶ

(1) + 2 + 6 = 9 (返されるリスト = 9 -> 1 ->2 )

1 + 5 = 6 (リストを返す = 6->9>1->2)

リストが単独でリンクされている場合は、Stacks を使用して LIFO の性質を逆方向に繰り返すことでこれを実装できます。

于 2013-10-11T14:33:56.903 に答える
0

私が見た他の回答は、多くの場合、余分なスタックに依存しています。O(1)実際には、余分なスペースだけで解決できます。別の回答の例を変更して、2 つのリストの長さを変えました。

list a is: 1->2->3->4
list b is: 5->6->7->8->3->6

両方のリストを反復し、現在の値の値をaとに保存しb、新しいリストの値に保存するだけcです。しかし、単純に 2 つの値の合計を の値として取得することはできませんc。2 つのリストの長さが異なる場合、リストaとの元の値を復元できないからbです。ちょっとしたトリックは、次のように 2 桁の値を生成することです。最初の桁は の値でa、2 番目の桁は の値bです。

list c: 15 <- 26 <- 37 <- 48 <- 3 <- 6
                                     ^ pointer "p1"
                           ^ pointer "p2" here to mark the end of list a

リストcが完全に作成されたら、ポインタ「p1」から巻き戻します。最初にノード内の 2 つの数値をポインター "p2" で分離し、次に正しい数値を p1 の値に追加します。p1->next次に、p1 と set 、および p2 とを逆p2->nextにして、前のノードに進みます。

list c: 15 <- 26 <- 37 <- 8 <- 3 -> 4
                               ^ p1
                     ^ p2
                               carry = 1

時間計算量は2*max( length(a), length(b) )です。

于 2015-03-11T05:30:33.007 に答える