例题5-3安迪的第一个字典 UVa10815--C++STL库映射set的应用_Old_Lu的博客-程序员宅基地_输入一个文本,找出所有不同的单词(连续的字母序列),按字典序从小到大输出。单 词

技术标签: c++  stl  C++STL  

前言

不定期更新C++的STL库以及算法练习的笔记
分享给大家 也是督促自己不断努力学习算法与程序设计
学习算法之前,要想高效简洁的写好代码,还需要熟练掌握STL库的一些方法和数据结构
参考书籍:
《算法竞赛入门经典》(第2版)刘汝佳 著
《挑战程序设计竞赛》巫泽俊 主译


一、题目描述

输入一个文本,找出所有不同的单词(连续的字母序列),按字典序从小到大输出。单词不区分大小写。
Sample Input
Adventures in Disneyland
Two blondes were going to Disneyland when they came to a fork in the
road. The sign read: “Disneyland Left.”
So they went home.
Sample Output
a
adventures
blondes
came
disneyland
fork
going
home
in
left
read
road
sign
so
the
they
to
two
went
were
when
注:文末附有原版英文题目

二、思路分析与代码书写

1.集合set

题目中提到“所有不同的单词”,一下子就能想到集合,因为集合具有互异性【任意一个元素不会在集合中出现多次】
此外,STL中的集合还默认将元素从小到大排列,这样还解决了字典序的问题。
综上,基于互异性和字典序,我们选择创建集合来解题。
如果对set的使用不熟练,或者第一次接触,可以看这一篇文章:
C++STL集合set基本使用

2.题目思路分析

①单词不区分大小写,显然我们需要有一个将单词统一成小写(因为小写字母占绝大多数)的过程。
②此外,样例输入的文本中有句点.也需要处理,否则影响我们程序的搭建。这里将句点统一换成空格(因为单词之间本身就是空格隔开)。
③一段文字可以是一个string。但显然我们希望一个单词是一个string。既然输入的是一段文本,也就是单词和空格的组合,那这时我们想到用stringstream流读入读出,也就是说从流里每次读出一个string并加入集合。显然如果这个单词已经出现过了,集合里不会重复添加。
④最后定义一个迭代器iterator,用以遍历集合中所有的单词并输出。

3.完整代码书写

该代码参考刘汝佳老师书上的代码,自己根据思路独立完成,可能细节上与老师略有不同。

首先是头文件,一个都不能少。(实际写代码过程中可能是边写边添加的)

#include<iostream>
#include<set>
#include<string>
#include<sstream>
#include<cctype>

其中cctype提供tolower()函数和isalpha()函数

考虑到文段中有字母空格和句点三种情况,因此分两类处理:
是字母的,变小写
否则,变空格

完整程序:

int main()
{
    
	string s,buf;
	while(cin>>s){
    
		if(s[0]=='#')break;//这里为了调试方便,输入#表示数据读取结束,不影响系统评判
		for(int i=0;i<s.length();i++){
    
			if(isalpha(s[i]))s[i]=tolower(s[i]);
			else s[i]=' ';
		}
		stringstream ss(s);
		while(ss>>buf)dict.insert(buf);//从字符串流中逐一读出每个词并添加到字典里 
	} 
	set<string>::iterator it;
	for(it=dict.begin();it!=dict.end();++it){
    
		cout<<*it<<endl;
	} 
	return 0;
}

提交结果

最后几句话

集合有着其互异性这一独特的特性,因此在许多竞赛和练习中应用广泛。
使用时务必记得头文件#include<set>
另外string和stringstream虽然好用。但是在算法竞赛中依然要慎重。因为string慢,stringstream更慢。
附:UVa10815原题:
在这里插入图片描述

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_46772309/article/details/119254139

智能推荐

c#+ArcGIS Engine-矢量要素赋值_jhoneyan的博客-程序员宅基地

上一篇介绍了矢量结构的创建方法,只是得到了空的矢量结构,里面的要素为空,现在介绍添加矢量要素并赋值的方法,以创建面图层为例。 /// <summary> /// 添加要素并赋值 /// </summary> /// <param name="pGrids">数据源</param> /// <param name="pFeatureCla

MySQL数据库空值和空字符串及NULL的分析_WorkLee的博客-程序员宅基地_mysql null as

文章中所有操作均是在 MySQL 5.7 版本下进行的区分空字符串和NULL数据库存储数据有必要搞清空值,空字符串和 NULL 的概念。空字符串是单引号引的,它其实是不占空间的。MySQL 中 null 其实是占空间的,官网文档里有说明。它们之前的长度验证:select length('') as '空串', length(null) as 'null', length(' ') as '空格字符串';+--------+------+-----------------+| 空串 ..

hive--2014.6.10_smtxyt的博客-程序员宅基地

1.ps -ef |grep hive               //查看hive进程 kill -9 6945 //关闭hive进程2.

预测Titanic号上的乘客生存概率_03_优化训练集_SongpingWang的博客-程序员宅基地

优化训练集—再次训练import numpy as npimport pandas as pdfrom sklearn import metricsfrom sklearn import model_selectionfrom sklearn.linear_model import LogisticRegressionfrom sklearn.svm import SVC,Linea...

cocos2dx 输入实时监听_实时流计算:Structured Streaming_wx wu的博客-程序员宅基地

背景上一篇文章:高威:Flink集群搭建​zhuanlan.zhihu.com介绍了Flink集群的搭建(单机版),其中介绍了当前最流行的3中实时开发中间件,其中spark中有两个:sparkStreaming和Structured Streaming。Sparkstreaming首次引入在0.*版本,其核心思想是利用spark批处理框架,以microbatch(以一段时间的流作为一个batch)...

随便推点

Compile Error - The Type Comparable is not generic解决方法_天高任鸟飞海阔凭鱼跃的博客-程序员宅基地

StringBuffer query = new StringBuffer(768); query.append(&quot;12312312&quot;); 以上第二句代码报错:The type Comparable is not generic, it cannot be parameterized with arguments&amp;lt;string&amp;gt;   百思不得其解。 ...

mysql 使用sql语句查询数据库所有表注释以及表字段的注释_政东.zd的博客-程序员宅基地_mysql查询表注释

mysql使用sql语句查询数据库所有表注释已经表字段注释场景:1. 要查询数据库 "mammothcode" 下所有表名以及表注释/* 查询数据库 ‘mammothcode’ 所有表注释 */SELECT TABLE_NAME,TABLE_COMMENT FROM information_schema.TABLES WHERE table_schema='mammothcode';2. 要查询表字段的注释/* 查询数据库 ‘mammothcode’ 下表 ‘t_adminuser

react项目中使用 Sass 或者 Less_halo1416的博客-程序员宅基地_react sass less

注意:1. 使用脚手架create-react-app 创建的 react项目,默认使用了webpack ==&gt;&gt; 请注意webpack的版本 2.create-react-app 创建的 react项目,webpack配置默认是隐藏的,如果需要查看或者修改,请使用npm run eject 命令, 3. 如果webpack是4.x...

Ubuntu E: 无法获得锁 /var/lib/dpkg/lock-frontend - open (11: 资源暂时不可用或没有文件)_mhrobot的博客-程序员宅基地_e: 无法获得锁 /var/lib/dpkg/lock-frontend - open (11: 资

1. 无法获得锁 /var/lib/dpkg/lock-frontend - open (11: 资源暂时不可用)当运行sudo apt-get install/update/或其他命令时,由于各种说不清的原因有时会出现如下提示:E: 无法获得锁 /var/lib/dpkg/lock-frontend - open (11: 资源暂时不可用)E: Unable to acquire the dpkg frontend lock (/var/lib/dpkg/lock-frontend), is ano

Uniapp引入json文件和引入Js文件_不用89k的博客-程序员宅基地_uniapp引入json文件

1.引入JSON 文件使用require// 引入json文件let dnf = require('@/data/person.json')json文件{ "code": "0001", "data": [{ "name": "赛利亚", "age": "16" }, { "name": "阿甘左", "age": "35" }, { "name": "诺顿", "age": "50" }]}主程序看下效果:2.引入JS文件2.1 方式一one.

PSRAM/SRAM与XMC硬件连接的推荐方法_李佳昕70的博客-程序员宅基地_psram接口

AN0068-PSRAM/SRAM与XMC硬件连接的推荐方法1、概述AT32系列的部分MCU产品集成XMC(外部存储器控制器)接口,支持外接PSRAM存储器扩展存储空间。其中144引脚封装MCU芯片支持连接地址数据非复用型PSRAM;而100引脚封装芯片因地址线缩减,仅支持连接地址数据复用型PSRAM。但目前市场上非复用型PSRAM较具价格优势,而AT32系列MCU又以100封装为大宗,形成器件选用和匹配上的予盾。若选择使用100引脚封装MCU芯片,就必须搭配复用型PSRAM。但PSRAM加上

推荐文章

热门文章

相关标签