实现一种算法以确定字符串是否具有所有唯一字符

Question

请帮助我理解 For..Loop。 if 语句如何在 For 循环语句中工作。我特别关注 if 语句以及以下语句的工作原理：if ((checker & (1 << val)) > 0) return false; checker |= (1 << val);

/* Assumes only letters a through z. */
    public static boolean isUniqueChars(String str) {
        if (str.length() > 26) { // Only 26 characters
            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;
    }

Answer 1

正如您在 post 下的评论中所说，检查变量用作 26 个值的布尔值，每个字母一个。

以下部分将字符转换为0到25之间的十进制表示（26个不同字母的26个可能值）

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

所以'a'变成0，'b'变成1等等。

之后，if语句检查后面的字母是否已经出现过，检查checker变量中字母值val位置的位是否已经出现设置为 1 意味着该字母已经在字符串中。

这里有一个小演示：

tet

t -> 116 - 97 = 19
e -> 101 - 97 = 4 
t -> 116 - 97 = 19

checker: 00000000000000000000000000

first iteration
   00000000000000000000000000 <- checker
 & 00000000000000000000000001 << 19
 ___________________________________

   00000000000000000000000000
 & 00000010000000000000000000
 ___________________________________
   00000000000000000000000000 = 0


second iteration
   00000010000000000000000000 <- checker
 & 00000000000000000000000001 << 4
 ___________________________________

   00000010000000000000000000
 & 00000000000000000000010000
 ___________________________________
   00000000000000000000000000 = 0


third iteration
   00000010000000000000010000 <- checker
 & 00000000000000000000000001 << 19
 ___________________________________

   00000010000000000000010000
 & 00000010000000000000000000
  ___________________________________
   00000010000000000000000000 = 524288 > 0

<<、& 和 | 是按位运算符。在您的示例中，<< 基本上将 1 移动到左侧，& 检查该位置是否已经存在 1。当然，这些是最简单的解释，但这就是您的示例中发生的情况。

它不在示例中，但在每次迭代结束之前，checker 会更新，因此 1 已设置为较小的数字，变为设置在 checker 中.

在第三次迭代中，由于在检查的位置已经有一个 1（在第一次迭代中设置了 1），结果将在同一位置包含 1，所以整个结果数将大于零，这实际上是在 if 语句中检查的。因此，如果数字大于 0，则表示 checker 在 val.

的位置设置了 1

您甚至可以在 Wikipedia.

上找到有关按位运算符的更多有用信息

正如我所说，我尽可能地简化了问题，这只是一个大概的想法。

实现一种算法以确定字符串是否具有所有唯一字符

implement an algorithm to determine if a string has all unique characters

java

bit-shift