0

タスクを解決しようとしていますが、適切なデータ構造を使用しているかどうかわかりません。私の仕事は、文が一意の文字で構成されているかどうかを調べ、結果としてブール値を返すことです。

これが私の機能です：

bool use_map(string sentence) {
    map<int, string> my_map;

    for (string::size_type i = 0; i <= sentence.length(); i++) {
        unsigned int index = (int)sentence[i];    
        if (my_map.find(index) != my_map.end())
            return false;       
        my_map[index] = sentence[i];
    }

    return true;    
}

自分に適したマップ構造しか見つかりませんでした。多分私は何かを逃しますか？

で動的配列のようなものを使用する方が良いのでしょPHPうか？

ハッシュテーブルソリューションを使用しようとしています。

4

7 に答える 7

4

他の回答が示唆std::setしており、それが解決策です。しかし、それらは 内のすべての文字をコピーしてstd::setから、 のサイズを取得しsetます。これは実際には必要なく、 の戻り値を使用して回避できますstd::set::insert。何かのようなもの：

std::set< char > my_set;
for (std::string::size_type ii = 0; ii < sentence.size(); ++ii) 
{
    if( ! my_set.insert( sentence[ ii ] ).second )
    {
        return false;
    }
}

これにより、次のことができます。

  • 最初に複製された文字で停止すると、文字列全体を（不必要に）コピーしなくなります
  • コード内で不要なキャストを回避intします
  • メモリを節約します-実際に必要ない場合std::map< int, std::string >::second

また、すべての s を「カウント」する必要があること、charまたはそれらの一部 (空白、コンマ、疑問符など) をスキップする必要があることを確認してください。

于 2013-02-10T18:53:35.407 に答える
4

非常に単純な (ただし、かなりメモリを消費する) 方法は次のとおりです。

bool use_map(const std::string& sentence)
{
    std::set<char> chars(sentence.begin(), sentence.end());
    return chars.size() == sentence.size();
}

重複する文字がない場合、文字列とセットの両方のサイズは等しくなります。

@Jonathan Leffler はコメントで良い点を挙げています。通常、文にはいくつかの空白が含まれているため、これはfalse. スペースを除外する必要があります。それでも、std::set選択するコンテナにする必要があります。

編集：

これは、メモリを追加しない O(n) ソリューションのアイデアです。文字が以前に見られたかどうかをマークするルックアップテーブルを使用するだけです：

bool no_duplicates(const std::string& sentence)
{
    static bool table[256];
    std::fill(table, table+256, 0);

    for (char c : sentence) {

        // don't test spaces
        if (c == ' ') continue;
        // add more tests if needed

        const unsigned char& uc = static_cast<unsigned char>(c);
        if (table[uc]) return false;
        table[uc] = true;
    }
    return true;
}
于 2013-02-10T18:51:56.740 に答える
3

簡単な方法は、 などの重複を許可しない連想コンテナーにすべての文字を格納しstd::set、単一の値が含まれているかどうかを確認することだと思います。

#include <set>
#include <string>

bool has_unique_character(std::string const& str)
{
    std::set<char> s(begin(str), end(str));
    return (s.size() == str.size());
}
于 2013-02-10T18:51:45.660 に答える
2

これはどうですか？もちろん、ケースの問題もあります...

bool use_map(const std::string& sentence)
{
    std::vector<bool> chars(26, false);
    for(std::string::const_iterator i = sentence.begin(); i != sentence.end(); ++i) {
        if(*i == ' ' || *i - 'a' > 25 || *i - 'a' < 0) {
            continue;
        } else if(chars[*i - 'a']) {
            return false;
        } else {
            chars[*i - 'a'] = true;
        }
    }

    return true;
}
于 2013-02-10T19:23:12.803 に答える
1

文字を並べ替えてから、両方の文字が等しい隣接するアルファベット文字のペアを探します。このようなもの：

std::string my_sentence = /* whatever */
std::sort(my_sentence.begin(), my_sentence.end());
std::string::const_iterator it =
    std::adjacent_find(my_sentence.begin(), my_sentence.end());
while (it != my_sentence.end() && isalpha((unsigned char)*it)
    it = std::adjacent_find(++it, my_sentence.end());
if (it == my_sentence.end())
    std::cout << "No duplicates.\n";
else
    std::cout << "Duplicated '" << *it << "'.\n";
于 2013-02-10T19:32:55.287 に答える
0

追加のメモリを使用できる場合は、ハッシュ テーブルを使用します。
配列を反復処理し、現在の要素が既にハッシュされているかどうかを確認します。はいの場合、繰り返しが見つかりました。いいえの場合は、ハッシュに追加します。これは線形になりますが、追加のメモリが必要になります。

元のシーケンス要素の範囲が非常に小さい場合、ハッシュの代わりに、範囲サイズの配列を単純に取得して、バケット sortのようにすることができます。例えば

bool hasDuplicate( string s )
{
   int n = s.size();
   vector<char> v( 256, 0 );
   for( int i = 0; i < n; ++i )
      if( v[ s[ i ] ] ) // v[ hash( s[i] ) ] here in case of hash usage
         return true;
      else
         v[ s[ i ] ] = 1; // and here too
   return false;
}

最後に、追加のメモリを使用することが許可されていない場合は、並べ替えて、隣接する 2 つの要素が 1 回のパスで等しいかどうかを確認できます。これにはO(nlogn)時間がかかります。セットやマップは必要ありません:)

于 2013-02-10T19:13:45.653 に答える
0

最速の解決策は次のとおりです。

bool charUsed[256];
bool isUnique(string sentence) {
    int i;
    for(i = 0; i < 256; ++i) {
        charUsed[i] = false;
    }

    int n = s.size();
    for(i = 0; i < n; ++i) {
        if (charUsed[(unsigned char)sentence[i]]) {
            return false;
        }
        charUsed[(unsigned char)sentence[i]] = true;
    }
    return true;
}
于 2013-02-10T20:20:03.123 に答える