はじめに
最近、コーディングテストの準備をしており、練習問題をまとめています。 元々はC言語の経験しかありませんでしたが、実際に使用会发现C++の方がテストに向いています。ライブラリ関数も豊富で、より多くの操作をサポートでき、コードを簡潔に記述できます。 例えば、C言語で文字列を定義するにはchar s[1000]が必要ですが、C++ではstring sだけで済みます。
問題の説明
B. Santa Claus and Keyboard Check
入力: 標準入力
出力: 標準出力
時間制限: 2秒
メモリ制限: 256MB
サンタクロースはキーボードを分解して掃除することにしました。キーを元に戻した後、一部のキーが入れ替わっていることに気づきました。つまり、各キーは元の位置にあるか、別のキーの位置に移動しているかのいずれかです。
お気に入りの文字列をキーボードを見ながらタイプしてもらい、入力された文字列が与えられます。どのキーのペアが入れ替わっている可能性があるかを判定してください。各キーは最多で1回だけペアに参加できます。
入力形式
2つの文字列 s と t が与えられます。sはお気に入りの文字列、tは実際にタイプされた文字列です。s と t は空ではなく、同じ長さ（最大1000）です。両方の文字列は小文字の英文字のみで構成されます。
出力形式
もしキーボードを修復できない場合は、-1を出力してください。
otherwise、第1行目に交換する必要があるキーのペアの数 k を出力します。続く k 行には、スペースで区切られた2つの文字を出力し、交換する必要があるキーを示します。出力される文字はすべて異なる必要があります。
複数の答えがある場合は、いずれを出力しても問題ありません。ペアの順序とペア内のキーの順序は自由です。
例
入力:
helloworld
ehoolwlroz
出力:
3
h e
l o
d z
入力:
hastalavistababy
hastalavistababy
出力:
0
入力:
merrychristmas
christmasmerry
出力:
-1
問題を理解するまで10分かかりました。。。
要するに、2つの文字列が与えられ、キーが間違って配置されているために一部の文字が入れ替わっている可能性を修復する話です。修復可能であれば、エラーのペア数とすべての錯誤キーのペアを出力し、修復できない場合は-1を出力します。完全に正しい場合は0を出力します（これは修復可能な特殊情况です）。
解法と実装
まず、私の元のコードは以下の通りです（14番目のテストケースでエラーが発生するため、問題点を特定できていない状態です）。
クリックしてコードを表示
#include<bits/stdc++.h>
using namespace std;
int main(){
char input[1000], expected[1000], mapping[2000], ch1, ch2;
int used[1000] = {0};
int pairCount = 0;
gets(input);
gets(expected);
int len = strlen(input);
int i = 0, j = 0, idx = 0;
if(strcmp(input, expected) == 0){
cout << 0 << endl;
return 0;
}
while(i < len){
if(input[i] == expected[i]){
++i;
}
else{
ch1 = input[i];
ch2 = expected[i];
for(j = i + 1; j < len; j++){
if((expected[j] == ch2 && input[j] != ch1) ||
(input[j] == ch1 && expected[j] != ch2) ||
(expected[j] == ch1 && input[j] != ch2) ||
(input[j] == ch2 && expected[j] != ch1)){
cout << -1 << endl;
return 0;
}
}
mapping[idx++] = ch1;
mapping[idx++] = ch2;
pairCount++;
for(j = i; j < len; j++){
if(expected[j] == ch2) used[j] = 1;
if(expected[j] == ch1){
expected[j] = ch2;
}
}
for(j = i; j < len; j++){
if(used[j] == 1){
expected[j] = ch1;
used[j] = 0;
}
}
}
}
if(strcmp(input, expected) == 0){
cout << pairCount << endl;
for(i = 0; i < idx; i = i + 2){
cout << mapping[i] << " " << mapping[i+1] << endl;
}
return 0;
}
}
次に、ある方のACコード（参考: https://www.cnblogs.com/happy-MEdge/p/10455803.html）を拝見し、mapを使用する方法があることを知りました。映射関係をどのように建立すればよいか分からなかったので，下次はmapを.systematicallyに学習する必要があります。
解法思路
C++のmapを使用して、双方向の映射関係を建立できます。後の組み合わせがこの映射関係不符合の場合は-1を出力し、符合する場合は前に記録した映射関係を出力します。配列を使用してこれらの映射関係を保存できます（1文字保存すれば、mapを通じて另一方の文字にアクセスできます）。
クリックしてコードを表示
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
map<char, char> relation;
char pairList[30];
int totalPairs = 0;
int main(){
string pattern, actual;
cin >> pattern >> actual;
int length = pattern.length();
for(int i = 0; i < length; i++){
if(relation[pattern[i]] == 0 && relation[actual[i]] == 0){
relation[pattern[i]] = actual[i];
relation[actual[i]] = pattern[i];
if(pattern[i] != actual[i]){
pairList[++totalPairs] = pattern[i];
}
}
else if(relation[pattern[i]] != actual[i] || relation[actual[i]] != pattern[i]){
cout << -1 << endl;
return 0;
}
}
cout << totalPairs << endl;
for(int i = 1; i <= totalPairs; i++){
printf("%c %c\n", pairList[i], relation[pairList[i]]);
}
return 0;
}