经典算法面试题目-判断一个字符串中的字符是否唯一（1.1）

题目：
Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?

实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据结构。 (即只使用基本的数据结构)

解答：
首先，你可以问面试官，构成字符串的字符集有多大？是ASCII字符，还是只是26个字母？ 还是有更大的字符集，对于不同的情况，我们可能会有不同的解决方案。

如果我们假设字符集是ASCII字符，那么我们可以开一个大小为256的bool数组来表征每个字 符的出现。数组初始化为false，遍历一遍字符串中的字符，当bool数组对应位置的值为真， 表明该字符在之前已经出现过，即可得出该字符串中有重复字符。否则将该位置的bool数组 值置为true。代码如下：

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

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

该算法的时间复杂度为O(n)。我们还可以通过位运算来减少空间的使用量。 用每一位表征相应位置字符的出现。对于ASCII字符，我们需要256位，即一个长度为8的int 数组a即可。这里的关键是要把字符对应的数字，映射到正确的位上去。比如字符’b’对应的 代码是98，那么我们应该将数组中的哪一位置为1呢？用98除以32，得到对应数组a的下标： 3。98对32取模得到相应的位：2。相应代码如下：

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;//<<左移不改变原来的数值。移位的结果是：第一个操作数乘以2的幂，指数的值是由第二个数给出的。 //右边空出用0填补.在不溢出的情况下,每左移一位相当于乘以2 a[idx] |= (1 << shift); //只要没有出现重复的，a[idx]是会从0开始一直加下去的，a[idx] & (1 << shift)一直会是0，从0加到2的31次方，接下来就是a[idx+1]的了。我是差不多这样理解的。 } return true;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

两个算法的本质其实是一样的，只不过一个用bool单元来表征字符出现，一个用位来表征。

完整代码如下：

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

 

  
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
 

如果字符集只是a－z(或是A－Z)，那就更好办了，用位运算只需要一个整型数即可。

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

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

文章来源: chenhx.blog.csdn.net，作者：谙忆，版权归原作者所有，如需转载，请联系作者。

原文链接：chenhx.blog.csdn.net/article/details/51954734