[google面试CTCI] 1-1.判断一个字符串是否包含重复字符

【字符串与数组】
 
Q：Implement an algorithm to determine if a string has all unique characters What if you
can not use additional data structures?
 
题目：实现一个算法来判断一个字符串是否包含重复字符。如果不能使用额外数据结构，怎么做？
 
解答：
 
方法一：从头到尾取字符串中的每一个字符，并将该字符与其后的字符依次比较，一旦发现重复的字符，就返回，表示该字符串含有重复字符串。
 
int is_unique(char * str){
int len=strlen(str);
int  i,j;
for(i=0;i<len-1;++i){
 for(j=i+1;j<len;++j){
if(str[i]==str[j])
 return 0;
}
}
return 1;
}
方法二：如果假设字符串中的字符都是ascii字符（ascii码字符对应的数值范围为0-255），那么我们可以分配一个256字节大小的数组，并将该数组元素初始化为0。然后，遍历字符串中的字符，将字符对应的ascii码值作为数组下标，如若该数组元素为0，将其置为1；如若该数组元素为1，则说明该字符出现过，说明字符串含有重复字符。
 
int is_unique(char* str){
int flags[256];
int  i;
memset(flags,0,256);
for(i=0;i<strlen(str);i++){
   if(flags[str[i]]==1)
return 0;
   flags[str[i]]=1;
}
return 1;
}
方法三.由于方法二中用字符数组来表示一个字符(byte)是否出现过，事实上，只需要用一个位(bit)即可表示某个字符是否出现过，可以节约存储空间,因此，我们可以用位操作来改写方法二。
 
int is_unique_str2(char* str){
int flags[8];//只需要8个32位的int，8*32=256位
memset(flags,0,sizeof(flags));
int i;
int len=strlen(str);
for(i=0;i<len;i++){
int index=(int)str[i]/32;
int shift=(int)str[i]%32;
if(flags[index] & (1<<shift))
   return 0;
flags[index]|=(1<<shift);
}
return 1;

补充：综合编程 , 其他综合 ,