Problem:
Implement an algorithm to determine if a string has all unique characters. What if youcan not use additional data structures?
<pre name="code" class="cpp">#include<iostream>#include<set>#include<string>#include<algorithm>#include<memory.h>#include<fstream>#include<ctime>#include<bitset>using namespace std;// Solution1: 使用setbool isUnique1(string str){set<char> s;int sizeOfStr = str.size();for(int i=0; i<sizeOfStr; ++i)s.insert(str[i]);return s.size()==sizeOfStr;}// Solution2: 从第二个字符开始判断，该字符与在它之前的每一个字符进行比较，如果相等，则返回falsebool isUnique2(string str){if(str.empty() || str.size()==1) return true;for(int i=1; i<str.size(); ++i){for(int j=0; j<i; ++j)if(str[i] == str[j]) return false;}return true;}// Solution3: 先排序，再对相邻字符进行比较bool isUnique3(string str){if(str.empty() || str.size()==1) return true;sort(str.begin(), str.end());for(int i=0; i<str.size()-1; ++i)if(str[i] == str[i+1]) return false;return true;}// Solution4: 用128=2^7大小的字符数组存放字符，如果当前遍历的字符已经存放过，则表明// 有重复的字符bool isUnique4(string str){if(str.empty() || str.size()==1) return true;char arr[128];memset(arr, 0, 128);for(int i=0; i<str.size(); ++i){int num = (int)str[i];if(arr[num] != 0) return false;arr[num]++;}return true;}// Solution5: 使用bitset可比Solution4进一步减少额外使用空间，，bitset只需考虑字符串中字符的ASCII码范围bool isUnique5(string str){if(str.empty() || str.size()==1) return true;bitset<128> bs;for(int i=0; i<str.size(); ++i){int num = (int)str[i];if(bs[num]) return false;bs[num] = 1;}return true;}int main(){clock_t start = clock();ifstream ifile("strings.txt");string str;while(getline(ifile, str)){if(isUnique5(str)) printf("%s is unique.\n", str.c_str());else printf("%s is not unique.\n", str.c_str());}clock_t finish = clock();double time = (double)(finish-start)/CLOCKS_PER_SEC*1000;printf("This program runs %fms.\n", time);return 0;}
爱情从希望开始，也由绝望结束。死心了，
