0

独自の Node クラスと独自の LinkedList クラスを作成しました。LinkedList に含まれる異なる Node の数をカウントする関数を作成したいと考えています。

このコードを試してみましたが、うまくいきません:

for (int i = 0; i < quantityOfNode(); i++) {
    boolean isDistinct = true;

    for (int j = 0; j < i; j++) {
        if (node.getInfo().equals(node.getNext().getInfo())) {
            isDistinct = false;
        }
    }
    if (isDistinct) {
        nbDistinct++;
    }
    if (node.getNext().getNext() != null) {
        node= node.getNext();
    }
}

例:

        list.add(3);
    list.add(2);
    list.add(5);
    list.add(3);
    list.add(3);
    list.add(8);

これは 4 つの異なるノードを提供することを想定していますが、ノード 3 が 2 回カウントされるため、5 になります。

今、私は j ループで 2 番目のノードを使用して移動しようとしましたが、同じ入力に対して、4 ではなく 2 が返されます。

ここに私が試した新しいコードがありますが、まだ機能していません:

            for (int i = 0; i < quantityOfNode(); i++) {
            boolean isDistinct = true;
            for (int j = 0; j < i; j++) {
                if (node.getInfo().equals(node2.getInfo())) {
                    isDistinct = false;

                }

                if (node2.getNext() != null) {
                    node2 = node2.getNext();
                }

            }
            if (isDistinct) {
                nbDistinct++;
            }
            if (node.getNext() != null) {
                node= node.getNext();
            }
        }
4

5 に答える 5

2

セットでご利用いただけます。

Set set = new HashSet();
Node cur = list.head;
while(cur != null) {
    set.add(cur.getInfo());
    cur = cur.getNext();
}
return set.size();

getInfo の型がわからないため、これはジェネリックを使用しません。

または、セットを使用できない場合は、「インデックス」変数 (i および j) を削除するようにしてください。暗黙的に計算された値ではなく、実際に持っているものにアプリケーション ロジックを集中させたいと考えています。特定の回数進んだときではなく、現在のノードが null になったときに停止する必要があります。それが論理的でない場合は、私に知らせてください。

ノードごとに、そのノードの前にあるノードをチェックして、そのノードが存在するかどうかを確認します。二重リンクがあるかどうかわからないので、毎回頭から始めます。どちらの方法でも複雑さは同じですが、ソートされたリストでは最適ではありません。

Node cur = list.head; // for each node
int nbDistinct = 0;
while(cur != null) { // go until we're out of nodes
    Node check = list.head; // check the first node
    boolean isDistinct = true; // assume distinct
    while(check != cur && isDistinct) { // stop if we found a match OR if our checker caught up to our current node
        isDistinct |= !check.getInfo().equals(cur.getInfo()); // essentially "if(check.getInfo().equals(cur.getInfo()) isDistinct = true;"
        check = check.getNext(); // advance the checker
    }
    if(isDistinct) nbDistinct++;
    cur = cur.getNext(); // advance the current node
}
于 2013-03-27T23:15:17.337 に答える
2

最初の問題:

リンク リストの長さを超えないように for ループが記述されている場合:

for (int i = 0; i < length(); i++) {

では、なぜこれが必要なのですか？

            if (node.getNext().getNext() != null) {
                node= node.getNext();
            }

特に、このコードは、終わりの直前のノードが 2 回評価されることを意味する可能性がありますnull。必ずしもアルゴリズムが間違っているわけではありませんが、悪臭がするので好きではありません。

2番目の問題:

            for (int j = 0; j < i; j++) {
                if (node.getInfo().equals(node.getNext().getInfo())) {
                    isDistinct = false;
                }
            }

これは、比較対象の 2 番目のノードの位置を保存して進めないため、重複を計算するのに不適切な方法です。次のようなものを試してください

            Node node2 = firstNode(); //idk what method gets the first node :)
            for (int j = 0; j < i; j++) {
                if (node.getInfo().equals(node2.getInfo())) {
                    isDistinct = false;
                    break; //optimization, stop as soon as we find a duplicate
                }
                node2 = node2.GetNext();
            }

最後に、動作しないコードに直面したときはいつでも、デバッガーをアタッチしてステップ実行し、コードが期待どおりに動作しない場合に注意してください。これにより、少量の観察だけですべての論理エラーを迅速に解決できます。デバッガーにアクセスできない場合でも、printステートメントを使用して、さまざまな変数の値を出力し、特定のコード分岐が実行されたときに、予想した結果と比較することができます。

于 2013-03-27T23:15:31.240 に答える
1

jループは前進していませnodeん。常に同じノードのペアを比較しているため、機能しません。

次のようなものが必要です：

...
Node earlierNode = rootNode;
for (int j = 0; j < i; j++) {
    if (earlierNode.getInfo().equals(node.getInfo())) {
        isDistinct = false;
    }
    earlierNode = earlierNode.getNext();
}
...
于 2013-03-27T23:35:20.923 に答える
0

iループを初めて使用するときは、jループは何もしません (0 から始まり、j < iそうでない間は続くため) distinct。何も比較せずに true を設定したままにします。

1から始めてみてくださいi。

于 2013-03-27T23:20:39.247 に答える
0

セットを使用する

Set<Node> mySet = new HashSet<Node>(list);
answer = mySet.size();

これは、ノード クラスに hashCode と equals を実装するかどうかによって異なります。代わりに、TreeSet と Comparator を使用することもできます。

Comparator<Node> myComparator = new MyCustomComparator();// you have to define your comparator.
Set<Node> mySet = new TreeSet<Node>(myComparator);
mySet.addAll(list);
answer = mySet.size();
于 2013-03-27T23:14:32.040 に答える