9

これは、Gayle Laakmann McDowell によるCracking the Coding Interviewブックの質問の 1 つです。

文字列にすべての一意の文字が含まれているかどうかを判断するアルゴリズムを実装します。追加のデータ構造を使用できない場合はどうなりますか?

著者は次のように書いています。

ビットベクトルを使用することで、スペースの使用量を少し減らすことができます。以下のコードでは、文字列が小文字'a'から'z'. これにより、int を 1 つだけ使用できるようになります。

著者はこの実装を持っています：

public static boolean isUniqueChars(String str) {
    int checker = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i) - 'a';
        if ((checker & (1 << val)) > 0)
            return false;
        checker |= (1 << val);
    }
    return true;
}

「文字列は小文字のみ」という仮定を取り除くとしましょ'a'う'z'。代わりに、文字列には、ASCII 文字や Unicode 文字など、あらゆる種類の文字を含めることができます。

作成者と同じくらい効率的なソリューション (または、作成者のものと同じくらい効率的であることに近いソリューション) はありますか?

関連する質問:

4

7 に答える 7

6

asccii 文字セットの場合、256 ビットを 4 つの long で表すことができます。基本的には配列を手作業でコーディングします。

public static boolean isUniqueChars(String str) {
    long checker1 = 0;
    long checker2 = 0;
    long checker3 = 0;
    long checker4 = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i);
        int toCheck = val / 64;
        val %= 64;
        switch (toCheck) {
            case 0:
                if ((checker1 & (1L << val)) > 0) {
                    return false;
                }
                checker1 |= (1L << val);
                break;
            case 1:
                if ((checker2 & (1L << val)) > 0) {
                    return false;
                }
                checker2 |= (1L << val);
                break;
            case 2:
                if ((checker3 & (1L << val)) > 0) {
                    return false;
                }
                checker3 |= (1L << val);
                break;
            case 3:
                if ((checker4 & (1L << val)) > 0) {
                    return false;
                }
                checker4 |= (1L << val);
                break;
        }            
    }
    return true;
}

次のコードを使用して、Unicode 文字用の同様のメソッドの本体を生成できます。

static void generate() {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < 1024; i++) {
        sb.append(String.format("long checker%d = 0;%n", i));
    }
    sb.append("for (int i = 0; i < str.length(); ++i) {\n"
            + "int val = str.charAt(i);\n"
            + "int toCheck = val / 64;\n"
            + "val %= 64;\n"
            + "switch (toCheck) {\n");
    for (int i = 0; i < 1024; i++) {
        sb.append(String.format("case %d:\n"
                + "if ((checker%d & (1L << val)) > 0) {\n"
                + "return false;\n"
                + "}\n"
                + "checker%d |= (1L << val);\n"
                + "break;\n", i, i, i));
    }
    sb.append("}\n"
            + "}\n"
            + "return true;");
    System.out.println(sb);
}
于 2014-01-11T02:54:01.033 に答える
2

「追加のデータ構造」の一般的かつ実用的な定義が必要だと思います。直感的には、すべてのスカラー整数またはポインターを「データ構造」と呼びたくありません。これは、「追加のデータ構造」の禁止が意味をなさないためです。

big-O 表記法から概念を借用することを提案します。「追加のデータ構造」とは、データセットのサイズとともに成長するものです。

現在のケースでは、OP によって引用されたコードは、ビット ベクトルがたまたま整数型に適合するため、O(1) のスペース要件を持っているように見えます。しかし、OP が示すように、問題の一般的な形式は実際には O(N) です。

一般的なケースの解決策の例は、2 つのポインターとネストされたループを使用して、すべての文字を他のすべての文字と単純に比較することです。スペース要件は O(1) ですが、時間要件は O(N^2) です。

于 2014-01-11T06:23:18.927 に答える