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

Question

我正在阅读《破解编码面试》一书，在这里遇到了一些问题以寻求答案，但是我需要帮助将我的答案与解决方案进行比较。我的算法有效，但是我很难理解书中的解决方案。主要是因为我不了解某些操作员的实际操作。

任务是：“实施一种算法来确定字符串是否具有所有唯一字符。如果无法使用其他数据结构该怎么办？”

这是我的解决方案：

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))办？我知道它是按位的，但是我不理解它，因为我不理解checker获得值的那一行。

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

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

例如，看下面这行：

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

怎么checker & (1 << val)办？好吧，1 << val创建一个int除val第th位外所有位均为零的值。然后，它使用按位AND将该值与进行与checker。如果位置valin
的位checker已设置，则该值将为非零值（表示我们已经看过该数字），并且可以返回false。否则，它的值为0，我们还没有看到这个数字。

下一行是这样的：

checker |= (1 << val);

这使用“按位或与赋值”运算符，等效于

checker = checker | (1 << val);

该OR checker的值仅在position处设置了1位val，从而将其打开。等同于将数字的val第一位设置为1。

这种方法比您的方法快得多。首先，由于该函数通过检查字符串的长度是否大于26（我假设256是一个错字）而开始，因此该函数从不必测试任何长度为27或更大的字符串。因此，内部循环最多运行26次。每次迭代确实在位运算O（1）工作，所以做了整体的工作是O（1）（O（1）次迭代O（1）每次迭代工作），这是
显著 比你更快地实现。

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

希望这可以帮助！