算法练习（3）——C++ STL练习（2）题目1：反片语题目2：集合栈计算机（后续补充）题目3：团体队列题目4：丑数（后续补充）

74 阅读 0 评论 49 点赞

我是靠谱客的博主等待皮卡丘，最近开发中收集的这篇文章主要介绍算法练习（3）——C++ STL练习（2）题目1：反片语题目2：集合栈计算机（后续补充）题目3：团体队列题目4：丑数（后续补充），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目1：反片语

思路：

由于有了上篇博客题目中的经验，遇到不区分大小写，那就在判断时用临时变量保存调用tolower()函数转变成小写形式的字符串

1.可以写一个函数对每个单词标准化：全部转化为小写字母，然后再对字母排序

2.用map统计标准化每个单词出现的次数，标准化之后题目中能通过字母重排的单词相同

3.保存单词出现次数为1的原单词

4.对保存的单词进行字典排序，然后打印出来

代码实现：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;
//定义关联数组map用于统计每个单词出现的次数
map<string,int> timesOfWord;
//定义一个可变数组用于保存原单词
vector<string> words;
//标准化每个单词
	/*   注意：这个函数的定义不能直接返回引用，因为题目要求最终输出要保留输入中的大小写
	void standardizeWord(string &word)
	 */
//所以我们可以传入引用，在函数内部进行拷贝，然后返回拷贝的string对象
string standardizeWord(const string &word)
{
	//定义变量保存标准化的单词
	string standardWord = word;
	//遍历单词的每个字符，将每个字符转换成小写
	for(unsigned int i=0;i < word.length();i++)
	{
		tolower(standardWord[i]);
	}
	//对单词内的字符进行排序
	sort(standardWord.begin(),standardWord.end());
	return standardWord;
}

int main() {
	//定义一个变量用于保存用户输入的单词    注意：这道题目要求用户输入的是单词，所以除过结束字符'#'和字母字符没有其他字符
	string inputText;
	//执行一次循环cin每次读取多少字符？用什么标识来决定？
	//循环结束的标志：EOF   Unix和Linux:ctrl+D   windows:ctrl+Z和Enter
	//循环读取用户输入的单词
	while(cin >> inputText)
	{
		//遇到用户输入的结束符‘#’就结束循环
		if(inputText[0] == '#')
			break;
		//将单词保存在vector当中，用于最后进行输出
		words.push_back(inputText);
		//将接受到的单词进行标准化
		string standardWord = standardizeWord(inputText);
		//这里的判断是必要的，因为我们会在下面直接通过索引访问map,但是我们访问时必须保证我们所访问的键存在
		if(!timesOfWord.count(standardWord))
			timesOfWord[standardWord] = 0;
		//让标准化后的字符串统计数+1
		timesOfWord[standardWord]++;
	}
	//定义保存要输出单词的数组
	vector<string> savePrintStr;
	//将统计次数为1的字符串保存到savePrintStr
	for(unsigned int i=0;i < words.size();i++)
	{
		if(timesOfWord[standardizeWord(words[i])]==1)
		{
			savePrintStr.push_back(words[i]);
		}
	}
	//对要输出的字符串排序
	sort(savePrintStr.begin(),savePrintStr.end());
	//打印结果
	for(vector<string>::iterator it =savePrintStr.begin();it!=savePrintStr.end();it++)
		cout<<*it<<endl;
	return 0;
}

eclipse下运行结果：

知识点详细用法补充：（待补充）

while(cin >> inputText)中执行一次循环cin每次读取多少字符？用什么标识来决定？

题目2：集合栈计算机（后续补充）

思路：

代码实现：

eclipse下运行结果：

知识点详细用法补充：

题目3：团体队列

思路：本题没有使用书中原来的思路，通过参考作者思路和自己思考，使用了类似操作系统当中多级页表的原理

1. 定义两种队列：团队内部队列数组（这个数组可以使用关联数组，键：团队编号，值：团队队列），团队编号队列
2.入队：
        我们先判断该团队队列编号是否在团队编号队列中，
        如果在，我们对应到团队队列数组中可以用O(1)的时间复杂度找到对应团队编号的队列，将它插入到其中
       如果不在，我们将该团队编号入团队编号队列，同时新建该团队队列所对应的关联数组，将该编号入队

3.出队：
我们直接到团队编号队列的队首元素，然后对应到map中相应的队列的队首元素出队，
同时判断出队后，队列是否为空，如果为空，释放该map元素的内存

代码实现：

#include <iostream>
#include <queue>
#include <map>
using namespace std;

//函数声明
void q_enqueue();
void q_dequeue();
//这里使用vector可以吗？这样就可以不把数组长度写死，使用vector,array和内置数组有什么区别
//用于保存团队队列数组的最大团队数
const int arrSizeOfTeam=1000;
//保存每个团队成员信息，用键值对保存每个队员的编号和他所属队的编号，键：队员编号(唯一)    值：所属团队编号
map<int,int> teamMemInfo;

//团队编号队列
queue<int> numQueue;
//团队队列数组
map<int,queue<int>> queueMap;

//****************************************获取用户输入的指令，并执行相应的操作**************************
    //%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%下列思路类似于多级页表的原理%%%%%%%%%%%%%%%%%%%%%%%%%%
		//定义两种队列：团队内部队列数组（这个数组可以使用关联数组，键：团队编号，值：团队队列），团队编号队列
		//入队：
		//我们先判断该团队队列编号是否在团队编号队列中，
		//	如果在，我们对应到团队队列数组中可以用O(1)的时间复杂度找到对应团队编号的队列，将它插入到其中
		//  如果不在，我们将该团队编号入团队编号队列，同时新建该团队队列所对应的关联数组，将该编号入队
		//出队：
		//我们直接到团队编号队列的队首元素，然后对应到map中相应的队列的队首元素出队，
		//   同时判断出队后，队列是否为空，如果为空，释放该map元素的内存
void q_enqueue()
{
	queue<int> temp;//queue默认初始化时，队列中有元素吗？
	//获取用户输入的队员编号
	int mNum;
	cin>>mNum;
	//获取用户所在团队号
	int tNum= teamMemInfo[mNum];
	//团队队列map中是否有该团队号（键）
	if(!queueMap.count(tNum))
	{//没有该键的话，我们动态申请新建一个队列
		//queueMap[tNum] = new queue<int>();
		queueMap[tNum] = temp;
		numQueue.push(tNum);
	}
	queueMap[tNum].push(mNum);
}
void q_dequeue()
{
	//获取队列编号的队头编号
	int numDequeue = numQueue.front();
	//打印要出队的队员
	cout<<queueMap[numDequeue].front()<<endl;
	//找到队头编号队列，执行出栈
	queueMap[numDequeue].pop();
	//判断该对列是否为空，为空的话释放内存
	if(queueMap[numDequeue].empty())   //c++中map怎么删除元素，释放内存呢？
	{
		//将编号队列出队
		numQueue.pop();
		//delete queueMap[numDequeue];
		//c++中map怎么删除元素，释放内存呢？

	    for(map<int,queue<int>>::iterator it=queueMap.begin();it != queueMap.end();it++)
	    {
	    	if(it->first == numDequeue)
	    	{
	    		//delete it->second;
	    	    //it->second=NULL;
	    		//怎么释放一个queue的内存->STL容器的各种类型是如何释放内存的？
	    		queueMap.erase(it);
	    		break;
	    	}
	    }
	}
}

int main() {
	int scen = 0;//场景模拟的次数
	int teamNum = 0;//团队的数量

	while((cin>>teamNum)&&teamNum)    //获取用户输入的团队数量，并且保证团队数量不为0执行下面的操作才有意义
	{
		//每当执行循环的都是一次新的场景模拟，我们按照样例输出区分不同场景
		cout<<"Scenario #"<<++scen<<endl;
//****************************************获取用户输入的团队信息*****************************
		for(int i=0;i < teamNum;i++)
		{
			//获取用户输入的团队的成员数量
			int memNum;
			cin>>memNum;

			int tempMem;//用于接受用户临时保存的队员编号
			//记录用户输入的队员信息
			while(memNum--)
			{
				cin>>tempMem;
				teamMemInfo[tempMem]= i;
			}
		}

//判断用户输入的指令，执行相应的操作
		while(true)
		{
			//获取用户输入的指令
			string instruction;
			cin>>instruction;
			//判断用户输入的指令类型
			if(instruction[0] == 'S')//工程中这么判断缺乏安全性，在这里我们假设用户的输入都是合法输入
				break;
			else if(instruction[0] == 'D')
				q_dequeue();
			else if(instruction[0] == 'E')
				q_enqueue();
		}

		cout<<"第"<<scen<<"次模拟结束"<<endl;
	}

	return 0;
}

eclipse下运行结果：