检测字符串是否具有唯一字符：将我的解决方案与“破解编码面试？”进行比较

Question

我正在阅读“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 中 String 的索引函数的复杂度是 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;
}

我对解决方案不太了解的几件事。首先，“|=”运算符的作用是什么？为什么要从字符串中的当前字符中减去’a’以获得“val”的值？我知道“<<”是按位左移，但是 (checker & (1<<val)) 是做什么的？我知道它是按位和，但我不理解它，因为我不理解检查器获取值的那一行。

我只是不熟悉这些操作，不幸的是这本书没有给出解决方案的解释，可能是因为它假设你已经了解这些操作。

原文由 Seephor 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这里有两个不同的问题：您的解决方案的效率如何，以及参考解决方案的作用是什么？让我们独立对待每个人。

首先，您的解决方案：

 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 )。

但是，您的代码有些问题。尝试在字符串 aab 上运行它。它在此输入上是否正常工作？提示一下，一旦确定有两个或更多重复字符，就可以保证存在重复字符，并且可以返回并非所有字符都是唯一的。

现在，让我们看一下参考资料：

 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 个不同的字符，并且 int 中有 32 位，因此该解决方案创建了一个 int 变量，其中变量的每一位对应于字符串中的一个字符.该解决方案不是读取和写入数组，而是读取和写入数字的位。

例如，看看这一行：

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

checker & (1 << val) 是做什么的？嗯， 1 << val 创建了一个 int 值，除了 val 位之外所有位都为零。然后它使用按位 AND 将该值与 checker 进行 AND 运算。如果 — 中位置 val checker 位已经设置，那么它的计算结果为非零值（意味着我们已经看到了数字）并且我们可以返回 false。否则，它的计算结果为 0，我们还没有看到该数字。

下一行是这样的：

 checker |= (1 << val);

这使用“带赋值的按位或”运算符，相当于

checker = checker | (1 << val);

此 OR checker 的值仅在位置 val 处设置了 1 位，这会打开该位。这相当于将数字的 val 位设置为 1。

这种方法比你的快得多。首先，由于该函数首先检查字符串的长度是否大于 26（我假设 256 是错字），因此该函数永远不必测试任何长度为 27 或更大的字符串。因此，内循环最多运行 26 次。每次迭代在按位运算中执行 O(1) 工作，因此完成的总体工作是 O(1)（O(1) 次迭代乘以每次迭代 O(1) 工作），这 比 您的实现快得多。

如果您还没有看到按位运算以这种方式使用，我建议您在 Google 上搜索“按位运算符”以了解更多信息。

希望这可以帮助！

原文由 templatetypedef 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

这本书的解决方案是我不喜欢的，我认为它功能失调….. 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;
}

原文由 rolfl 发布，翻译遵循 CC BY-SA 3.0 许可协议