a712 - [POJ 1002] 487-3279
題目描述
題目要求處理電話號碼，將包含字母的電話號碼轉換為純數字形式，並找出重複的電話號碼。電話號碼的格式為七位數字，中間用連字符分隔。字母會根據電話鍵盤上的映射關係轉換為數字。如果有多個電話號碼相同，則輸出該電話號碼及其出現次數，並按電話號碼的字典序排序。如果沒有重複的電話號碼，則輸出 "No duplicates."。
解題思路
本題的核心思路是將包含字母的電話號碼轉換為純數字形式，然後使用哈希表（map）統計每個電話號碼出現的次數。具體步驟如下：
- 讀取輸入： 讀取電話號碼的數量，然後逐行讀取每個電話號碼。
- 轉換為數字： 對每個電話號碼，將字母轉換為對應的數字。根據題目提供的鍵盤映射關係，將 A, B, C 轉換為 2，D, E, F 轉換為 3，以此類推。
- 統計出現次數： 使用
map儲存轉換後的電話號碼及其出現次數。 - 輸出結果： 遍歷
map，找出出現次數大於 1 的電話號碼，按照字典序輸出電話號碼及其出現次數。如果沒有重複的電話號碼，則輸出 "No duplicates."。
複雜度分析
- 時間複雜度: O(N * K)，其中 N 是電話號碼的數量，K 是電話號碼的長度。轉換每個電話號碼需要 O(K) 的時間，遍歷所有電話號碼需要 O(N) 的時間，因此總時間複雜度為 O(N * K)。
- 空間複雜度: O(N)，其中 N 是電話號碼的數量。
map儲存所有唯一的電話號碼，因此空間複雜度為 O(N)。
程式碼
#include <iostream>
#include <map>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
string a;
int n;
cin >> n;
map < string , int > ans;
while(n--){
cin >> a;
string tmp;
for(int i=0,al=a.length();i<al;++i){
if(a[i]>='A'&&a[i]<='C')
tmp+='2';
else if(a[i]>='D'&&a[i]<='F')
tmp+='3';
else if(a[i]>='G'&&a[i]<='I')
tmp+='4';
else if(a[i]>='J'&&a[i]<='L')
tmp+='5';
else if(a[i]>='M'&&a[i]<='O')
tmp+='6';
else if(a[i]>='P'&&a[i]<='S'&&a[i]!='Q')
tmp+='7';
else if(a[i]>='T'&&a[i]<='V')
tmp+='8';
else if(a[i]>='W'&&a[i]<='Y')
tmp+='9';
else if(a[i]>='0'&&a[i]<='9')
tmp+=a[i];
}
++ans[tmp];
}
bool bb=0;
for(auto it=ans.begin();it!=ans.end();++it){
if(it->second>1){
bb=1;
string tmp=it->first;
for(int i=0;i<3;++i)
cout << tmp[i];
cout << "-";
for(int i=3;i<7;++i)
cout << tmp[i];
cout << " " << it->second << "\n";
}
}
if(bb==0){
cout << "No duplicates.\n";
}
}