POJ 1002 487-3279 電話號碼轉換與重複檢測完整解法

題目大意

給定多組電話號碼，格式包含數字、大寫字母及連字符。需將所有號碼統一轉換為標準格式（XXX-XXXX），找出重複出現的號碼並按字典序輸出及其出現次數。若無重複則輸出 "No duplicates."。

核心思路

1. 標準化轉換：建立字母到數字的映射表（A/B/C→2, D/E/F→3 ... W/X/Y/Z→9），忽略連字符，按順序提取數字，第 3 位後插入連字符
2. 排序去重統計：將所有標準化號碼存入二維字符數組，使用 qsort 配合 strcmp 排序，相同號碼必相鄰，單次掃描即可統計重複次數
3. 輸出控制：僅輸出計數 > 1 的號碼，若無任何重複輸出提示信息

關鍵數據結構

• char m[] = "22233344455566677778889999"：字母映射表，索引 ch - 'A' 直接獲取對應數字
• char p[100000][9]：存儲最多 10 萬個標準化號碼（8 字符 + \0）
• char buf[1000]：臨時讀取原始輸入行

完整 C 代碼實現

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char m[] = "22233344455566677778889999";
char p[100000][9], buf[1000];
int i, j, k, n, count, duplicate;

int compare(const void *elem1, const void *elem2) {
    return strcmp((char *)elem1, (char *)elem2);
}

int main() {
    scanf("%d\n", &n);
    for (i = 0; i < n; i++) {
        gets(buf);
        for (k = j = 0; buf[j]; j++) {
            if (buf[j] == '-') continue;
            if (buf[j] >= 'A' && buf[j] <= 'Z') {
                p[i][k] = m[buf[j] - 'A'];
            } else if (buf[j] >= '0' && buf[j] <= '9') {
                p[i][k] = buf[j];
            }
            if (++k == 3) p[i][k++] = '-';
        }
    }
    qsort(p, n, 9, compare);
    duplicate = 0;
    count = 0;
    for (i = 0; ++i <= n; ) {
        count++;
        if (strcmp(p[i-1], p[i])) {
            if (count > 1) {
                printf("%s %d\n", p[i-1], count);
                duplicate = 1;
            }
            count = 0;
        }
    }
    if (!duplicate) puts("No duplicates.");
    return 0;
}

複雜度分析

• 時間：O(n log n) 排序主導，n ≤ 100,000 完全可行
• 空間：O(n) 存儲號碼數組，約 900 KB

常見坑點提醒

• 輸入行可能包含空格，需用 gets 或 fgets 讀整行
• 字母映射表長度 26，'Q' 和 'Z' 在舊鍵盤無對應，題目數據保證不出現
• 排序比較函數必須強轉為 char* 避免指針算術錯誤
• 輸出格式：號碼與計數間單空格，每行一個結果

本題是字符串處理、排序應用與計數統計的經典組合，代碼簡潔高效，是 ACM 入門必刷好題。