【CareerCup】 Arrays and Strings—Q1.1

转载请注明出处：http://blog.csdn.net/ns_code/article/details/21276577

    从今天开始要刷这个网站了，时间再紧，也要坚持下去！

    题目：

    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<MAX;i++)
		arr[i] = 0;
	//依次对字符对应的数组位置上的值进行判断
	//0表示还没有出现该字符,1表示出现了该字符
	//如果已经为1了，再次出现该字符，则说明出现了重复
	for(i=0;i<len;i++)
	{
		unsigned int index = s[i] - ‘a‘;
		if(arr[index] == 0)
			arr[index] = 1;
		else
			return false;
	}
	return true;
}

    由于实际上arr数字中的每个元素只可能为0或1（一旦为1时，判断再次出现，就直接返回false），因此我们可以用bool数组来代替unsigned int数组，这样可以节省内存（32位的系统中，unsigned int占4个字节，而bool占一个字节）。

    完整代码如下：

/**********************************************************
题目描述：
判断一个字符串中是否没有重复的字符，只能使用基本的数据结构
Date：2014-03-15
**********************************************************/
#define MAX 26
#include<iostream>
#include<cstring>
using namespace std;

/*
判断是否有重复字符
*/
bool unqString(string s)
{
	unsigned int i;
	unsigned int len = s.length();
	unsigned int arr[MAX];
	for(i=0;i<MAX;i++)
		arr[i] = 0;
	//依次对字符对应的数组位置上的值进行判断
	//0表示还没有出现该字符,1表示出现了该字符
	//如果已经为1了，再次出现该字符，则说明出现了重复
	for(i=0;i<len;i++)
	{
		unsigned int index = s[i] - ‘a‘;
		if(arr[index] == 0)
			arr[index] = 1;
		else
			return false;
	}
	return true;
}

int main()
{
	string s1 = "abcdef";
	string s2 = "advcgbdfrvst";
	if(unqString(s1))
		cout<<"s1->yes"<<endl;	
	else
		cout<<"s1->no"<<endl;
	if(unqString(s2))
		cout<<"s2->yes"<<endl;	
	else
		cout<<"s2->no"<<endl;
	return 0;
}

   测试结果如下：

s1->yes
s2->no 

    如果我们将字符串中字符的范围扩大到整个ASCII编码表，需要注意：ASCII编码表的0-127是标准编码，而128-255为扩展编码（一般情况下是用不到的，编译器的实现对该部分的编码也没有任何统一的标准），如果保存为char类型，就变为负值了，即变成了-128—-1。因此，在写程序的时候，对0-127这部分字符可以直接转化为对应的整数来作为其在arr数组中的位置，而对与128-255这部分字符，则要将其转化为整数后再加256，将得到的数作为其在arr数组中的位置。

    另外，还有人通过位运算来解决该问题，挺新颖的思路，不过空间代价与用bool数组时一样的，而且思想也大同小异。这里不再给出。

【CareerCup】 Arrays and Strings—Q1.1,布布扣,bubuko.com

【CareerCup】 Arrays and Strings—Q1.1

原文：http://blog.csdn.net/ns_code/article/details/21276577