PAT (乙级) 真题题解(五)-技术圈

建议：首选Python，然后是C/C++，Java就算了，不难发现PAT对Java并不友好。

难度排序：5 > 4 > 2 > 3 > 1

1.个位数统计(15分)

题意

一个不超过1000位的正整数 n，统计0-9出现的次数。

分析

遍历统计即可。

C++ 代码

#include <iostream>using namespace std;
int cnt[10];int main() {    string n;    cin >> n;    for (int i = 0; i < int(n.size()); i++) {        cnt[n[i] - '0']++;    }    for (int i = 0; i < 10; i++) {        if (cnt[i] > 0) {            cout << i << ":" << cnt[i] << endl;        }    }    return 0;}

Java 代码

import java.util.Scanner;
public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        String s = sc.next();        int[] cnt = new int[10];        for (int i = 0; i < s.length(); ++i) {            cnt[s.charAt(i) - '0']++;        }        for (int i = 0; i < 10; ++i) {            if (cnt[i] > 0) {                System.out.printf("%d:%d\n", i, cnt[i]);            }        }        sc.close();    }}

Python 代码

if __name__ == "__main__":    n = input()    for i in range(10):        cnt = n.count(str(i))        if cnt > 0:            print("%d:%d" % (i, cnt))

2.D进制的A+B(20分)

题意

输出A+B的D进制。

分析

先计算A+B的10进制和，再转为D进制，注意0要输出"0"。

C++ 代码

#include <iostream>using namespace std;
string translate(long long dec, long long radix) {    string res = "";    while (dec) {        res = (char)(dec % radix + '0') + res;        dec /= radix;    }    return res == "" ? "0" : res;}
int main() {    long long a, b, d;    cin >> a >> b >> d;    long long s = a + b;    cout << translate(s, d) << endl;    return 0;}

Java 代码

import java.util.Scanner;
public class Main {
    private static String translate(long dec, int radix) {        StringBuilder sb = new StringBuilder();        while (dec > 0) {            sb.append(Character.forDigit((int) (dec % radix), radix));            dec /= radix;        }        return sb.reverse().toString();    }
    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        long a = sc.nextLong();        long b = sc.nextLong();        int d = sc.nextInt();        long s = a + b;        String ans = translate(s, d);        if (ans.length() == 0) {            System.out.println("0");        } else {            System.out.println(ans);        }        sc.close();    }}

Python 代码

def translate(dec, radix):    if dec < 0:        return "-" + translate(-dec, radix)    elif dec == 0:        return "0"    elif dec < radix:        return str(dec)    else:        return translate(dec // radix, radix) + str(dec % radix)

if __name__ == "__main__":    A, B, D = map(int, input().split())    s = A + B    print(translate(s, D))

3.组个最小数(20分)

题意

给若干个数，找出由这些数组成的最小的那一个，0不能做首位。

分析

先把若干个数读到数组里，由小到大排序，若首位是0，那么遍历找出第一个不是0的数，与第一位交换位置。

C++ 代码

#include <algorithm>#include <iostream>#include <vector>using namespace std;
int cnts[10];vector<int> vec;int main() {    for (int i = 0; i < 10; i++) {        cin >> cnts[i];        for (int j = 0; j < cnts[i]; j++) {            vec.push_back(i);        }    }    sort(vec.begin(), vec.end());    int sz = vec.size();    if (vec[0] == 0) {        for (int i = 1; i < sz; ++i) {            if (vec[i] != 0) {                int t = vec[i];                vec[i] = vec[0];                vec[0] = t;                break;            }        }    }    for (int i = 0; i < sz; ++i) {        cout << vec[i];    }    return 0;}

Java 代码

import java.util.*;
public class Main {
    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int[] cnts = new int[10];        List<Integer> seqs = new ArrayList<>();        for (int i = 0; i < 10; i++) {            cnts[i] = sc.nextInt();            for (int j = 0; j < cnts[i]; j++) {                seqs.add(i);            }        }        sc.close();        Collections.sort(seqs);        if (seqs.get(0) == 0) {            for (int i = 1; i < seqs.size(); i++) {                if (seqs.get(i) != 0) {                    int t = seqs.get(i);                    seqs.set(i, seqs.get(0));                    seqs.set(0, t);                    break;                }            }        }        for (Integer i : seqs) {            System.out.print(i);        }    }}

Python 代码

if __name__ == "__main__":    cnts = list(map(int, input().split()))    seqs = []    for i, cnt in enumerate(cnts):        for _ in range(cnt):            seqs.append(str(i))
    seqs.sort()    if seqs[0] == "0":        for i in range(1, len(seqs)):            if seqs[i] != "0":                seqs[0], seqs[i] = seqs[i], seqs[0]                break    print("".join(seqs))

4.科学计数法(20分)

题意

输入一个科学计数法表示的数字，把该数字的普通表示输出，不能丢失精度。

分析

先找到E的位置，然后划分为左右两部分。
左半部分为数值部分，标记好正负，去掉符号位，保持类型为字符串。
右半部分为指数部分，标记好正负，去掉符号位，转为整数。
根据指数正负分两种情况，模拟小数点移动的过程。
判断是否以小数点结尾，若是，则把小数点去掉。
根据数值部分正负标记，判断是否要加负号。

C++ 代码

#include <iostream>using namespace std;
string zero(int n) {    if (n == 0)        return "";    return "0" + zero(n - 1);}
int main() {    string s;    cin >> s;    int sgn = 1;    if (s[0] == '-')        sgn = -1;    s = s.substr(1);    int eIdx = s.find('E');    string prefix = s.substr(0, eIdx);    int dotIdx = prefix.find('.');    string suffix = s.substr(eIdx + 1);    if (suffix[0] == '+')        suffix = suffix.substr(1);    int exp = stoi(suffix);    if (exp > 0) {        int sz = exp + 2 - prefix.size();        for (int i = 0; i < sz; i++)            prefix += '0';        prefix = prefix.substr(0, dotIdx) + prefix.substr(dotIdx + 1, exp) +                 '.' + prefix.substr(dotIdx + exp + 1);        sz = prefix.size() - 1;        if (prefix[sz] == '.')            prefix = prefix.substr(0, sz);    } else if (exp < 0) {        exp = -exp;        exp -= 1;        prefix = "0." + zero(exp) + prefix.substr(0, dotIdx) +                 prefix.substr(dotIdx + 1);    }    if (sgn == -1)        prefix = "-" + prefix;    cout << prefix << endl;    return 0;}

Java 代码

import java.util.*;
public class Main {    private static String repeatZero(int n) {        StringBuilder sb = new StringBuilder();        for (int i = 0; i < n; i++) {            sb.append("0");        }        return sb.toString();    }
    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        String s = sc.next();        sc.close();        int sgn = 1;        if (s.charAt(0) == '-')            sgn = -1;        s = s.substring(1);        int eIdx = s.indexOf('E');        String prefix = s.substring(0, eIdx);        int dotIdx = prefix.indexOf('.');        String suffix = s.substring(eIdx + 1);        if (suffix.charAt(0) == '+')            suffix = suffix.substring(1);        int exp = Integer.parseInt(suffix);        if (exp > 0) {            int sz = exp + 2 - prefix.length();            prefix += repeatZero(sz);            prefix = prefix.substring(0, dotIdx) + prefix.substring(dotIdx + 1, dotIdx + 1 + exp) + "."                    + prefix.substring(dotIdx + 1 + exp);            sz = prefix.length() - 1;            if (prefix.charAt(sz) == '.')                prefix = prefix.substring(0, sz);        } else {            exp = -exp;            exp -= 1;            prefix = "0." + repeatZero(exp) + prefix.substring(0, dotIdx) +                    prefix.substring(dotIdx + 1);        }        if (sgn == -1)            prefix = "-" + prefix;        System.out.println(prefix);    }}

Python 代码

if __name__ == "__main__":    val = input().strip()    sgn = 1    if val[0] == '-':        sgn = -1    val = val[1:]    eIdx = val.find('E')    prefix = val[:eIdx]    dotIdx = prefix.find('.')    suffix = val[eIdx + 1:]    if suffix[0] == '+':        suffix = suffix[1:]    exp = int(suffix)    if exp > 0:        prefix = prefix.ljust(exp + 2, '0')        prefix = prefix[:dotIdx] + prefix[dotIdx + 1:dotIdx +                                          1 + exp] + '.' + prefix[dotIdx + 1 + exp:]        if prefix[-1] == '.':            prefix = prefix[:-1]    elif exp < 0:        exp = -exp        exp -= 1        prefix = '0.' + ('0' * exp) + prefix[:dotIdx] + prefix[dotIdx + 1:]    if sgn == -1:        prefix = '-' + prefix    print(prefix)

5.反转链表

题意

输入N个链表节点，要求每k个要逆序，最后不满足k个的部分无需逆序。

分析

由于Python的灵活性，首选Python。
先读入N个节点，建立好地址与data，next的映射。
根据首地址，按地址顺序链接链表节点。
步长为k，遍历列表，判断当前部分长度是否为k，若是则逆序，否则无操作。

Python 代码

from sys import stdin, stdout
if __name__ == "__main__":    head, n, k = stdin.readline().split()    n, k = int(n), int(k)    mp = {}    for i in range(n):        addr, data, nxt = stdin.readline().split()        mp[addr] = (data, nxt)    cur = head    lst = []    while cur != '-1':        data, nxt = mp[cur]        lst.append([cur, data, nxt])        cur = nxt    ans = []    for i in range(0, len(lst), k):        sub = lst[i:i + k]        if len(sub) == k:            ans += sub[::-1]        else:            ans += sub[:]    if n == 1:        stdout.write("{} {} {}\n".format(ans[0][0], ans[0][1], '-1'))    else:        stdout.write("{} {} {}\n".format(ans[0][0], ans[0][1], ans[1][0]))        for i in range(1, len(ans) - 1):            stdout.write("{} {} {}\n".format(                ans[i][0], ans[i][1], ans[i + 1][0]))        stdout.write("{} {} {}\n".format(ans[-1][0], ans[-1][1], '-1'))

END

如果有什么疑问，都可以通过给本公众号发送消息联系到我。

点击阅读原文跳转到题目链接。