从今天开始要刷这个网站了，时间再紧，也要坚持下去！
题目：
Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures
翻译：
实现一个算法来判断一个字符串中是否没有重复的字符，只能使用基本的数据结构。
思路：
我们这里假设字符串为26个小写字母（当然我们可以扩充到整个ASCII码表，下面会说）。思路很多啦！可以使用桶排序的思想，分成26个桶，如果有桶中元素个数大于1，则出现重复，但实际上我们没必要对字符串进行排序，直接判断即可，因此我们可以使用哈希表，将26个小写字母映射到一个哈希表中，但因为只能使用基本的数据结构，因此我们可以使用哈希的思想，将26个小写字母映射到一个数组中（其实也还是哈希表啦，只是使最简单的直接寻址表）。
我们开辟一个大小为26的int数组，记录26个小写字母在字符串中出现的次数，初始为0，出现一次对应位置变为1，再出现一次的话，就说明有重复了，直接返回false即可。
这样子只需遍历一次字符串，的时间复杂度为O（n），需要额外的26个int辅助空间。
实现代码：
/*
判断是否有重复字符
*/
bool unqString(string s)
{
unsigned int i;
unsigned int len = s.length();
unsigned int arr[MAX];
for(i=0;i
由于实际上arr数字中的每个元素只可能为0或1（一旦为1时，判断再次出现，就直接返回false），因此我们可以用bool数组来代替unsigned int数组，这样可以节省内存（32位的系统中，unsigned int占4个字节，而bool占一个字节）。
完整代码如下：
/**********************************************************
题目描述：
判断一个字符串中是否没有重复的字符，只能使用基本的数据结构
Date：2014-03-15
**********************************************************/
#define MAX 26
#include
#include
using namespace std; /* 判断是否有重复字符 */ bool unqString(string s) { unsigned int i; unsigned int len = s.length(); unsigned int arr[MAX]; for(i=0;i
vcgbdfrvst;" string="" unsigned="">yes<
no<
yes<
no<
测试结果如下：
s1->yes s2->no
如果我们将字符串中字符的范围扩大到整个ASCII编码表，需要注意：ASCII编码表的0-127是标准编码，而128-255为扩展编码（一般情况下是用不到的，编译器的实现对该部分的编码也没有任何统一的标准），如果保存为char类型，就变为负值了，即变成了-128—-1。因此，在写程序的时候，对0-127这部分字符可以直接转化为对应的整数来作为其在arr数组中的位置，而对与128-255这部分字符，则要将其转化为整数后再加256，将得到的数作为其在arr数组中的位置。
另外，还有人通过位运算来解决该问题，挺新颖的思路，不过空间代价与用bool数组时一样的，而且思想也大同小异。这里不再给出。