UVA 156 Ananagrams STL応用

2186 ワード

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=92
いくつかの単語を与え、辞書順に並べ替えられていない単語を出力します.(重複する単語を含まないテスト)
単語の並べ替え:各アルファベットの出現回数は同じですが、順序が異なります.つまり、単語のシーケンスの並べ替えです.

構想分析

並べ替えが等価に変換できる問題を満たすかどうか:単語の構成アルファベットは順序に関係なく,2つの解決構想(標準化)がある.

アルファベットカウント:各アルファベットの出現回数を統計し、一致すれば、再配置

を満たすことを示す.

map, int>dict; //  ->

統一ソート:いずれも昇順に並べられ、同じシーケンスが得られると、再配置

を満たすことを示す.

map dict; //  ->

したがって、標準化された単語(すべて小文字に変換)の後、異なる考え方で回数を統計し、古い単語へのマッピングを記録することができます.

定義set ans;は出力結果を格納し、

を辞書順に自動的に並べ替える.
各標準化単語を遍歴し,その出現回数が1であればans集合に挿入し,最後に出力すればよい.

ACコード（C++11，map標準化，順序無関係）

統合ソート

#include
using 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 <= 'Z') ch = tolower(ch); //  
        sort(st.begin(), st.end()); //  ， 
        dict[st]++; //  
        trans[st] = s; //  
    }
    for (auto p : dict) if (p.second == 1) ans.insert(trans[p.first]); //  1 
    for (auto& p : ans) cout <

アルファベット数

#include
using namespace std;
map, int>dict; //  -> 
map, string> trans; //  -> 
set ans; //  ， 
string s, st;
int main() {
    while (cin >>s && s!= "#") {
        st = s;
        map mp;
        for (auto& ch : st) {
            if (ch >= 'A' && ch <= 'Z') ch = tolower(ch); //  
            mp[ch] ++; //  
        }
        dict[mp]++; //  
        trans[mp] = s; //  
    }
    for (auto p : dict) if (p.second == 1) ans.insert(trans[p.first]); //  1 
    for (auto& p : ans) cout <

WebServiceローカルアクセスが正常で、リモートでアクセスできない問題を解決

UTとPowerMock