#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char firstNotRepeatingChar(char* pString)
{
if(pString==NULL)
return '\0';
const int tablesize = 256;
unsigned int hashtable[tablesize];
for(unsigned int i=0;i<tablesize;i++)
{
hashtable[i]=0;
}
char* pHashKey = pString;
while(*(pHashKey)!='\0')
hashtable[*(pHashKey++)]++;
pHashKey = pString;
while(*pHashKey!='\0')
{
if(hashtable[*pHashKey]==1)
return *pHashKey;
pHashKey++;
}
return '\0';
}
int main()
{
char pString[10010];
while(gets(pString)!=NULL)
printf("%c",firstNotRepeatingChar(pString));
return 0;
}
题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff
,则输出b
。
看到这道题时,最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较,如果在后面没有发现重复的字符,则该字符就是只出现一次的字符。如果字符串有n个字符,每个字符可能与后面的O(n)个字符相比较,因此这种思路时间复杂度是O(n2)。我们试着去找一个更快的方法。
由于题目与字符出现的次数相关,我们是不是可以统计每个字符在该字符串中出现的次数?要达到这个目的,我们需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数,也就是说这个容器的作用是把一个字符映射成一个数字。在常用的数据容器中,哈希表正是这个用途。
哈希表是一种比较复杂的数据结构。由于比较复杂,STL中没有实现哈希表,因此需要我们自己实现一个。但由于本题的特殊性,我们只需要一个非常简单的哈希表就能满足要求。由于字符(char)是一个长度为8的数据类型,因此总共有可能256
种可能。于是我们创建一个长度为256的数组,每个字母根据其ASCII码值作为数组的下标对应数组的对应项,而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256,以字符ASCII码为键值的哈希表。
我们第一遍扫描这个数组时,每碰到一个字符,在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时,就能直接从哈希表中得到每个字符出现的次数了。
结果:
分享到:
相关推荐
1130:找第一个只出现一次的字符 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 82755 通过数: 31415 【题目描述】 给定一个只包含小写字母的字符串,请你找到第一个仅出现一次的字符。如果没有,输出no。 【输入...
java 寻找指定字符第一次出现的位置 java 寻找指定字符第一次出现的位置
在一个字符串中找到第一个只出现一次的字符
下面程序的功能是删除字符串中第一次出现的a字符。其中有两处错误.cpp
题目描述在一个字符串(0字符串长度,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).解
获取目标字符串在源字符串第一次出现的下标Demo
自写PHP strpos() 函数 查找字符串在另一字符串中第一次出现的位置. https://blog.csdn.net/qq_40534785/article/details/87939551
已知S和T,求得所有包含在S中而不包含在T中的字符构成的新串R, 以及新串R中的每个字符在串S中的第一次出现的位置
python 实现 第一个只出现一次的字符
字符串中第一个只出现一次的字符.md
给定一个字符串,在字符串中找到第一个连续出现至少k次的字符。 【输入】 第一行包含一个正整数k,表示至少需要连续出现的次数。1 ≤ k ≤ 1000。 第二行包含需要查找的字符串。字符串长度在1到2500之间,且不包含...
题目一 字符串中第一个只出现一次的字符哈希表题目二哈希表。
字符流中第一个只出现一次的字符(1).md
java基础面试题第一个只出现一次的字符本资源系百度网盘分享地址
select f_find('Ap@2233ll@@l@@','@') from dual 返回结果为5,代表‘@’在该字符串中出现5次。 同理 select f_find('Ap@223SWEQQQ3ll@@l@@','Q') from dual---返回3,代表Q在字符串中出现了3次, select f_find('我...
Delphi返回子字符串第一次出现的索引值,也就是位置,出现在第几个字符的位置,比如我是中国人中的“中”字第一次出现的索引值,Private declarations中“tion”第一次出现的索引值。示例截图所图所示。
209 · 第一个只出现一次的字符解:HashMap记录循环2次HashMap记录每个字符出现的次数public class Solution {* @para
编写函数void fun(char *s,char *t,char *p)将未在字符串s中出现、而在字符串t中出现的字符, 形成一个新的字符串放在p中,p中字符按原字符串中字符顺序排列,但去掉重复字符。 例如: 当s为"12345", t为"8624677"时, p...
查找字符串中指定的字符,并能返回其多次出现的每个位置。
给定一个字符串列表’strlist’和整数‘k’ 请编写函数‘func’, 它返回字符串列表中‘k’个相邻字符串中最长的第一个