鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > cms安装教程 > z-blog > >

第17 题:题目:在一个字符串中找到第一个只出现一次的字符。如

来源:互联网 作者:佚名 时间:2015-10-18 05:47
第17 题: 题目 :在 一个 字符 串 中 找到 第 一个 只 出现 一次的 字符 。如 输入 abaccdeff,则 输出 b。 分析:这道题是2006 年google 的一道笔试题。 申请26个数据结构来记录每个 字符 出现 的次数及最后 一个 的位置。 如果 字符 包含数字或者其他符号

 第17 题:
题目:在一个字符找到一个出现一次的字符。如输入abaccdeff,则输出b。
分析:这道题是2006 年google 的一道笔试题。

 

申请26个数据结构来记录每个字符出现的次数及最后一个的位置。

如果字符包含数字或者其他符号的话,可以申请256个该类型数组结构来存储。

 

#include <iostream>
#include <string>
#include <cassert>

using namespace std;

struct Record
{
	int index;
	int count;
};

char getFirstOnlyOneChar(string& str)
{
	// all char in str should be lower case
	Record records[26];

	memset(records, 0, sizeof(Record) * 26);

	for (int i = 0; i < str.length(); i++)
	{
		assert((str[i] <= 'z') && (str[i] >= 'a'));
		records['z' - str[i]].count++;
		records['z' - str[i]].index = i;
	}

	int index = str.length();
	for (int i = 0; i < 26; i++)
	{
		if (records[i].count == 1)
		{
			if (records[i].index < index)
				index = records[i].index;
		}
	}

	return str[index];
}
/*
int main(void)
{
	string str = "abaccdeff";

	cout << getFirstOnlyOneChar(str) << endl;

	system("pause");

	return 0;
}
*/


 

上一篇:对CSDN的建议
下一篇:Vim正则表达式整理
网友评论
<