MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 156 - Ananagrams
AOAPC II

UVaOJ 156 - Ananagrams

Chai
2021-11-24 0:00:00在线评测阅读 416

问题描述

p156

原题链接:UVaOJ 156 - Ananagrams

相关说明:本题为《算法竞赛入门经典(第2版)》例题 5-4

解法一:映射(Map)

使用 map<string, int> cnt 统计标准化 standard() 表示后单词 st_word 的出现数量,如果只出现过一次,说明该单词无法通过其它单词重新排序得到。注意输出也需要按照字典序。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
 
using namespace std;
 
string standard(string &s) {
  string res = "";
  for (auto c:s) res += tolower(c);
  sort(res.begin(), res.end());
  return res;
}
 
int main() {
  string word, st_word;
  vector<string> words;
  map<string, int> cnt;
  while (cin >> word && word[0] != '#') {
    words.push_back(word);
    st_word = standard(word);
    if (cnt.find(st_word) == cnt.end()) cnt[st_word] = 0;
    cnt[st_word] += 1;
  }
  sort(words.begin(), words.end());
  for (auto word: words) {
    st_word = standard(word);
    if (cnt[st_word] == 1) cout << word << endl;
  }
  return 0;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz