53

私は本「Cracking the Coding Interview」に取り組んでおり、ここで回答を求める質問に出くわしましたが、私の回答と解決策を比較する助​​けが必要です. 私のアルゴリズムは機能しますが、本の解決策を理解するのに苦労しています。主な理由は、一部のオペレーターが実際に何をしているのか理解できないからです。

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

これが私の解決策です：

public static boolean checkForUnique(String str){
    boolean containsUnique = false;

    for(char c : str.toCharArray()){
        if(str.indexOf(c) == str.lastIndexOf(c)){
            containsUnique = true;
        } else {
            containsUnique = false;
        }
    }

    return containsUnique;
}

うまくいきますが、これはどのくらい効率的ですか？Java の文字列のインデックス関数の複雑さは O(n*m) であることがわかりました

本からの解決策は次のとおりです。

public static boolean isUniqueChars(String str) {
    if (str.length() > 256) {
        return false;
    }
    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;
}

私が解決策についてよく理解していないことがいくつかあります。まず、「|=」演算子は何をするのでしょうか? 「val」の値として、文字列の現在の文字から「a」が減算されるのはなぜですか? 「<<」がビットごとの左シフトであることは知っていますが、どう(checker & (1<<val))すればよいでしょうか? 私はそれがビット単位であることを知っていますが、チェッカーが値を取得する行を理解していないため、理解していません。

私はこれらの操作に精通していません。残念ながら、この本では解決策について説明していません。おそらく、これらの操作を既に理解していることを前提としているためです。

4

7 に答える 7

110

ここには 2 つの個別の質問があります。ソリューションの効率はどのくらいか、参照ソリューションは何を行っているかです。それぞれを独立して扱いましょう。

まず、あなたのソリューション：

public static boolean checkForUnique(String str){
    boolean containsUnique = false;

    for(char c : str.toCharArray()){
        if(str.indexOf(c) == str.lastIndexOf(c)){
            containsUnique = true;
        } else {
            containsUnique = false;
        }
    }

    return containsUnique;
}

あなたのソリューションは基本的に、文字列内のすべての文字 (n 個あるとしましょう) のループで構成され、各反復で文字の最初と最後のインデックスが同じかどうかをチェックします。indexOfおよびlastIndexOfメソッドは、文字列のすべての文字をスキャンして、探している文字と一致する文字があるかどうかを判断する必要があるため、それぞれ O(n) の時間がかかります。したがって、ループは O(n) 回実行され、反復ごとに O(n) 回実行されるため、その実行時間は O(n 2 ) です。

しかし、あなたのコードには何か不確かなものがあります。string で実行してみてくださいaab。この入力で正しく動作しますか? ヒントとして、2 つ以上の重複文字があると判断するとすぐに、重複があることが保証され、すべての文字が一意であるとは限らないことを返すことができます。

それでは、リファレンスを見てみましょう。

public static boolean isUniqueChars(String str) {
    if (str.length() > 256) { // NOTE: Are you sure this isn't 26?
        return false;
    }
    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;
}

この解決策はかわいいです。基本的な考え方は次のとおりです。26 個のブール値の配列があり、それぞれが特定の文字が文字列に既に出現しているかどうかを追跡しているとします。あなたはそれらすべてを偽で始めます。次に、文字列の文字を繰り返し処理し、文字が表示されるたびに、その文字の配列スロットを調べます。の場合falseは、そのキャラクターを初めて見たので、スロットを に設定できますtrue。の場合true、このキャラクターは既に見たことがあり、重複があることをすぐに報告できます。

このメソッドはブール値の配列を割り当てないことに注意してください。代わりに、巧妙なトリックを選択します。26 種類の文字しか使用できず、 には 32 ビットしかないためint、このソリューションでは、int変数の各ビットが文字列内の文字の 1 つに対応する変数を作成します。配列を読み書きする代わりに、ソリューションは数値のビットを読み書きします。

たとえば、次の行を見てください。

if ((checker & (1 << val)) > 0) return false;

何をしchecker & (1 << val)ますか？さて、th ビットを除くすべてのビットがゼロ1 << valの値を作成します。次に、ビットごとの AND を使用して、この値と の AND をとります。の位置のビットがすでに設定されている場合、これはゼロ以外の値に評価され (数値が既に表示されていることを意味します)、false を返すことができます。それ以外の場合は 0 と評価され、数値は表示されません。intvalcheckervalchecker

次の行は次のとおりです。

checker |= (1 << val);

これは、次と同等の「代入付きビット単位 OR」演算子を使用します。

checker = checker | (1 << val);

checkerこれは、位置 のみに 1 ビットが設定されている値とOR演算をval行い、ビットをオンにします。これvalは、数値の th ビットを 1 に設定することと同じです。

このアプローチは、あなたのものよりもはるかに高速です。まず、関数は文字列の長さが 26 を超えるかどうかをチェックすることから始まるため (256 はタイプミスだと思います)、関数は長さが 27 以上の文字列をテストする必要はありません。したがって、内側のループは最大 26 回実行されます。各反復はビットごとの演算で O(1) の作業を行うため、実行される全体の作業は O(1) (O(1) の反復×反復ごとの O(1) の作業) であり、実装よりも大幅に高速です。

このように使用されているビット単位の演算を見たことがない場合は、Google で「ビット単位の演算子」を検索して詳細を確認することをお勧めします。

お役に立てれば！

于 2013-10-21T00:23:46.680 に答える
14

本の解決策は私が気に入らないものであり、機能不全であると思います..... templatetypedef は、解決策が優れていることを示す包括的な回答を投稿しました。この本の回答では、文字列に小文字 (ascii) のみが含まれていると想定されており、それを確認するための検証が行われていないため、私は同意しません。

public static boolean isUniqueChars(String str) {
    // short circuit - supposed to imply that
    // there are no more than 256 different characters.
    // this is broken, because in Java, char's are Unicode,
    // and 2-byte values so there are 32768 values
    // (or so - technically not all 32768 are valid chars)
    if (str.length() > 256) {
        return false;
    }
    // checker is used as a bitmap to indicate which characters
    // have been seen already
    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
        // set val to be the difference between the char at i and 'a'
        // unicode 'a' is 97
        // if you have an upper-case letter e.g. 'A' you will get a
        // negative 'val' which is illegal
        int val = str.charAt(i) - 'a';
        // if this lowercase letter has been seen before, then
        // the corresponding bit in checker will have been set and
        // we can exit immediately.
        if ((checker & (1 << val)) > 0) return false;
        // set the bit to indicate we have now seen the letter.
        checker |= (1 << val);
    }
    // none of the characters has been seen more than once.
    return true;
}

要点は、templatedef の回答も考慮して、本の回答が正しいかどうかを判断するのに十分な情報がないということです。

不信感はあるけど。

複雑さに関するtemplatedefの答えは、私が同意するものです.... ;-)

編集：演習として、本の答えをうまくいくものに変換しました（本の答えよりも遅いですが-BigIntegerは遅いです）...このバージョンは本のと同じロジックを実行しますが、同じ検証と仮定の問題 (ただし、速度は遅くなります)。ロジックも表示すると便利です。

public static boolean isUniqueChars(String str) {
    if (str.length() > 32768) {
        return false;
    }
    BigInteger checker = new BigInteger(0);
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i);
        if (checker.testBit(val)) return false;
        checker = checker.setBit(val);
    }
    // none of the characters has been seen more than once.
    return true;
}
于 2013-10-21T00:32:07.523 に答える
4

値は 256 の異なる値の 1 つしか保持できないためchar、256 文字を超える文字列には少なくとも 1 つの重複が含まれている必要があります。

コードの残りの部分では、checker各ビットが 1 文字を表す一連のビットとして使用されます。= 1で始まる各文字を整数に変換するようaです。次に、 の対応するビットをチェックしcheckerます。設定されている場合は、文字が既に表示されていることを意味し、文字列に少なくとも 1 つの重複文字が含まれていることがわかります。文字がまだ表示されていない場合、コードは対応するビットを設定しcheckerて続行します。

具体的には、position に 1 ビット(1<<val)の整数を生成します。たとえば、バイナリ、または 8 になります。 で position のビットが設定されていない (つまり、値が 0 である)場合、式は 0 を返します。そのビットが設定されている場合、これは常に非ゼロです。式はそのビットを に設定します。1val(1<<3)1000checker & (1<<val)valchecker(1<<val)checker |= (1<<val)checker

ただし、このアルゴリズムには欠陥があるようです。大文字と句読点 (通常、辞書式に小文字よりも前に来る) を考慮していないようです。また、標準ではない 256 ビット整数が必要なようです。

以下のコメントでrolflが言及しているように、私はあなたのソリューションが機能するので気に入っています。false一意でない文字を識別したらすぐに戻ることで最適化できます。

于 2013-10-21T00:17:46.607 に答える