PAT 1035 Password 解題詳解：密碼混淆字符替換與賬戶修改統計

題目背景

PAT（Advanced Level）1035 題要求處理用戶賬戶密碼中的視覺混淆字符：將 '1' 替換為 '@'，'0' 替換為 '%'，'l'（小寫 L）替換為 'L'，'O'（大寫 O）替換為 'o'。需統計修改過的賬戶數量並按輸入順序輸出修改後的信息；若無修改則輸出特定格式提示（注意單複數區分）。

輸入輸出規範

• 輸入：正整數 N (≤1000)，隨後 N 行賬戶信息（用戶名 + 密碼，均為 ≤10 字符無空格字符串）
• 輸出：修改賬戶數 M 及修改後記錄；無修改時按 N 輸出 "There is 1 account..." 或 "There are N accounts..."

核心算法思路

1. 遍歷每個賬戶的密碼字符串
2. 檢查是否包含四類混淆字符（'1','0','l','O'）
3. 若包含則原地替換並標記該賬戶已修改
4. 將修改後的賬戶存入動態數組（vector）保持輸入順序
5. 最後根據修改數量決定輸出格式

AC 代碼（C++）

#include <cstdio>
#include <vector>
#include <string>
using namespace std;

int main() {
    int n;
    char name[20], pass[20];
    vector<string> modified; // 交替存儲：用戶名, 密碼, 用戶名, 密碼...
    
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s%s", name, pass);
        bool changed = false;
        for (char* p = pass; *p; ++p) {
            switch (*p) {
                case '0': *p = '%'; changed = true; break;
                case '1': *p = '@'; changed = true; break;
                case 'l': *p = 'L'; changed = true; break;
                case 'O': *p = 'o'; changed = true; break;
            }
        }
        if (changed) {
            modified.push_back(name);
            modified.push_back(pass);
        }
    }
    
    if (!modified.empty()) {
        printf("%d\n", (int)modified.size() / 2);
        for (size_t i = 0; i < modified.size(); i += 2) {
            printf("%s %s\n", modified[i].c_str(), modified[i+1].c_str());
        }
    } else {
        if (n == 1)
            printf("There is 1 account and no account is modified\n");
        else
            printf("There are %d accounts and no account is modified\n", n);
    }
    return 0;
}

關鍵技巧總結

• 字符串原地修改：直接操作 char 數組避免額外空間
• Vector 交替存儲：用單一 vector 維持用戶名-密碼配對順序，簡化輸出邏輯
• 輸出格式嚴格匹配：特別注意 "is/are" 及 "account/accounts" 的單複數變化
• 掃描輸入優化：使用 scanf 讀取無空格字符串，效率高於 iostream

複雜度分析

• 時間複雜度：O(N × L)，L 為密碼最大長度（≤10），實際極快
• 空間複雜度：O(M)，M 為修改賬戶數，最多 2N 個字符串