1

キーと値のペアのリストがあり、値がキーと一致するリスト内のチェーンを検出する必要があります。

たとえば、下から 12、23、34 または 62、23、34 の可能性があります。

Key  Value
1    2
3    4
2    3
6    2

複数の値が同じキーを指している可能性がありますが、一意の開始点と終了点ごとに異なる「チェーン」を保存する必要があります。リストは任意の順序である可能性があります。

私はJavaを使用していますが、この問題に取り組む方法に少しこだわっています.

助けてください！

4

3 に答える 3

0

を作成しMap<Integer, List<Integer>>、すべてのペアをそのマップに保存してから、マップを繰り返します。

擬似コード:

// 1st step
foreach(key, value){
    if(!map.containsKey(key)){
        map.put(key, new ArrayList());
    }
    map.get(key).add(value);
}
// 2nd step
foreach(entry /* of map */){
    if(map.containsKey(entry.value)){
       // print pairs
    }
}

明らかに、これはコンパイルされない擬似コードですが、開始する必要があります

于 2012-04-16T14:28:07.360 に答える
0

再帰！

import java.util.HashMap;
import java.util.Map;

public class Chain
{
    private static Map< String , String > map;

    public static void main( String args[] )
    {
        map = new HashMap< String , String >();

        map.put( "1" , "2" );
        map.put( "3" , "4" );
        map.put( "2" , "3" );
        map.put( "6" , "2" );

        for ( String key : map.keySet() )
        {
            System.out.print( "(" + key + "," + map.get( key ) + ")" );
            recurse( map.get( key ) );
            System.out.println();
        }
    }

    private static void recurse( String value )
    {
        if ( map.containsKey( value ) )
        {
            System.out.print( " (" + value + "," + map.get( value ) + ")" );
            recurse( map.get( value ) );
        }
    }
}

次の出力が得られます。

(3,4)
(2,3) (3,4)
(1,2) (2,3) (3,4)
(6,2) (2,3) (3,4)
于 2012-04-16T14:41:23.510 に答える
0

これは宿題のように思えるので、完全な解決策を提供するのではなく、問題を自分で解決するためのヒントを提供します。

  1. マップ内の任意のキーについて、 を呼び出すことで対応する値を取得できますMap.get(key)。
  2. 任意の値をキーとして使用して、対応する値を取得できます (存在する場合)。
  3. を使用して、マップ内のすべてのキーを反復処理できますMap.getKeys()。

チェーンのみを出力したい場合は、これで十分です。チェーンを別のデータ構造に保存したい場合は、詳細を教えてください。

于 2012-04-16T14:29:50.530 に答える