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') 中的相应位。如果该索引的位已设置，您可以确定该字符已包含在给定字符串中。

请注意，此算法仅适用于小写字符串，对于大写字符，值会溢出并给出不可靠的结果。对此的一种解决方法是将“检查器”类型从 int 转换为 long。

于 2013-01-14T19:16:49.650 回答
2

我们在这里将每个字符转换为从 0 ('a') 到 25 ('z') 的数字索引

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

在这里，我们看一下二进制表示，checker 例如，如果checker = 001 这意味着我们已经计算了 char 'a'，因为第一位设置为 1。

在这一行中，我们检查是否设置了与当前字母相关的位。1<<val表示00100..00，其中1设置在val左起第-个位置。其他数字为零。关于二进制操作，您可以在 TopCoder阅读

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

这条线checker |= (1 << val);在位置val从左到1中设置位checker。

编辑：checker在这里你可能会 假设bool arr[32]，

和

int val = str.charAt(i) - 'a';一样if(arr[str.charAt(i) - 'a'] == true) ...

并且 checker |= (1 << val);等于arr[val] = true。

因此，在乞求时，您将所有元素都arr设置为零。 val- 是从“a”到“z”的字母的整数表示。

于 2013-01-14T19:23:32.700 回答
1

此代码将每个小写字符的存在存储为 32 位整数中的单个位。

1 << val计算仅设置该位的数字。

于 2013-01-14T19:13:01.143 回答