4

我不明白循环中的行：我们取字符并减去a，所以“10”？（为什么？）
然后1 << val：我们将 1 移 val ？（为什么？）
而 checker 为 0，那么我们如何达到> 0这个条件呢？

    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;
}

谢谢

4

3 回答 3

8

代码假定它str由小写字母组成，如果没有重复字母，则返回 true。它是这样工作的：

checker用作位图，即该变量中的每一位用于跟踪一个字母。从字符中减去“a”，“a”为 0，“b”为 1，“c”为 2，依此类推。将 1 左移此数字为 1，“a”为 1，“b”为 2，“c”为 4 ' ETC。

通过 oring ( |) 这个值与checker代码保持跟踪以前遇到的字符。因此，如果我们遇到第二个“a”，例如，checker它的第一位设置（&在 if 语句中由测试），所以我们知道它str有重复。

简而言之，checker用作更快更紧凑的 bool 数组。这种和类似的技术称为位操作。

于 2012-05-28T12:38:38.437 回答
1

str.charAt(i) - 'a'或多或少地返回“字母表中的字母”：如果str.charAt(i)是'a'，这是0，如果是'b'，val是1，如果是z，val是25，等等。

剩下的就是使用位旋转技术：如果第valth 位checker是1，那么我们已经看到了val第 th 字符。checker & (1 << val)当且仅当设置 的val第 位时，非零也是如此checker，这意味着我们已经看到了该字符。否则，我们设置第valth 位checker并继续循环。

于 2012-05-28T12:37:56.113 回答
1

这个问题很老了，但我认为我的回答是正确和清晰的。我们只在这种情况下处理小写字母。就像保罗问的那样，(1 << val)意味着 Shift 1 by 'val' 而不是 shift 'val' 。例如，'hello' 给出：

1st loop: val = 111 in binary, 7 in decimal
          1 << val = 10000000  <-- here one is shifted by 7
          checker = 10000000 
2nd loop: val = 100 in binary, 4 in decimal
          1 << val = 10000
          checker = 10010000
3rd loop: val = 1011 in binary, 11 in decimal
          1 << val = 100000000000
          checker = 100010010000
4th loop: val = 1011 in binary, 11 in decimal
          1 << val = 100000000000
         (checker & (1 << val)) gives 100000000000 which is greater than 0
The loop is over because 'l' is not unique after 'hel' in 'hello'.

我希望这能解决问题。如果你想看看到底发生了什么，我有源代码。

public class one_one_one {

    public static void main(String[] args) {
    String chars = "hello"; 
    if (isUniqueChars(chars)) {
        System.out.println("Unique");
    } else {
        System.out.println("Not Unique");
    }
    }

    public static boolean isUniqueChars(String str) {
    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i) - 'a';
        System.out.println(Integer.toBinaryString(val)); //debug printout
        int temp = 1 << val;
        System.out.println(Integer.toBinaryString(temp)); //debug printout
        System.out.println(checker & (1 << val)); //debug printout
        if ((checker & (1 << val)) > 0) {
        return false;
        }
        checker |= (1 << val);
        System.out.println(Integer.toBinaryString(checker)); //debug printout
        System.out.println(' '); //debug printout
    }
    return true;
    }
}
于 2015-06-02T06:01:43.480 回答