1

この問題に対して他のロジックが可能かどうか疑問に思っていました。質問：特定の文字列内のペアの数を見つけて、すべてのペアとペアになっていない要素の合計を出力します。PS：入力では大文字と小文字が区別されます。

O / Pの例：

eeqe 3

aaaa 2

rwertr 5

以下のコードに示すように、最初に入力文字列を並べ替えてから、隣接する要素を比較することで、この問題の解決策を見つけました。

int main()
{
int t,count=0,pos=0;
char swap;
    char a[201];
    cin>>a;
    int len=strlen(a);
    //cout<<a<<endl;
    for (int c = 0 ; c < ( len - 1 ); c++)
    {
for (int d = 0 ; d < len - c - 1; d++)
{
  if (a[d] > a[d+1]) /* For decreasing order use < */
  {
    swap       = a[d];
    a[d]   = a[d+1];
    a[d+1] = swap;
  }
}
}
    //cout<<a<<endl;
    count=0;
    for(int i=0;i<len;){
        if(a[i]==a[i+1]){
            count++;
            i+=2;
            //if(i== len-2)i++;
        }
        else{ count++; i++;}
    }
    //if(a[len-1]!=a[len-2])count++;
    cout<<count<<endl;
return 0;

}

このコードは正常に機能します。しかし、入力配列全体の並べ替えを伴わない、この問題に対する他の効率的な解決策があるかどうか疑問に思っていました。

4

1 に答える 1

1

基本的に、可能な文字は256個しかないという考えに基づいて並べ替えを回避するため、それらを数えるだけで十分です。これが私の解決策です。

int main()
{
  std::string s; std::cin >> s;
  int cnt[256] = {};
  for (std::size_t i = 0; i < s.size(); ++i)
    ++cnt[static_cast<unsigned char>(s[i])];
  int sum = 0;
  for (std::size_t i = 0; i < 256; ++i)
    sum += cnt[i]/2 + cnt[i]%2;
  std::cout << sum << std::endl;
}

たとえば、文字列に5回のが含まれている場合'a'、これにより5/2ペア（整数除算）が可能になり、1はペアになりません（5は奇数=> 5％2は1であるため）

編集：私たちはここSOにいるので：

int main()
{
  std::array<int, 256> cnt{-1}; // last char will be '\0', ignore this.
  std::for_each(std::istreambuf_iterator<char>(std::cin.rdbuf()),
                std::istreambuf_iterator<char>{},
                [&](unsigned char c){++cnt[c];});
  std::cout << std::accumulate(cnt.begin(), cnt.end(), 0,
                               [](int i, int c)->int{return i+(c/2)+(c%2);}) << '\n';
}
于 2013-02-03T00:44:46.353 に答える