数组以及字符串经典题

1.数组中只有一个数字只出现一次，其他都成对出现

如：int a[] = {2,3,5,6,4,3,2,5,6};   打印出4。

   首先呢，先分析此题。

   可将数组的第一个元素与后边其他元素进行异或，（异或的性质：任何一个数字异或自己都为0）若为0，则将这个元素删除。

   如：数组第一个元素为2，当碰到后边那个2时，将后边元素删除。a[] = {2,3,5,6,4,3,5,6}。

   然后比较数组第二个，以此类推。

   当我们在数组前面找到这个这个只出现一次的元素，即可return。因为题目给出的是只有一个数字只出现一次呢。

int FindOneNum(int* a,int size) {	int i = 0;     for(int j=i+1;j<size-i;j++)	{	if(i<size)	{	if(((a[i])^(a[j])) == 0)	{	for(int k=j;k<size-i;k++)	{	a[k] = a[k+1];	}	i++;	j = i;	continue;	}	if(((a[i])^(a[j])) != 0 && j == size-i-1)	{	return a[i];	}	}	}	return a[i]; }

//测试函数

void Test() {	int a[] = {4,2,3,5,6,3,2,5,6};	//int a[] = {2,3,5,6,4,3,2,5,6};	//int a[] = {2,3,5,6,3,2,5,6,4};	int size = sizeof(a)/sizeof(a[0]);	int ret = FindOneNum(a,size);	cout<<ret<<endl;	return 0; }

//测试结果

2.数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

分析：

    数组若为无序，则先将数组排序。

    数组中有一个元素的次数超过数组长度的一半，也就是说它的出现次数比其他数字之和还要多。

因此我们在遍历数组时，应该保存两个值：一个是数字，一个是次数。当我们遍历到下一个数字时，若与我们之前保存的数字相同，则次数加1，不同次数减1。若次数为0，则需要保存下一个数字，并将次数置为1。那么我们要找的可能就是最后一次将次数置为1的数字。

bool CheckArray(int* a,int size)//检查数组是否合法 {	if(a == NULL || size <= 0)	return false;	return true; } void Sort(int* a,int size)//数组排序 {	if(CheckArray(a,size))	{	int i = 0;	int j = 0;	for(i=0;i<size-1;i++)	{	for(j=0;j<size-i-1;j++)	{	if(a[j] > a[j+1])	{	int tmp = a[j];	a[j] = a[j+1];	a[j+1] = tmp;	}	}	}	}	return; } bool MornThanHalf(int* a,int size,int num)//是否超过一半 {	int count = 0;	for(int i=0;i<size;i++)	{	if(a[i] == num)	{	count++;	}	}	if(count*2 >= size)	{	return true;	}	return false; } int MoreThan(int* a,int size)//次数较多的数 {	if(!CheckArray(a,size))	return 0;	int num = a[0];	int count = 1;	for(int i=1;i<size;i++)	{	    if(num == a[i])//数字相同	    {	count++;	    }	    else	    {	count--;             }	    if(count == 0)	    {	num = a[i];	count = 1;	     }	}	if(MornThanHalf(a,size,num))	{	return num;	}	return 0; }

//测试函数

void Test() {	int a[] = {3,2,3,3,2,3,4,3,4,2,3,3};	int size = sizeof(a)/sizeof(a[0]);	Sort(a,size);	int ret = MoreThan(a,size);	cout<<ret<<endl; }

//测试结果

3.实现一个函数，可以右旋字符串中的k个字符。（可以左旋字符串中的k个字符）

   ABCDE右旋一个字符得到BCDEA

   ABCDE右旋两个字符得到CDEAB

   ABCDE左旋一个字符得到EABCD

   ABCDE左旋两个字符得到DEABC

void move(char* left,char* right) {	while(left < right)	{	char tmp = *left;	*left = *right;	*right = tmp;	left++;	right--;	} } int main() {	char p[] = {"ABCDE"};	int size = strlen(p);	int n = 0;	cin>>n;              //n=3	//右旋n为	//move(p,p+n-1);       //CBADE	//move(p+n,p+size-1);  //CBAED	//move(p,p+size-1);    //DEABC	//cout<<p<<endl;	//左旋n位	move(p+n,p+size-1);   //ABEDC	move(p,p+n-1);        //BAEDC	move(p,p+size-1);     //CDEAB	cout<<p<<endl; }

第3题扩展：判断一个字符串是否为另外一个字符串旋转之后的字符串。

bool CheckEquel(char* p,char* q,int size) {	char* tmp = new char[size+1];	for(int n=0;n<size;n++) //最多可旋转size个字符	{	strcpy(tmp,p);    //每次进出都必须将p的内容复制给tmp	move(tmp,tmp+n-1); //调用move函数，旋转n个字符	move(tmp+n,tmp+size-1);	move(tmp,tmp+size-1);	if(strcmp(tmp,q) == 0) //旋转后的字符串与q相等	{	return true;	}	}	return false; } int main() {	char p[] = {"ABCDE"};	char q[] = {"CDEAB"};	int size = strlen(p);	bool ret = CheckEquel(p,q,size);	if(ret == true)	{	cout<<"字符串是由旋转得来的"<<endl;	}	else	{	cout<<"字符串不是由旋转得来的"<<endl;	}	return 0; }

测试结果：