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

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))做了什么？我知道它是按位的,但我不理解它,因为我不理解检查器获取值的行.

我只是不熟悉这些操作,遗憾的是本书没有给出解决方案的解释,可能是因为它假设您已经理解了这些操作.

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个布尔数组成的数组,每个布尔值都跟踪一个特定字符是否已经出现在字符串中.你从他们所有的假开始.然后迭代遍历字符串的字符,每次看到一个字符时,都会查看该字符的数组插槽.如果是的话false,这是你第一次看到角色,你可以设置插槽true.如果是的话true,你已经看过这个角色,你可以立即报告有重复.

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

例如,看看这一行:

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

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

下一行是这样的:

checker |= (1 << val);

这使用"按位OR与赋值"运算符,相当于

checker = checker | (1 << val);

这个OR checker的值仅在位置设置1位val,从而使该位置1.它相当于将数字的val第th位设置为1.

这种方法比你的快得多.首先,由于函数通过检查字符串的长度是否大于26(我假设256是一个拼写错误)开始,该函数永远不必测试任何长度为27或更大的字符串.因此,内环最多运行26次.每次迭代做O(1)位运算的工作,所以做了整体的工作是O(1)(O(1)上的迭代时间O(1)每次迭代工作),这是显著比你更快地实现.

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

希望这可以帮助!

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