2

私はオンラインで見つけたプログラムを持っています。これは基本的に、Stringにすべての一意の文字が含まれているかどうかを示します。以下はコードです

private static boolean areCharsUnique(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;
    }

私はこのコード行if ((checker & (1 << val)) > 0)とまた

checker |= (1 << val);

私はそれ<<が左シフト演算子であることを知っていますが、上記の状況でどのように正確に左シフトが役立つのでしょうか？

要するに、上記のプログラムはどのように機能しますか？

4

4 に答える 4

7

このコードは、ASCII 文字セットがそのマッピングに連続した文字を持っているという仮定の下で機能するa == 97, b == 98ため、.

aこれから開始して、キャラクターからのデルタ距離を計算できます'e' - 'a' = 5。この距離は、( を介してchecker |= (1 << val)) 整数 (32 ビット) のビットを設定するために使用されます。

したがって、'e'文字が見つかった場合、インデックス 5 のビットが 1 に設定されcheckerます。

これは、( によって) 以前に設定されたビットが見つからないようにすることで、すべての文字に対して行われますif (checker & (1 << val)) > 0)。

これは小文字に対してのみ機能します (int が 32 ビットであっても)。アンのHashSet<Character>方が絶対いいです。

于 2013-01-14T19:16:02.580 に答える
2

各文字は、0 (== 'a') から 26 (== 'z') までの数値インデックスに変換されます。これらのインデックスのそれぞれについて、整数値 (== 'checker') の対応するビットが設定されます。そのインデックスのビットがすでに設定されている場合は、その文字が指定された文字列に既に含まれていると判断できます。

このアルゴリズムは小文字の文字列に対してのみ機能することに注意してください。大文字の場合、値がオーバーフローし、信頼できない結果が得られます。これに対する 1 つの修正方法は、「チェッカー」タイプを int から long に変換することです。

于 2013-01-14T19:16:49.650 に答える
2

ここでは、各文字を 0 ('a') から 25 ('z') までの数値インデックスに変換します。

 int val = str.charAt(i) - 'a';

ここでは、たとえば、 最初のビットが 1 に設定されているため、文字 'a' が既にカウントされていることを意味するchecker 場合のバイナリ表現を見ていきます。checker = 001

この行では、現在の文字に関連するビットが設定されているかどうかを確認します。ここで、1<<valは左から - 番目の位置に設定されます。他の桁はゼロです。TopCoderで読める二項演算について00100..001val

if ((checker & (1 << val)) > 0) {...}

この行は、左からinchecker |= (1 << val);の位置にビットを設定します。val1checker

編集: ここでcheckerはbool arr[32]、

と

int val = str.charAt(i) - 'a';と同じif(arr[str.charAt(i) - 'a'] == true) ...

と checker |= (1 << val);等しいarr[val] = trueです。

したがって、懇願すると、 set のすべての要素がarrゼロに設定されます。 val- 'a' から 'z' までの文字の整数表現です。

于 2013-01-14T19:23:32.700 に答える
1

このコードは、各小文字の存在を32ビット整数の1ビットとして格納します。

1 << valそのビットセットのみを使用して数値を計算します。

于 2013-01-14T19:13:01.143 に答える