冀教网 - 河北教师网站 - 专注于冀教版课本资源

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 24|回复: 0

UVA 156 Ananagrams STL应用

[复制链接]

4万

主题

4万

帖子

12万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
124999
发表于 2020-5-23 20:58 | 显示全部楼层 |阅读模式
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=92
给定若干单词,按字典序输出不存在重排的单词。(经测试,不包含重复的单词
重排单词:每个字母出现次数一样,但顺序不同,即对单词序列的一个排序
思路分析

是否满足重排可转换为等价问题:单词的构成字母与顺序无关,有两种解决思路(标准化

  • 字母计数:统计每个字母出现次数,若一致,说明满足重排
  1. mapdict; // 每个单词的字母出现次数->出现次数
复制代码

  • 统一排序:都按升序排列,若得到相同序列,说明满足重排
  1. map dict; // 标准化单词->出现次数
复制代码
因此在标准化单词(全转为小写)后,边可按照不同思路统计次数,并记录相应到旧单词映射

  • 定义set ans; 存储输出结果,自动按字典序排列
遍历每个标准化单词,若其出现次数为1,插入ans集合中,最后输出即可
AC代码(C++11,map标准化,顺序无关)

统一排序

[code]#includeusing namespace std;map dict; // 标准化单词->出现次数map trans; // 单词字母出现次数->原单词set ans; // 存储输出结果,按字典序排列string s, st;int main() {    while (cin >>s && s!= "#") {        st = s;        for (auto& ch : st) // 转为小写            if (ch >= 'A' && ch = 'A' && ch
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|冀教网 - 河北教师网站 - 专注于冀教版课本资源  

GMT+8, 2020-6-4 01:30 , Processed in 0.276626 second(s), 29 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表