【剑指offer】第一个仅仅出现一次的字符

大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。

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

题目描写叙述：: 在一个字符串(1<=字符串长度<=10000，所有由大写字母组成)中找到第一个仅仅出现一次的字符。

输入：: 输入有多组数据
每一组输入一个字符串。

输出：: 输出第一个仅仅出现一次的字符下标，没有仅仅出现一次的字符则输出-1。

例子输入：

ABACCDEFF
AA

例子输出：

1
-1

处理字符串中反复或者次数出现等问题，最经常使用的就是哈希表，用字符串中的字符作为key，字符出现次数作为value，假定仅仅有ASCII码范围内的字符，则能够开辟一个256大小的int数组，将每一个字符（key）映射到该数组的相应位置上，计算每次出现的次数就可以，遍历一次字符串，计算每一个字符出现的次数，保存在int数组的相应位置上，第二次遍历字符串，若第一次出现某个字符对相应到的哈希表的相应位置处的元素为1，则该字符便是第一个仅仅出现一次的字符，假设我们是遍历哈希表（int数组），则找到的哈希表中的第一个元素为1的位置相应的字符为字符串中第一个最小的仅仅出现一次的字符。时间复杂度为O（n），须要额外的256个int空间来辅助，能够看做空间复杂度为O（1）。

另外，假设要省空间，我们能够bitmap算法，用两个位来表示相应字符出现的次数，出现0次，则为00，出现一次则为01，出现2次及以上，都维持在10就可以。

另外，有一点须要注意，char的范围在-128-127，unsigned char的范围才是在0-255，因此ASCII值在128-255之间的字符，假设保存为了char型，其转化为int值的范围是在-128–1之间，这点在以下的代码中有体现。

以下给出用简单哈希表AC的代码（依据题目要求和測试要求分别写了两个函数）：

#include<stdio.h>
#include<string.h>

/*
返回第一个出现一次的字符
*/
char FirstOnceChar(char *str)
{
	if(str == NULL)
		return '#include<stdio.h>
#include<string.h>
/*
返回第一个出现一次的字符
*/
char FirstOnceChar(char *str)
{
if(str == NULL)
return '\0';
int hashtable[256];
memset(hashtable,0,sizeof(hashtable));
char *pCur = str;
while(*pCur != '\0')
{
if(*pCur>=0)
hashtable[*(pCur++)]++;
else
hashtable[*(pCur++)+256]++;
}
while(*str != '\0')
{
int index;
if(*str>=0)
index = *str;
else
index = *str+256;
if(hashtable[index] == 1)
return *str;
else
str++;
}
return '\0';
}
/*
返回第一个出现一次的字符的下标
*/
int IndexOfFirstOnceChar(char *str)
{
if(str == NULL)
return -1;
int len = strlen(str);
int hashtable[256];
memset(hashtable,0,sizeof(hashtable));
int i;
for(i=0;i<len;i++)
{
if(str[i]>=0)
hashtable[str[i]]++;
else
hashtable[str[i]+256]++;
}
for(i=0;i<len;i++)
{
int index;
if(str[i]>=0)
index = str[i];
else
index = str[i]+256;
if(hashtable[index] == 1)
return i;
}
return -1;
}
int main()
{
char str[10010];
while(gets(str) != NULL)
printf("%d\n",IndexOfFirstOnceChar(str));
return 0;
}';

	int hashtable[256];
	memset(hashtable,0,sizeof(hashtable));
	char *pCur = str;
	while(*pCur != '#include<stdio.h>
#include<string.h>
/*
返回第一个出现一次的字符
*/
char FirstOnceChar(char *str)
{
if(str == NULL)
return '\0';
int hashtable[256];
memset(hashtable,0,sizeof(hashtable));
char *pCur = str;
while(*pCur != '\0')
{
if(*pCur>=0)
hashtable[*(pCur++)]++;
else
hashtable[*(pCur++)+256]++;
}
while(*str != '\0')
{
int index;
if(*str>=0)
index = *str;
else
index = *str+256;
if(hashtable[index] == 1)
return *str;
else
str++;
}
return '\0';
}
/*
返回第一个出现一次的字符的下标
*/
int IndexOfFirstOnceChar(char *str)
{
if(str == NULL)
return -1;
int len = strlen(str);
int hashtable[256];
memset(hashtable,0,sizeof(hashtable));
int i;
for(i=0;i<len;i++)
{
if(str[i]>=0)
hashtable[str[i]]++;
else
hashtable[str[i]+256]++;
}
for(i=0;i<len;i++)
{
int index;
if(str[i]>=0)
index = str[i];
else
index = str[i]+256;
if(hashtable[index] == 1)
return i;
}
return -1;
}
int main()
{
char str[10010];
while(gets(str) != NULL)
printf("%d\n",IndexOfFirstOnceChar(str));
return 0;
}')
	{
		if(*pCur>=0)
			hashtable[*(pCur++)]++;
		else
			hashtable[*(pCur++)+256]++;
	}

	while(*str != '#include<stdio.h>
#include<string.h>
/*
返回第一个出现一次的字符
*/
char FirstOnceChar(char *str)
{
if(str == NULL)
return '\0';
int hashtable[256];
memset(hashtable,0,sizeof(hashtable));
char *pCur = str;
while(*pCur != '\0')
{
if(*pCur>=0)
hashtable[*(pCur++)]++;
else
hashtable[*(pCur++)+256]++;
}
while(*str != '\0')
{
int index;
if(*str>=0)
index = *str;
else
index = *str+256;
if(hashtable[index] == 1)
return *str;
else
str++;
}
return '\0';
}
/*
返回第一个出现一次的字符的下标
*/
int IndexOfFirstOnceChar(char *str)
{
if(str == NULL)
return -1;
int len = strlen(str);
int hashtable[256];
memset(hashtable,0,sizeof(hashtable));
int i;
for(i=0;i<len;i++)
{
if(str[i]>=0)
hashtable[str[i]]++;
else
hashtable[str[i]+256]++;
}
for(i=0;i<len;i++)
{
int index;
if(str[i]>=0)
index = str[i];
else
index = str[i]+256;
if(hashtable[index] == 1)
return i;
}
return -1;
}
int main()
{
char str[10010];
while(gets(str) != NULL)
printf("%d\n",IndexOfFirstOnceChar(str));
return 0;
}')
	{
		int index;
		if(*str>=0)
			index = *str;
		else
			index = *str+256;

		if(hashtable[index] == 1)
			return *str;
		else
			str++;
	}
	return '#include<stdio.h>
#include<string.h>
/*
返回第一个出现一次的字符
*/
char FirstOnceChar(char *str)
{
if(str == NULL)
return '\0';
int hashtable[256];
memset(hashtable,0,sizeof(hashtable));
char *pCur = str;
while(*pCur != '\0')
{
if(*pCur>=0)
hashtable[*(pCur++)]++;
else
hashtable[*(pCur++)+256]++;
}
while(*str != '\0')
{
int index;
if(*str>=0)
index = *str;
else
index = *str+256;
if(hashtable[index] == 1)
return *str;
else
str++;
}
return '\0';
}
/*
返回第一个出现一次的字符的下标
*/
int IndexOfFirstOnceChar(char *str)
{
if(str == NULL)
return -1;
int len = strlen(str);
int hashtable[256];
memset(hashtable,0,sizeof(hashtable));
int i;
for(i=0;i<len;i++)
{
if(str[i]>=0)
hashtable[str[i]]++;
else
hashtable[str[i]+256]++;
}
for(i=0;i<len;i++)
{
int index;
if(str[i]>=0)
index = str[i];
else
index = str[i]+256;
if(hashtable[index] == 1)
return i;
}
return -1;
}
int main()
{
char str[10010];
while(gets(str) != NULL)
printf("%d\n",IndexOfFirstOnceChar(str));
return 0;
}';
}

/*
返回第一个出现一次的字符的下标
*/
int IndexOfFirstOnceChar(char *str)
{
	if(str == NULL)
		return -1;

	int len = strlen(str);
	int hashtable[256];
	memset(hashtable,0,sizeof(hashtable));
	int i;
	for(i=0;i<len;i++)
	{
		if(str[i]>=0)
			hashtable[str[i]]++;
		else
			hashtable[str[i]+256]++;
	}

	for(i=0;i<len;i++)
	{
		int index;
		if(str[i]>=0)
			index = str[i];
		else
			index = str[i]+256;

		if(hashtable[index] == 1)
			return i;
	}
	return -1;
}

int main()
{
	char str[10010];
	while(gets(str) != NULL)
		printf("%d\n",IndexOfFirstOnceChar(str));
	return 0;
}

/**************************************************************

    

Problem: 1283

    

User: mmc_maodun

    

Language: C

    

Result: Accepted

    

Time:10 ms

    

Memory:912 kb

****************************************************************/

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/118492.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权正版激活】： 官方授权正版激活支持Jetbrains家族下所有IDE 使用个人JB账号...

【剑指offer】第一个仅仅出现一次的字符

相关推荐

二维码转换成短链接_二维码解析url

“did not call through to super.onResume”问题解决「建议收藏」

idea 2022.01.13最新激活码(JetBrains全家桶)「建议收藏」

PHP UEditor富文本编辑器 显示 后端配置项没有正常加载，上传插件不能正常使用…

CentOS 7如何配置yum源「建议收藏」

Idea下Spring Boot、thymeleaf、Jpa项目整合实例「建议收藏」

发表回复

PHP UEditor富文本编辑器显示后端配置项没有正常加载，上传插件不能正常使用…