检测一个string是否有独特的字符：比较我的解决scheme“破解编码面试？”
我正在通过“破解编码采访”一书的工作，我在这里遇到问题要求答案，但我需要帮助比较我的答案和解决scheme。 我的algorithm可行，但我很难理解本书中的解决scheme。 主要是因为我不明白一些运营商在做什么。
任务是：“实现一个algorithm来确定一个string是否具有所有唯一的字符，如果不能使用额外的数据结构怎么办？
这是我的解决scheme：
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）
以下是本书的解决scheme：
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; }
有些事情我对解决scheme不甚了解。 首先，“| =”运算符是做什么的？ 为什么从string中的当前字符中减去“a”的值“val”？ 我知道“<<”是一个左移位，但(checker & (1<<val))做什么的？ 我知道它是按位，但我不理解它，因为我不理解检查器获得价值的行。
我只是不熟悉这些操作，不幸的是本书没有给出解决scheme的解释，可能是因为它假定你已经理解了这些操作。
这里有两个独立的问题：你的解决scheme的效率是多less？参考解决scheme在做什么？ 让我们分别对待每一个。
首先，你的解决scheme：
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; }
你的解决scheme基本上包括一个循环遍历string中的所有字符（假设有n个字符），检查每个迭代中字符的第一个和最后一个索引是否相同。 indexOf和lastIndexOf方法每个都需要O（n）的时间，因为它们必须扫描string的所有字符，以确定它们中的任何一个是否与您正在查找的字符相匹配。 因此，由于你的循环运行O（n）次并且O（n）每次迭代都工作，所以它的运行时间是O（n 2 ）。
但是，有一些关于你的代码的东西。 尝试在stringaab上运行它。 它在这个input上工作正确吗？ 作为一个提示，只要你确定有两个或两个以上重复的字符，你保证有重复的，你可以返回并非所有的字符都是唯一的。
现在，我们来看看这个参考：
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; }
这个解决scheme很可爱。 其基本思想如下：假设你有一个26个布尔值的数组，每个布尔值都跟踪一个特定的字符是否已经出现在string中。 你开始他们都是假的。 然后遍历string的字符，并且每次看到一个字符时，都会查看该字符的数组槽。 如果它是false ，这是你第一次看到这个angular色，你可以把这个槽设置为true 。 如果这是true ，你已经看到这个angular色，你可以立即报告有重复。
注意这个方法没有分配一个布尔值数组。 相反，它select了一个聪明的把戏。 由于只有26个不同的字符是可能的，并且在一个int有32位，所以解决scheme创build一个intvariables，其中variables的每一位对应于string中的一个字符。 该解决scheme读取和写入数字的位，而不是读取和写入数组。
例如，看这一行：
if ((checker & (1 << val)) > 0) return false;
checker & (1 << val)做什么的？ 那么， 1 << val会创build一个int值，除了第val个位以外，所有的位都是零。 然后，它使用按位与与checker这个值。 如果checker中位置val的位已经被设置，那么这个值就是一个非零值（意味着我们已经看到了这个数字），我们可以返回false。 否则，它评估为0，我们没有看到这个数字。
下一行是这样的：
checker |= (1 << val);
这使用“按位或与赋值”运算符，这相当于
checker = checker | (1 << val);
这个ORs checker的值只有在位置val设置了一个1位，打开了这个位。 这相当于将数字的第个位设置为1。
这种方法比你的要快得多。 首先，由于该函数是通过检查string的长度是否大于26（我假定256是一个错字）开始的，函数不必testing任何长度为27或更长的string。 因此，内部循环最多运行26次。 每次迭代O（1）都在按位运算中工作，所以完成的总体工作是O（1）（O（1）迭代次O（1）每次迭代），这比你的实现要快得多。
如果您还没有看到按这种方式使用按位操作，我build议在Google上search“按位运算符”以了解更多信息。
希望这可以帮助！
书的解决scheme是我不喜欢，我相信是function障碍….. templatetypedef已经发布了一个全面的答案，表明该解决scheme是一个很好的。 我不同意，因为本书的答案假定string只有小写字符，（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 eg '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的答案是我同意，虽然…. 😉
编辑：作为一个练习，我把书的答案转换成了一个可以工作的答案（尽pipe比书的答案慢–BigInteger慢）….这个版本和本书的逻辑一样，但没有相同的validation和假设问题（但速度较慢）。 显示逻辑也是有用的。
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; }
由于char值只能保存256个不同的值之一，所以任何长度超过256个字符的string都必须至less包含一个重复值。
代码的其余部分使用checker作为一个位序列，每个位代表一个字符。 它似乎将每个字符转换为一个整数，从a = 1开始。然后检查检查器中的相应位。 如果已设置，则意味着已经看到字符，因此我们知道该string至less包含一个重复字符。 如果还没有看到字符，则代码在checker设置相应的位并继续。
具体来说， (1<<val)在位置val生成一个1位的整数。 例如， (1<<3)将是二进制1000或8.如果位置val的位未在checker设置（即值为0），则expression式checker & (1<<val)将返回零，和(1<<val) ，如果该位被设置，它总是非零的。 expression式checker |= (1<<val)将在checker设置该位。
然而，algorithm似乎是有缺陷的：似乎没有考虑到大写字母和标点符号（通常在小写字母之前按字典顺序）。 它似乎也需要一个256位整数，这是不标准的。
正如在下面的评论中提到的，我更喜欢你的解决scheme，因为它的工作原理。 只要识别出非唯一的字符，就可以通过返回false来优化它。
本书的解决scheme不区分大小写。 按照实施方式，“A”和“a”被认为是重复的。
说明：对于字符'A'，'A'的inputstring – 'a'是-32所以'1 << val'将被评估为1 << -32。 任何负数的移位都会使位反向移位。 因此1 << -32将是1 >> 32.这将把第一位设置为1. char'a'也是这种情况。 因此'A'和'a'被认为是重复的字符。 类似地，对于'B'和'b'，第二位被设置为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 { return false; } } return containsUnique; }
第六版更新
public static void main(String[] args) { System.out.println(isUniqueChars("abcdmc")); // false System.out.println(isUniqueChars("abcdm")); // true System.out.println(isUniqueChars("abcdm\u0061")); // false because \u0061 is unicode a } public static boolean isUniqueChars(String str) { /* You should first ask your interviewer if the string is an ASCII string or a Unicode string. Asking this question will show an eye for detail and a solid foundation in computer science. We'll assume for simplicity the character set is ASCII. If this assumption is not valid, we would need to increase the storage size. */ // at 6th edition of the book, there is no pre condition on string's length /* We can reduce our space usage by a factor of eight by using a bit vector. We will assume, in the below code, that the string only uses the lowercase letters a through z. This will allow us to use just a single int. */ // printing header to provide nice csv format log, you may uncomment // System.out.println("char,val,valBinaryString,leftShift,leftShiftBinaryString,checker"); int checker = 0; for (int i = 0; i < str.length(); i++) { /* Dec Binary Character 97 01100001 a 98 01100010 b 99 01100011 c 100 01100100 d 101 01100101 e 102 01100110 f 103 01100111 g 104 01101000 h 105 01101001 i 106 01101010 j 107 01101011 k 108 01101100 l 109 01101101 m 110 01101110 n 111 01101111 o 112 01110000 p 113 01110001 q 114 01110010 r 115 01110011 s 116 01110100 t 117 01110101 u 118 01110110 v 119 01110111 w 120 01111000 x 121 01111001 y 122 01111010 z */ // a = 97 as you can see in ASCII table above // set val to be the difference between the char at i and 'a' // b = 1, d = 3.. z = 25 char c = str.charAt(i); int val = c - 'a'; // means "shift 1 val numbers places to the left" // for example; if str.charAt(i) is "m", which is the 13th letter, 109 (g in ASCII) minus 97 equals 12 // it returns 1 and 12 zeros = 1000000000000 (which is also the number 4096) int leftShift = 1 << val; /* An integer is represented as a sequence of bits in memory. For interaction with humans, the computer has to display it as decimal digits, but all the calculations are carried out as binary. 123 in decimal is stored as 1111011 in memory. The & operator is a bitwise "And". The result is the bits that are turned on in both numbers. 1001 & 1100 = 1000, since only the first bit is turned on in both. It will be nicer to look like this 1001 & 1100 = 1000 Note that ones only appear in a place when both arguments have a one in that place. */ int bitWiseAND = checker & leftShift; String leftShiftBinaryString = Integer.toBinaryString(leftShift); String checkerBinaryString = leftPad(Integer.toBinaryString(checker), leftShiftBinaryString.length()); String leftShiftBinaryStringWithPad = leftPad(leftShiftBinaryString, checkerBinaryString.length()); // System.out.printf("%s &\n%s\n=\n%s\n\n", checkerBinaryString, leftShiftBinaryStringWithPad, Integer.toBinaryString(bitWiseAND)); /* in our example with string "abcdmc" 0 & 1 = 0 01 & 10 = 0 011 & 100 = 0 0111 & 1000 = 0 0000000001111 & 1000000000000 = 0 1000000001111 & 0000000000100 = 100 */ // System.out.println(c + "," + val + "," + Integer.toBinaryString(val) + "," + leftShift + "," + Integer.toBinaryString(leftShift) + "," + checker); /* char val valBinaryString leftShift leftShiftBinaryString checker a 0 0 1 1 0 b 1 1 2 10 1 c 2 10 4 100 3 d 3 11 8 1000 7 m 12 1100 4096 1000000000000 15 c 2 10 4 100 4111 */ if (bitWiseAND > 0) { return false; } // setting 1 on on the left shift /* 0000000001111 | 1000000000000 = 1000000001111 */ checker = checker | leftShift; } return true; /* If we can't use additional data structures, we can do the following: 1. Compare every character of the string to every other character of the string. This will take 0( n 2 ) time and 0(1) space 2. If we are allowed to modify the input string, we could sort the string in O(n log(n)) time and then linearly check the string for neighboring characters that are identical. Careful, though: many sorting algorithms take up extra space. These solutions are not as optimal in some respects, but might be better depending on the constraints of the problem. */ } private static String leftPad(String s, int i) { StringBuilder sb = new StringBuilder(s); int charsToGo = i - sb.length(); while (charsToGo > 0) { sb.insert(0, '0'); charsToGo--; } return sb.toString(); }
