实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据结构。 (即只使用基本的数据结构)
是ASCII字符,还是只是26个字母?
还是有更大的字符集,对于不同的情况,可能会有不同的解决方案。
#include <iostream> #include <cstring> using namespace std; //如果字符时ASCII字符,则一共256个 //数组保存 bool isUnique1(string str) { bool array[256]; memset(array,0,sizeof(array)); int len = str.length(); for(int flag=0;flag<len;flag++) { int vec = (int)str[flag]; if(array[vec]) return false; array[vec] = true; } return true; } //保存至8个int型数中,位保存 bool isUnique2(string str){ int array[8]; memset(array,0,sizeof(array)); int len = str.length(); for(int flag=0;flag<len;flag++){ int vec = (int)str[flag]; int index = vec/32; int shift = vec%32; if(array[index] & (1<<shift)) return false; array[index] |= (1<<shift); } return true; } //如果是26个字母a-z或A-Z,则位运算只需要一个整数 bool isUnique3(string str){ int check = 0; int len = str.length(); for(int flag=0;flag<len;flag++){ int vec = (int)(str[flag]-'a'); if(check & (1 << vec)) return false; check |= (1 << vec); } return true; } int main(){ string str1 = "wearulpogm"; string str2 = "qwertyuiopasdfghjkzxcvbnlkjhgft37tr874AFVF"; cout << isUnique1(str1) << " " << isUnique1(str2) << endl; cout << isUnique2(str1) << " " << isUnique2(str2) << endl; cout << isUnique3(str1) << endl; return 0; }