4

割り当ては、リスト内の 2 つのノードを交換する関数を作成することでした。関数が順序に関係なくノードを交換できた場合、10% が授与されました。私の実装では、リストの順序に関係なく 2 つの要素を交換できると思いますが、それでもボーナス マークを受け取りませんでした。不足しているものはありますか？

ジェネリック ノード クラスが与えられました。

public class Node<T> {
    public T val;
    public Node<T> next;

    public Node(T val) {
        this.val = val;
        this.next = null;
    }
}

以下のように定義されたインターフェースも与えられました。

public interface SwapList<T> {

    public void add(T val);

    /**
     * Swaps two elements in the list, but only if @param val1 comes BEFORE @param
     * val2. Solve the problem regardless of the order, for 10% extra. list: A B
     * C -> swap(A,B) will result in the list B A C list: A B C -> swap(B,A)
     * will not swap. list: A C C -> swap(A, D) will throw a
     * NoSuchElementException list: A B C B -> swap (A, B) will result in the
     * list B A C B list: A B C A B B -> swap (A,B) will result in the list B A
     * C A B B a list with one or zero elements cannot do a swap
     */
    public void swap(T val1, T val2);

    public T get(int i);
}

以下のように、このインターフェースを独自に実装しています。

import java.util.NoSuchElementException;
public class SwapListImpl<T> implements SwapList<T> {

    private Node<T> head;
    private Node<T> tail;
    private int counter;

    public SwapListImpl() {
        head = null;
        tail = null;
        counter = 0;
    }

    @Override
    public void add(T val) {
        Node<T> node = new Node<T>(val);
        if (head == null) {
            head = node;
            tail = node;
        } else {
            tail.next = node;
            tail = node;
        }

        counter++;
    }

    @Override
    public void swap(T val1, T val2) {

        if (counter < 2 || val1.equals(val2))
            return;

        Node<T> current = head;
        Node<T> currentPrev = null;

        Node<T> first = head;
        Node<T> firstPrev = null;
        Node<T> firstNext = first.next;

        Node<T> second = head;
        Node<T> secondPrev = null;
        Node<T> secondNext = second.next;

        boolean foundFirst = false;
        boolean foundSecond = false;
        boolean inOrder = false;

        while (current != null) {
            if (!foundFirst && current.val.equals(val1)) {

                firstPrev = currentPrev;
                first = current;
                firstNext = current.next;

                if (!foundSecond)
                    inOrder = true;

                foundFirst = true;

            }

            if (!foundSecond && current.val.equals(val2)) {

                secondPrev = currentPrev;
                second = current;
                secondNext = current.next;

                if (foundFirst)
                    inOrder = true;

                foundSecond = true;
            }

            if (foundFirst && foundSecond) {

                if (!inOrder) {
                    Node<T> temp = first;
                    first = second;
                    second = temp;

                    temp = firstPrev;
                    firstPrev = secondPrev;
                    secondPrev = temp;

                    temp = firstNext;
                    firstNext = secondNext;
                    secondNext = temp;
                }

                if (firstPrev == null) {

                    head = second;

                    if (first == secondPrev) {
                        second.next = first;
                        first.next = secondNext;
                    } else {
                        second.next = firstNext;
                        secondPrev.next = first;
                        first.next = secondNext;
                    }
                } else {

                    firstPrev.next = second;
                    first.next = secondNext;

                    if (first == secondPrev) {
                        second.next = first;
                    } else {
                        second.next = firstNext;
                        secondPrev.next = first;
                    }
                }

                break;
            }

            currentPrev = current;
            current = current.next;
        }

        if (!foundFirst || !foundSecond) {
            throw new NoSuchElementException();
        }
    }

    @Override
    public T get(int i) {
        if (i < counter) {
            Node<T> node = head;
            for (int n = 0; n < i; n++) {
                node = node.next;
            }
            return node.val;
        } else {
            throw new IndexOutOfBoundsException();
        }
    }
 }
4

1 に答える 1

2

問題はスワップ自体だと思います。テールを設定するのを忘れていました。

これは、まさにその問題に対する小さなテストです。

@Test
public void test() {
  SwapListImpl<String> list = new SwapListImpl<String>();
  list.add("A");
  list.add("B");
  list.add("C");

  list.swap("A", "C");

  assertEquals("C", list.get(0));
  assertEquals("C", list.getHead().val);
  assertEquals("B", list.get(1));
  assertEquals("A", list.get(2));
  assertEquals("A", list.getTail().val);

  list.add("D");

  assertEquals("C", list.get(0));
  assertEquals("C", list.getHead().val);
  assertEquals("B", list.get(1));
  assertEquals("A", list.get(2));
  assertEquals("D", list.get(3));
  assertEquals("D", list.getTail().val);

  list.swap("A", "C");

  assertEquals("A", list.get(0));
  assertEquals("A", list.getHead().val);
  assertEquals("B", list.get(1));
  assertEquals("C", list.get(2));
  assertEquals("D", list.get(3));
  assertEquals("D", list.getTail().val);

  list.swap("C", "B");

  assertEquals("A", list.get(0));
  assertEquals("A", list.getHead().val);
  assertEquals("C", list.get(1));
  assertEquals("B", list.get(2));
  assertEquals("D", list.get(3));
  assertEquals("D", list.getTail().val);
}

頭と尾を取得するためにリストに 2 つのメソッドを追加したことがわかりますが、それは重要ではありません。頭と尾の明示的なテストがなければ、テストは失敗することさえあります。リストの追加メソッドは非常に単純です。

  public Node<T> getTail() {
      return this.tail;
    }

    public Node<T> getHead() {
      return this.head;
    }

リストの最後の要素を交換してから別の要素を追加すると、末尾が設定されないという問題が発生します。

実際のスワップの修正版は次のとおりです。

  if (foundFirst && foundSecond) {

    if (second == this.tail) {
      this.tail = first;
    } else if (first == this.tail) {
      this.tail = second;
    }

    if (first == this.head) {
      this.head = second;
    } else if (second == this.head) {
      this.head = first;
    }

    if (firstPrev == second) {
      first.next = second;
    } else {
      if (firstPrev != null) {
        firstPrev.next = second;
      }
      first.next = secondNext;
    }
    if (secondPrev == first) {
      second.next = first;
    } else {
      if (secondPrev != first && secondPrev != null) {
        secondPrev.next = first;
      }
      second.next = firstNext;
    }
    break;
  }

コードに行を追加していないことがわかります。代わりに、別の方法でコードを記述しました。読みやすいと思いますが、テールを正しい方法で設定することもできます。しかし、私には複雑すぎたので、そのコードの複雑さを減らしました。それが、コードを書き直した理由です。

1 番目と 2 番目の引数ではなく、1 番目と 2 番目の出現に対して first と second を使用することをお勧めします。これにより、メソッドの可読性が向上すると思います。しかし、それは別のポイントです;-)

それが役立つことを願っています-したがって、IMHOの順序は問題ではなく、尾です。

于 2012-06-21T09:34:23.083 に答える