谷歌面试题
实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据结构。 (即只使用基本的数据结构)
解答
首先，你可以问面试官，构成字符串的字符集有多大?是ASCII字符，还是只是26个字母? 还是有更大的字符集，对于不同的情况，我们可能会有不同的解决方案。
如果我们假设字符集是ASCII字符，那么我们可以开一个大小为256的bool数组来表征每个字 符的出现。数组初始化为false，遍历一遍字符串中的字符，当bool数组对应位置的值为真， 表明该字符在之前已经出现过，即可得出该字符串中有重复字符。否则将该位置的bool数组 值置为true。代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 | bool isUnique1(string s) { bool a[256]; memset(a, 0, sizeof(a)); int len = s.length(); for(int i=0; i < len; ++i) { int v = (int)s[i]; if(a[v]) return false; a[v] = true; } return true; } |
该算法的时间复杂度为O(n)。我们还可以通过位运算来减少空间的使用量。 用每一位表征相应位置字符的出现。对于ASCII字符，我们需要256位，即一个长度为8的int 数组a即可。这里的关键是要把字符对应的.数字，映射到正确的位上去。比如字符’b’对应的 代码是98，那么我们应该将数组中的哪一位置为1呢?用98除以32，得到对应数组a的下标： 3。98对32取模得到相应的位：2。相应代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | bool isUnique2(string s) { int a[8]; memset(a, 0, sizeof(a)); int len = s.length(); for(int i=0; i < len; ++i) { int v = (int)s[i]; int idx = v/32, shift=v%32; if(a[idx] & (1 << shift)) return false; a[idx] |= (1 << shift); } return true; } |
两个算法的本质其实是一样的，只不过一个用bool单元来表征字符出现，一个用位来表征。 完整代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | #include <iostream> #include <cstring> using namespace std; bool isUnique1(string s) { bool a[256]; memset(a, 0, sizeof(a)); int len = s.length(); for(int i=0; i < len; ++i) { int v = (int)s[i]; if(a[v]) return false; a[v] = true; } return true; } bool isUnique2(string s) { int a[8]; memset(a, 0, sizeof(a)); int len = s.length(); for(int i=0; i < len; ++i) { int v = (int)s[i]; int idx = v/32, shift=v%32; if(a[idx] & (1 << shift)) return false; a[idx] |= (1 << shift); } return true; } int main() { string s1 = "i am hawstein."; string s2 = "abcdefghijklmnopqrstuvwxyzABCD1234567890"; cout << isUnique1(s1) << " " << isUnique1(s2) << endl; cout << isUnique2(s1) << " " << isUnique2(s2) << endl; return 0; } |
如果字符集只是a-z(或是A-Z)，那就更好办了，用位运算只需要一个整型数即可。
1 2 3 4 5 6 7 8 9 10 11 12 | bool isUnique3(string s) { int check = 0; int len = s.length(); for(int i=0; i < len; ++i) { int v = (int)(s[i]-'a'); if(check & (1 << v)) return false; check |= (1 << v); } return true; } |
【JAVA实现】
1 2 3 4 5 6 7 8 9 | public static boolean isUniqueChars(String str) { 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; } |
1 2 3 4 5 6 7 8 9 | public static boolean isUniqueChars2(String str) { boolean[] char_set = new boolean[256]; for (int i = 0; i < str.length(); i++) { int val = str.charAt(i); if (char_set[val]) return false; char_set[val] = true; } return true; } |
【谷歌面试题】相关文章：
网页制作面试题10-28
最新财务面试题目09-01
评论：[面试]曝外企趣味面试题07-01
8个经典面试题回答思路技巧10-02