1.1

http://www.hawstein.com/posts/1.1.html

• 实现一个算法，确定一个字符串的所有字符是否全都不同。假设可以使用额外的数据结构

* 算法1

• 是否是ASCII字符
• 判断是否大于256，若大于256，则错误
• 设置256的bool数组，数组初始化为false
• 遍历字符串当bool数组对应位置的值为真，表明该字符在之前已经出现过，
• 即可得出该字符串中有重复字符。否则将该位置的bool数组 值置为true。

* 时间复杂度为O(n)。

* 算法2

• 优化：位运算优化

• 8 位代替256

• 位运算：

http://blog.csdn.net/xiaoxiaoyu85/article/details/6334707

* 代码

#include <iostream>
#include<string>
#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 stud";
string s2="abcdefghjklop";
cout<<isUnique1(s1)<< " "<<endl;
}