實現(xiàn)一個算法來判斷一個字符串中的字符是否唯一(即沒有重復(fù)).不能使用額外的數(shù)據(jù)結(jié)構(gòu)。 (即只使用基本的數(shù)據(jù)結(jié)構(gòu))
解答
首先，你可以問面試官，構(gòu)成字符串的字符集有多大?是ASCII字符，還是只是26個字母? 還是有更大的字符集，對于不同的情況，我們可能會有不同的解決方案。
如果我們假設(shè)字符集是ASCII字符，那么我們可以開一個大小為256的bool數(shù)組來表征每個字 符的出現(xiàn)。數(shù)組初始化為false，遍歷一遍字符串中的字符，當bool數(shù)組對應(yīng)位置的值為真， 表明該字符在之前已經(jīng)出現(xiàn)過，即可得出該字符串中有重復(fù)字符。否則將該位置的bool數(shù)組 值置為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;
}
該算法的時間復(fù)雜度為O(n)。我們還可以通過位運算來減少空間的使用量。 用每一位表征相應(yīng)位置字符的出現(xiàn)。對于ASCII字符，我們需要256位，即一個長度為8的int 數(shù)組a即可。這里的關(guān)鍵是要把字符對應(yīng)的數(shù)字，映射到正確的位上去。比如字符’b’對應(yīng)的 代碼是98，那么我們應(yīng)該將數(shù)組中的哪一位置為1呢?用98除以32，得到對應(yīng)數(shù)組a的下標： 3。98對32取模得到相應(yīng)的位：2。相應(yīng)代碼如下：
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;
}
兩個算法的本質(zhì)其實是一樣的，只不過一個用bool單元來表征字符出現(xiàn)，一個用位來表征。 完整代碼如下：
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)，那就更好辦了，用位運算只需要一個整型數(shù)即可。
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實現(xiàn)】
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(chǎn)’;
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;
}
[谷歌面試題]