1

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

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(3n) の複雑さで実行されます。各配列入力を 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

2

やってみよう...

static LinkedListNode getSum(LinkedListNode a, LinkedListNode b) {  
  //some checks first if any computation will be needed at all
  if(a == null) {
    if(b == null)
      return null;
    else
      return b;
  } else if (b == null)
    return a;

  //initialize the variables
  LinkedListNode stacka = null; 
  LinkedListNode stackb = null;
  LinkedListNode ans = null;
  LinkedListNode temp = null;

  //move the contents of a & b into stacka & stackb respectively at the same time
  //best case is when a & b are of equal size
  //worst case is when the size of a & b are worlds apart.
  while(a != null || b != null){
    if(a != null) {
      if(stacka == null){
        stacka = new LinkedListNode(a.value);
      } else {
        temp = new LinkedListNode(a.value);
        temp.next = stacka;
        stacka = temp;
      }
    }

    if(b != null) {
      if(stackb == null){
        stackb = new LinkedListNode(b.value);
      } else {
        temp = new LinkedListNode(b.value);
        temp.next = stackb;
        stackb = temp;
      }
    }

    if(a != null) a = a.next;
    if(b != null) b = b.next;
  }

  int remainder = 0;
  //just pop off the stack then merge! also, don't forget the remainder~
  while(stacka != null || stackb != null){
    //pop from the top of the stack
    int i = ((stacka == null) ? 0 : stacka.value) + ((stackb == null) ? 0 : stackb.value) + remainder;

    //set the value of the remainder if any as well as the value of i
    remainder = i / 10;
    i %= 10;

    temp = new LinkedListNode(i);
    if(ans == null) {
      ans  = temp;
    } else {
      temp.next = ans;
      ans = temp;
    }
    if(stacka != null) stacka = stacka.next;
    if(stackb != null) stackb = stackb.next;
  }
  return ans;
}

getValue() 関数を使用しなかったため、これはせいぜい O(2n) 程度になるはずです。ここで行ったことは、LinkedListNode をスタックとして使用してノードを一時的に格納し、ノードを反転させてから、一度に 1 つずつ値をポップして、出力 LinkedListNode に入力することでした。

繰り返しになりますが、最終的には両方のアルゴリズムが依然として O(n) に該当するため、違いは無視できます。

時間があれば、後で再帰的なバージョンを作成しようとします。

PS if else ステートメントの一部に中かっこを追加しなかった場合は申し訳ありません。回答フォームを使用してタブを付けるのは難しいです。

于 2013-10-11T20:24:24.837 に答える
1

元の質問は Java にありますが、これは非常に単純な Scala ソリューションです。同じ長さになるように、リストを 0 で埋めたままにします。次に、ペアのリストが 1 つになるように、リストを圧縮します。最後に、ペアを右から左に追加し、キャリー値を渡します。(1 年生で習った数の足し算と同じ方法です。) これは、関数型の手法を使用して、少量のコードで問題を迅速に解決する方法を示しています。

def add(nums1: List[Int], nums2: List[Int]): List[Int] = {
  val nums1Size = nums1.size
  val nums2Size = nums2.size
  val maxSize = nums1Size max nums2Size

  val nums1Padded = List.fill(maxSize - nums1Size)(0) ++ nums1
  val nums2Padded = List.fill(maxSize - nums2Size)(0) ++ nums2
  val zipped = nums1Padded.zip(nums2Padded)

  val (result, carry) = zipped.foldRight((List.empty[Int], 0)) { (curr, r) =>
    val sum = curr._1 + curr._2 + r._2
    ((sum % 10) :: r._1, sum / 10)
  }

  if (carry > 0) carry :: result else result
}
于 2013-10-12T13:08:50.307 に答える
0

結果のリンクリストを前後から構築することで最適化できます。

int aval = getValue(a);
int bval = getValue(b);
int result = aval + bval;
LinkedListNode answer = null;
while (result > 0) {
    int val = result % 10;
    LinkedListNode prev = answer;
    answer = new LinkedListNode(val);
    answer.next = prev;
    result /= 10;
}
if (answer == null) {
    // Assuming you want to return 0 rather than null if the sum is 0
    answer = new LinkedListNode(0);
}
return answer;

これにより、Math.pow 呼び出しの繰り返しが回避されます。

使用した全体的なアルゴリズムは最速である必要があると思います。頭に浮かぶ 1 つの代替手段は、桁の各ペアに対して何らかの種類のキャリー付き加算操作を行うことです (つまり、「手動で」加算を行います) が、それは非常に遅くなる可能性があります。

于 2013-10-11T18:39:40.977 に答える
0

通常、これらのタイプの演習では、最初により一般的な中間形式 (整数など) に変換せずに操作を実行することが期待されます。次の質問は、「数字が 100 桁だったらどうするの?」というものです。合理的な実行時間を提供するためにオペランドの方向を逆にする必要があるかもしれませんが、リンクされたリストのみを使用して解決してみてください。

于 2013-10-11T18:50:19.940 に答える