题目:判断字符串中是否出现了一样的字符,如abcda,a出现了2次,则应该输出true
方法1:对于字符串中的每一个字符,遍历除了自身之外的其他字符,如果得到相同的字符,则输出为true,时间复杂度为O(n*n);这里就不给出代码了
方法2:给定的字符串中字符为ASCII中字符,定义一个布尔型的256位的数组,遍历字符串,将以字符的ASCII码值作为数组的位置索引,如果有某个字符,则其对应的位置设为true,因此,当出现相同的字符时,判断如果这个位置已经为true了,即字符串中有相同的字符。
bool isUnique(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; }
方法3,:处理256种可能出现的字符,可以通过一个int型的数组来做,其长度为8,因为在32位或者64位的机器中,int都为4个字节,即32位,因此8个int类型的数即可表示256位,将每一个字符的ASCII码值除以32即可得出其属于哪一个位置的整数,然后对32求模得出这个数属于这个整数的“哪一位”,这样就能完整的表示字符串中的每一个字符,通过或运算将整数中指定的位置设为1,然后如果来了相同的元素,通过除以32得出其属于哪一个整数位,然后通过对32求模,通过对求模的值求与,因为如果曾经出现过相同的字符则此时与运算会得1,所以以此来判断是否有重复字符
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; }
方法4:以上讲述的都是对256中字符进行处理,如果处理的字符只有26种,则一个int类型的整数即可完成判断工作,则处理过程如上