谷歌面試題
實(shí)現一個(gè)算法來(lái)判斷一個(gè)字符串中的字符是否唯一(即沒(méi)有重復).不能使用額外的數據結構。 (即只使用基本的數據結構)
解答
首先，你可以問(wèn)面試官，構成字符串的字符集有多大?是ASCII字符，還是只是26個(gè)字母? 還是有更大的字符集，對于不同的情況，我們可能會(huì )有不同的解決方案。
如果我們假設字符集是ASCII字符，那么我們可以開(kāi)一個(gè)大小為256的bool數組來(lái)表征每個(gè)字 符的出現。數組初始化為false，遍歷一遍字符串中的字符，當bool數組對應位置的值為真， 表明該字符在之前已經(jīng)出現過(guò)，即可得出該字符串中有重復字符。否則將該位置的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; } |
該算法的時(shí)間復雜度為O(n)。我們還可以通過(guò)位運算來(lái)減少空間的使用量。 用每一位表征相應位置字符的出現。對于A(yíng)SCII字符，我們需要256位，即一個(gè)長(cháng)度為8的int 數組a即可。這里的關(guān)鍵是要把字符對應的數字，映射到正確的位上去。比如字符’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; } |
兩個(gè)算法的本質(zhì)其實(shí)是一樣的，只不過(guò)一個(gè)用bool單元來(lái)表征字符出現，一個(gè)用位來(lái)表征。 完整代碼如下：
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)，那就更好辦了，用位運算只需要一個(gè)整型數即可。
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實(shí)現】
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; } |
【谷歌面試題】相關(guān)文章：
谷歌中國面試題07-13
谷歌的面試題和招聘流程介紹07-13
谷歌有趣腦經(jīng)急轉彎面試題,你會(huì )嗎？07-13
谷歌面試問(wèn)題...07-13
谷歌公司待遇是怎樣的？07-11
谷歌的「親兒子」指什么？07-11
谷歌面試常見(jiàn)問(wèn)題07-02
大家如何看待谷歌這款產(chǎn)品的？07-11
谷歌的穿越搜索帶來(lái)了什么？07-11