1

2つの文字列S1とS2が与えられた場合、S = S1-S2は、S1からS2のすべての文字を取得した後の残りの文字列として定義されます。任意の文字列のS1-S2をできるだけ速く計算する方法は？

例えば ​​：

入力：

彼らは学生です。

aeiou

出力：

あなたの標準。

私はハッシュマップを試しました、sadlly裁判官はそれが遅すぎると言いました、しかしどんな解決策もより速くすることができますか？

これが私のコードです：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
bool occur[300]={false};
int main()
{
    char str1[10002];
    gets(str1);
    char ch;
    while((ch=getchar())!='\n')
        occur[ch]=true;
    int i;
    for(i=0;i<strlen(str1);i++)
        if(occur[str1[i]])
            continue;
        else
            putchar(str1[i]);
    putchar('\n');
    return 0;
}
4

4 に答える 4

2

私はあなたがすべきだと思います：

  1. S2 のすべての文字を含む HashSet S を作成します
  2. S にない S1 を反復処理するときに文字を追加する List を使用します。
  3. リストから文字列を作成します (Python では "".join(list..))

より速い方法はないと思います..S1をN個の部分に分割して、これと並行して作業することができます-これは私が見る唯一の最適化です...

コードに関しては、ループ条件で strlen を使用しないでください。参照: strlen: どのように機能しますか? . 「\ 0」文字を取得するまですべての文字を反復するか、strlenを1回計算して、ループ条件で使用する変数に入れます...

于 2013-03-10T10:48:00.570 に答える
1

問題を小さなアルファベット (英語の文字のみなど) に制限できる場合は、代わりにアルファベットのサイズの bool 配列を作成できます。

1 つの配列ルックアップは、バイナリ ツリーのハッシュまたはトラバースよりもはるかに高速です。

于 2013-03-10T10:50:49.973 に答える
0

おそらく、これを行うための最も速くて簡単な方法の 1 つは、正規表現の置換を使用することです。以下のサンプル Python コードを参照してください。

正規表現を使用できない場合は、入力文字列の各文字に対して 1 つのループが必要になります。すべての文字に取り組んでいるため、アルゴリズムは少なくともO(n). これは、実装を高速化する唯一の方法は、文字を出力にコピーする必要があるかどうかのチェックと、実際の出力へのコピーにかかる時間を短縮することであることを意味します。使用している言語がわからないので、Python での簡単な実装を示します。setこれは、値がセット内にあるかどうかを一定時間チェックできるpythonクラスを使用します。サンプルコードを以下に示します。

import re

def remove1(string, chars):
    return re.sub("[%s]"%chars, "", string)

def remove2(string, chars):
    chars = set(chars)
    res = ""
    for c in string:
        if c not in chars:
            res += c

    return res

import unittest

class TestRemove(unittest.TestCase):
    def test_removeVowels1(self):
        self.assertEqual("Thy r stdnts.", remove1("They are students.","aeiou"))

    def test_removeVowels1(self):
        self.assertEqual("Thy r stdnts.", remove2("They are students.","aeiou"))

if __name__=="__main__":
    unittest.main()

注: C++ などの言語を使用していて、入力が 8 ビット値に制限されていることがわかっている場合は、直接アドレス指定を使用するのが最も速い方法です。つまり、文字値を配列インデックスとして使用します。

于 2013-03-10T12:09:40.097 に答える
0

技術的には、ハッシュマップの解は O(n)+O(m) でnあり、文の長さとm禁止文字の量です。

私の見解では、これは、その文字を保持するか破棄するかを決定する文を実行する必要があるため、取得できるのと同じくらい高速です. また、それらを知るために、すべての禁止文字を少なくとも 1 回実行する必要があります。

しかし、提示されたものよりも効率的なソリューション、つまりオーバーヘッドの少ないソリューションがあると想像できます。でも正直、思いつきません。

更新（これは可能な限り最も単純ですが、O（n * m）です。ただし、短い文字列の場合は他のアプローチよりも高速になる場合があります）：

foreach (c in sentence) 
  if (forbiddenChars.IndexOf(c) == -1) 
    Console.Write(c);
于 2013-03-10T12:12:37.023 に答える