【题目】
Chapter 1 | Arrays and Strings
原文：
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。该算法的时间复杂度为O(n)。
【思路二】
我们还可以通过位运算来减少空间的使用量。其实就是用所谓的Bit-map的原理来存储。就是用一个bit位来标记某个元素对应的Value,在这就是该元素是否出现的bool值,而Key即是该元素。用每一位表征相应位置字符是否出现。对于ASCII字符，我们需要256位，即一个长度为8的int数组map即可(8*4*8)。
这里的关键是要把字符对应的ASCII，映射到正确的位上去。
举个例子：
字符'a'对应的ASCII是97，那么我们应该将数组中的哪一位置为1呢？
用97除以32，得到对应数组map的下标:3。97对32取模得到相应的位：1。
【代码】
/*********************************
* 日期：2014-05-04
* 作者：SJF0115
* 题目: 字符串中字符判重
* 来源：CareerCup
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
bool IsUnique(string str){
bool visited[256];
//初始化
memset(visited,false,sizeof(visited));
int len = str.length();
for(int i = 0;i < len;i++){
int index = (int)str[i];
//判断是否有重复
if(!visited[index]){
visited[index] = true;
}
else{
//有重复直接返回
return true;
}
}
return false;
}
int main(){
string str = "i am xiaosi";
bool result = IsUnique(str);
cout<<result<<endl;
return 0;
}
【代码2】
/*********************************
* 日期：2014-05-04
* 作者：SJF0115
* 题目: 字符串中字符判重
* 来源：CareerCup
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
//判断字符串中字符是否重复
bool IsUnique(string str){
//8*4*8 共256位可以表示256个元素
int map[8];
//初始化
memset(map,0,sizeof(map));
int len = str.length();
for(int i = 0;i < len;i++){
int value = (int)str[i];
int index = value / 32, offset = value % 32;
//判断是否已经存储过
if(map[index] & (1 << offset)) {
//重复
return false;
}
map[index] |= (1 << offset);
}
return true;
}
int main(){
string str = "i amxos ";
bool result = IsUnique(str);
cout<<result<<endl;
return 0;
}
