现在的位置: 首页 > 综合 > 正文

cc150:判断一个字符串中的字符是否唯一

2019年11月03日 ⁄ 综合 ⁄ 共 1092字 ⁄ 字号 评论关闭

      


       实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据结构。 (即只使用基本的数据结构)

      是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; 
}
 

     

抱歉!评论已关闭.