1

リンクされたリストで円を見つけて、円の先頭にあるノードを返そうとしています。たとえば、リストが A -> B -> C -> D -> C の場合 -- C を返します。

これが私のコードです：

ListNode<T> * findCircle()
{
  map<ListNode<T>*, bool> addresses;

  ListNode<T>* node = head;

  if(addresses.find(node)->second)
    cout << " wtf " << endl;

  while(node)
  { 
    if((addresses.find(node))->second)
    {
      return node;
    } 
    else
      addresses.insert(pair<ListNode<T>*,bool>(node, 1));

    node = node->next;
  }

  return NULL;

}

いくつかの質問を聞きたいんです：

1）これは問題にアプローチする正しい方法ですか

2) キーと値をテーブルに検索/挿入する最も効率的な方法を使用していますか?

3) なぜ機能しないのですか? head を挿入する前に、head のマップをチェックインすると、if ステートメントが実行され、"wtf" が出力されます。私のアルゴリズムは、ノードがマップに見つからない場合は真の値を持つキーとしてノードを挿入し、それ以外の場合はキーが既にマップにある場合はノードを返します。

std::set でこれをやってみましたが、うまくいかなかったので、マップに切り替えました。私を困惑させているのは、まったく同じ方法論を使用して、次のコード (リンクされたリスト内の重複を削除するコード、ルックアップ テーブルを使用) が機能することです。 

  void removeDuplicates()
    {
      map<T, bool> listData;

      ListNode<T> *node;
      ListNode<T> *prev = node;
      for(node = head; node; node = node->next)
      {
        if(listData.find(node->data)->second)
        {
          prev->next = node->next;
          delete node;
        }
        else
        {
          listData.insert( pair<T, bool>(node->data, 1));
        }
        prev = node;
      }
    }

コードの 2 番目のブロックが想定どおりに機能するのに、最初のブロックが機能しないのは単なるまぐれですか?

4

2 に答える 2

2

検索操作が実際にデータを検索するかどうかを確認する必要があります

auto iterator itr = address.find(node);
if(itr != address.end()){
    if(itr->second == true){ cout << "WTF" << endl; }
}

while ループについても同様です。あなたのアプローチに関しては、O（n）の可能な限り最高のランタイムがあると思います。できることは、定数を下げることだけです。

于 2012-11-02T02:01:46.550 に答える
1 
addresses.find(node)->second

が失敗すると、現在未定義の動作が発生します。これは、末尾イテレータのフィールドfind()にアクセスしようとしているためです。second代わりに、

addresses.find(node) != addresses.end()

また、サイクルが存在する正確な場所を見つけることは重要ですか (通常はそう呼ばれます)、それとも単にサイクルが存在するかどうかを確認したいだけですか? 後者の場合、非常に巧妙なアルゴリズムは、2 つのポインターのみを使用して、線形時間と定数空間で問題を解決できます。一方のポインターは他方の 2 倍の速度で移動します:)

于 2012-11-02T02:02:17.653 に答える