PAT -- 字符串处理篇(共3题,持续更新...)

Jul 10, 2019 | 数据结构与算法 | 阅读 | 1.4k 字 | 7 分钟

题目来源:

本文记录 PAT 中关于 字符串处理 的相关习题(包括甲乙级)与笔者的解题思路及代码, 由于篇幅较长, 建议读者通过 侧边目录框或顶部目录按键 选择想要查看的习题, 且由于习题内容较多, 此处仅贴出题干部分不包含输入输出样例, 具体内容可 点击标题 跳转至原题页面进行查看与代码提交.

A1035 Password (20 分)

To prepare for PAT, the judge sometimes has to generate random passwords for the users. The problem is that there are always some confusing passwords since it is hard to distinguish 1 (one) from l (L in lowercase), or 0 (zero) from O (o in uppercase). One solution is to replace 1 (one) by @, 0 (zero) by %, l by L, and O by o. Now it is your job to write a program to check the accounts generated by the judge, and to help the juge modify the confusing passwords.

#include <cstdio>
#include <cstring>
const int maxn = 1010;

struct node{
    char name[20],pwd[20];
    bool isChanged;
}user[maxn];

void checkPwd(node& t, int& cnt){
    int len = strlen(t.pwd);
    for (int i = 0; i < len; i++){
        if(t.pwd[i] == '1'){
            t.pwd[i] = '@';
            t.isChanged = true;
        }else if(t.pwd[i] == '0'){
            t.pwd[i] = '%';
            t.isChanged = true;
        }else if(t.pwd[i] == 'l'){
            t.pwd[i] = 'L';
            t.isChanged = true;
        }else if(t.pwd[i] == 'O'){
            t.pwd[i] = 'o';
            t.isChanged = true;
        }
    }
    if(t.isChanged) cnt++;
}

int main(){
    int n,cnt = 0;
    scanf("%d",&n);
    for (int i = 0; i < n; i++){
        scanf("%s %s",user[i].name,user[i].pwd);
        checkPwd(user[i],cnt);
    }
    if(cnt == 0)
        if(n == 1)
            printf("There is 1 account and no account is modified");
        else
            printf("There are %d accounts and no account is modified",n);
    else{
        printf("%d\n",cnt);
        for (int i = 0; i < n; i++){
            if(user[i].isChanged)
                printf("%s %s\n",user[i].name,user[i].pwd);
        }
    }
    return 0;
}

A1077 Kuchiguse (20 分)

The Japanese language is notorious for its sentence ending particles. Personal preference of such particles can be considered as a reflection of the speaker’s personality. Such a preference is called “Kuchiguse” and is often exaggerated artistically in Anime and Manga. For example, the artificial sentence ending particle “nyan~” is often used as a stereotype for characters with a cat-like personality:

Itai nyan~ (It hurts, nyan~)
Ninjin wa iyada nyan~ (I hate carrots, nyan~)

Now given a few lines spoken by the same character, can you find her Kuchiguse?
题意: 首先, 先对题目中对日语中句子结尾的 particles 用 臭名昭著 (notorious)来形容表示赞同. 题目大意即求得给出的 N 个字符串中的 公共后缀, 如果不存在则输出 nai.
思路:
1. 对于此等类似的题目 (即从 字符串末位 开始比较) 其一贯做法就是对字符串进行反转, 建议的使用 algorithm 头文件下的 reverse 函数通过字符串的首尾指针进行反转
2. 给出的 N 个字符串, 其公共后缀最大长度不可能超过给出的字符串中最短的字符串长度, 故在存储以上字符串时获取到最短长度 minLen
参考代码:

注意: 代码中通过 fgets 函数读入字符串是易错点
具体参考我的另一篇文章 C 之 gets与fgets

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 256;
int minLen = 256;   // 记录可能的最长公共后缀位数

int main(){
    int n;
    scanf("%d",&n);
    getchar();
    char str[100][maxn];
    int len;
    for (int i = 0; i < n; i++){
        fgets(str[i],sizeof(str[i]) + 2,stdin);
        len = strlen(str[i]);
        str[i][--len] = '\0';
        reverse(str[i],str[i] + len);
        if(len < minLen) minLen = len;
    }

    int same = -1,cnt;
    char ans[maxn];
    for (int i = 0; i < minLen; i++){
        cnt = 0;
        char c = str[0][i];
        for (int j = 1; j < n; j++){
            if(c == str[j][i])
                cnt++; 
        }
        if(cnt == n - 1){
            same = i;
        }else{
            break;
        }
    }

    if(same >= 0)
        for (int i = same; i >= 0; i--){
            printf("%c",str[0][i]);
        }
    else
        printf("nai");
    return 0;
}

A1082 Read Number in Chinese (25 分)

Given an integer with no more than 9 digits, you are supposed to read it in the traditional Chinese way. Output Fu first if it is negative. For example, -123456789 is read as Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu.
Note: zero ( ling ) must be handled correctly according to the Chinese tradition. For example, 100800 is yi Shi Wan ling ba Bai.

题意: 给定一个不超过9位数的整数(不包括符号), 用传统中文的方式输出这个数的读法(即拼音 ), 如果是负数, 需要先读出 Fu
思路:
1. 用 字符串数组 的方式储存读入的整数(惯用方法)
2. 由于零在这个数中有特定的读法, 因此把该数字拆成三部分分别来读, 每4位为一部分, 用 left,right 标志位标记当前部分的首尾下标

参考代码:

#include <cstdio>
#include <cstring>
char num[10][5] = {"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
char wei[5][5] = {"Shi","Bai","Qian","Wan","Yi"};

int main(){
    char str[15];
    scanf("%s",str);
    int len = strlen(str);
    int left = 0,right = len - 1;
    if(str[0] == '-'){
        left++;
        printf("Fu"); // 如果为负数,输出"Fu"
    }
    while(left + 4 <= right){
        right -=4;  // 将right下标左移4位,直到与left在同一4位数部分中
    }
    while(left < len){  // 每次循环处理一个部分(每4位为一部分)
        bool flag = false;  // 该位前是否包含0.
        bool isPrint = false;   // 表示该位是否被输出
        while(left <= right){   // 该循环结束表示该部分处理完毕
            if(left > 0 && str[left] == '0'){   // 如果当前位为0
                flag = true;
            }else{  // 如果当前位不为0
                if(flag == true){
                    printf(" ling");
                    flag = false;
                }
                if(left > 0) printf(" ");
                printf("%s",num[str[left] - '0']);  // 输出当前数字
                isPrint = true;
                if(left != right){
                    printf(" %s",wei[right - left - 1]);
                }
            }
            left++;
        }
        if(isPrint == true && right != len - 1){
            printf(" %s",wei[(len - 1 -right) / 4 + 2]);
        }
        right += 4; // 右移4位,输出下一部分
    }
    return 0;
}

本文作者：Char Jin
本文链接：https://blog.charjin.top/2019/07/10/pat-string-processing-updating/
版权声明：本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 CN 许可协议。转载请注明出处！

PAT 编程字符串处理