2020华为秋招笔试题第一题C++实现(istringstream和unordered_map)

一、全量字符集与已占用字符集

输入描述:

输入一个字符串,字符串中包含了全量字符集和已占用字符集,两个字符集用@相连。@前的字符集合为全量字符集,@后的字符集为已占用字符集合。已占用字符集中的字符一定是全量字符集中的字符。字符集中的字符跟字符之间使用英文逗号分隔。字符集中的字符表示为字符加数字,字符跟数字使用英文冒号分隔,比如a:1,表示1个a字符。字符只考虑英文字母,区分大小写,数字只考虑正整形,数量不超过100,如果一个字符都没被占用,@标识符仍在,例如a:3,b:5,c:2@

输出描述:

可用字符集。输出带回车换行。

示例1:

输入:a:3,b:5,c:2@a:1,b:2

输出:a:2,b:3,c:2

说明:全量字符集为3个a,5个b,2个c。已占用字符集为1个a,2个b。由于已占用字符集不能再使用,因此,剩余可用字符为2个a,3个b,2个c。因此输出a:2,b:3,c:2。注意,输出的字符顺序要跟输入一致。不能输出b:3,a:2,c:2。如果某个字符已全被占用,不需要输出。例如a:3,b:5,c:2@a:3,b:2,输出为b:3,c:2。

方法:

主要用到了sstream库的istringstream类和string来实现分割截取和提取数据
一开始使用了map键值对来实现查找,后来发现map输入的数据会按键自动排序,而题目要求“输出的字符顺序要跟输入一致”,查阅资料(网络上有方法是通过重写比较函数,尝试了之后发现编译出错)后发现可以使用unordered_map来替代。
map是有序关联容器,基于红黑树的结构,unordered_map是无序关联容器,基于数据结构哈希表,不用对输入进行排序。这旨在提高添加和删除元素的速度以及提高查找算法的效率。

代码如下
#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>
using namespace std;

class Solution {
private:
	unordered_map<char, int>  character_set;
public:
	Solution(string str);
	void show(void) const;
};

Solution::Solution(string str)
{
	int loc = str.find('@');						// 分割
	string whole_ch = str.substr(0, loc);
	string occup_ch = str.substr(loc + 1);

	istringstream iss;								// 提取数据
	iss.str(whole_ch);
	char discard, letter;
	int num;
	// 注意这里,需要等到处理结束再接收并丢弃逗号,否则有bug
	while (iss >> letter >> discard >> num)
	{
		character_set[letter] = num;			// 直观插入键值方法
		// character_set.insert(pair<char, int>(letter, num));  // 普通插入键值方法
		iss >> discard;								// 处理结束后接收逗号
	}

	if (!occup_ch.empty())
	{
		iss.clear();						// 再次使用时,必须调用成员函数clear()进行清除
		iss.str(occup_ch);
		while (iss >> letter >> discard >> num)
		{
			auto iter = character_set.find(letter);
			if (iter != character_set.end())
			{
				iter->second -= num;
			}
			iss >> discard;
		}
	}
	// 去掉值为0的键
	auto iter = character_set.begin();
	while (iter != character_set.end())	// 迭代进行删除的方法
	{
		if (iter->second == 0)
			iter = character_set.erase(iter);
		else
			iter++;
	}
}

void Solution::show(void) const
{
	/*for (auto var : character_set)
		showElement(var);*/
	auto iter = character_set.begin();
	cout << iter->first << ":" << iter->second;
	iter++;
	while(iter != character_set.end())
	{
		cout << ",";
		cout << iter->first << ":" << iter->second;
		iter++;
	}
	cout << endl;
}

int main()
{
	//string tmp;
	//cin >> tmp;
	//Solution test(tmp);
	Solution test("c:12,b:5,a:13,d:100,e:88@b:5,e:88");
	test.show();

	return 0;
}

##### 运行结果
![运行结果](https://www.icode9.com/i/ll/?i=20200316162002368.JPG)
上一篇:java补充:网络编程


下一篇:InetAddress对象的使用