java - 检测字符串是否具有唯一字符 : comparing my solution to "Cracking the Coding Interview?"

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)) 是什么意思？做？我知道它是按位的，但我不理解它，因为我不理解 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²)。

但是，您的代码有些问题。尝试在字符串 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 个 boolean 值组成的数组，每个 boolean 值都跟踪特定字符是否已经出现在字符串中。你一开始都是假的。然后，您遍历字符串的字符，每次看到一个字符时，您都会查看该字符的数组槽。如果是 false ，这是您第一次看到这个角色，您可以将插槽设置​​为 true .如果是 true ，你已经看到了这个角色，你可以立即报告有重复。

请注意，此方法不分配 boolean 数组。相反，它选择了一个聪明的把戏。由于可能只有 26 个不同的字符，并且 int 中有 32 位。 ，解决方案创建一个 int变量，其中变量的每一位对应于字符串中的一个字符。该解决方案不是读取和写入数组，而是读取和写入数字的位。

例如，看这一行:

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

checker & (1 << val) 是什么意思？做？好吧，1 << val创建一个 int除 val 外所有位为零的值位。然后它使用按位 AND 将此值与 checker .如果位置 val 的位在 checker已经设置好了，那么它的计算结果是一个非零值(意味着我们已经看到了这个数字)，我们可以返回 false。否则，它的计算结果为 0，我们还没有看到这个数字。

下一行是这样的:

checker |= (1 << val);

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

checker = checker | (1 << val);

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

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

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

希望这会有所帮助!