PAT (Advanced Level) Practice 1061~1080

---

1061

---

1062

---

1063 Set Similarity

题意：
求两个集合公共整数个数和去掉重复元素后的总的整数个数的比值，并按百分比保留一位小数输出。

思路就不赘述了。

注意点：

• 集合可能存在重复的元素，所以需要用 set 来存储元素
• 直接输出结果的题目，就不用返回主函数了，在调用的函数里面输出即可。
• C++ 有丰富的函数调用方法，这一点平常要积累。

#include <cstdio>
#include <set>
using namespace std;const int N = 51;
set<int> st[N]; // N个集合void compare(int x, int y) // 比较集合 st[x] 与集合 st[y] 并输出结果
{
    int totalNum = st[y].size(), sameNum = 0; //不同数的个数、相同数的个数for(set<int>::iterator it = st [x].begin(); it != st [x].end(); ++it){
    if(st[y].find(*it) != st[y].end())++sameNum; // 在 st[y] 中能找到该元素else ++totalNum; //在 st[y] 中不能找到该元素}printf("%.1f%\n", sameNum * 100.0 / totalNum); // 输出比率
}int main()
{
    int n, k, q, v, st1, st2;scanf("%d", &n); // 集合个数for(int i = 1; i <= n; ++i){
    scanf("%d", &k); // 集合 i 中的元素个数for(int j = 0; j < k; ++j){
    scanf("%d", &v); // 集合 i 中的元素 vst[i].insert(v); // 将元素 v 加入集合 st[i] 中}}scanf("%d", &q); // q 个查询for(int i = 0; i < q; ++i){
    scanf("%d%d", &st1, &st2); // 欲对比的集合编号compare(st1, st2);}
}

---

1064

---

1065

---

1066

---

1067

---

1068

---

1069 The Black Hole of Numbers

题意：
对于给定的 [0, 10000) 以内的数，将其各个位上的数字重新组合得到的最大值减去最小值得到一个新的数，重复进行该步骤最后总会得到6174，要求打印出其变换的过程。

注意点：

• 要用 do…while 循环，因为如果输入的 n 为6174，至少要输出一次 7641 - 1467 = 6174再退出循环，用 while 循环则会出错；
• 用长度为4的数组 arr 存储输入的数的各个位上的数；
• 对四个位都相等的数进行特判；
• 对数组 arr 进行从小到大的排序，顺位即为最小值，逆位即为最大值；
• 注意输出的格式里，每一个数都需要用 %04d 进行输出；
• 当 n 等于6174时退出循环。

#include<cstdio>
#include<algorithm>
using namespace std;int main()
{
    int n, small[4], big[4];scanf("%d", &n);do{
    int temp = n;for (int i = 0; i < 4; ++i){
    small[i] = temp % 10;temp /= 10;}if (small[0] == small[1] && small[1] == small[2] && small[2] == small[3]){
     // 如果各数位上的数相等printf("%04d - %04d = 0000", n, n);break; // 退出循环}sort(small, small + 4); // 对 small 数组进行排序，使得其为int a = small[0] * 1000 + small[1] * 100 + small[2] * 10 + small[3];int b = small[3] * 1000 + small[2] * 100 + small[1] * 10 + small[0];n = b - a;printf("%04d - %04d = %04d\n", b, a, n); // 全部用 %04d 输出，包括相减的结果} while(n != 6174);return 0;
}

---

1070

---

1071 Speech Patterns

题意：
令“单词”的定义为大小写字母、数字的组合。给出一个字符串，问出现次数最多的单词及其出现次数（一切除了大小写字母、数字之外的字符都作为单词的分隔符）。其中字母不区分大小写，且最后按小写字母输出。

思路：

1. 枚举字符串中的字符，如果该字符是构成单词的字符，则将其加入当前单词中（如果是大写字母，则将其替换为对应的小写字母）；如果该字符不是构成单词的字符，则将当前单词的出现次数加1（使用 map 实现)。之后跳过非单词字符，进行下一个单词的组合。
2. 遍历 map 中的所有元素，获取出现次数最多的单词。

注意点：

• 题目规定了单词由大小写字母、数字组成，因此 can1 与 can 是两个不同的单词。
• 在得到一个单词 temp 之后，必须先查看 map 中是否已经存在该单词。如果单词 temp 不存在，则不能直接对其出现次数加1，而应直接将其出现次数赋值为1。

#include <iostream>
#include <map>
using namespace std;//Can1: "Can a can can a can? It can!"bool isAlphaNum(char c)
{
    if ((c >= '0' && c <= '9') || (c >='a' && c <= 'z') || (c >= 'A' && c <= 'Z'))return true;else return false;
}int main()
{
    map<string, int> word; // word 计数字符串出现的次数string str;getline(cin, str); // 读取字符串int i = 0; // 下标while (i < str.length()) // 枚举字符串的每个字符{
    while (i < str.length() && !isAlphaNum(str[i]))++i; // 跳过非单词字符string temp; // 记录连续的单词while (i < str.length() && isAlphaNum(str[i])){
     // 如果是单词的字符if (str[i] >= 'A' && str[i] <= 'Z')str[i] += 32; // 转为小写字母temp += str[i]; // 将 str[i] 加到 temp 后++i; // 下标后移一位}if (word.find(temp) == word.end())word[temp] = 1;else ++word[temp];++i;}string k;int MAX = 0;for (map<string, int>::iterator it = word.begin(); it != word.end(); ++it){
     // 寻找出现次数最多的单词if (it -> second > MAX){
    k = it -> first;MAX = it -> second;}}cout << k << " " << MAX;return 0;
}

---

1072

---

1073

---

1074 Reversing Linked List

题意：
给出单链表的头结点地址、结点总数 N 以及步长 K。接下来 N 行条数据，每行给出结点的地址、数据以及下一个结点的地址。要求将链表从第一个结点开始每 K 个步长的结点反转，结尾不足 K个结点的不反转。最后按照地址、数据以及下一个结点的地址输出链表。

思路：
这一题比较注重细节，我想了得有四个小时，数据量比较小，而且有地址值，用静态链表做更为方便，但需要考虑以下三种情况：

• 链表长度不够步长，直接从正向输出即可；
• 链表长度只够一个步长（样例），只反转第一个步长的结点即可，然后输出结点情况。如 $1?2?3$，步长为2，输出的应该是 $2?1?3$；
• 链表长度不止一个步长，每 K 个步长的结点都要反转。如 $1?2?3?4?5?6$，步长为2， 输出的应该是 $2?1?4?3?6?5$。

如果说你的算法不打算改变结点的指针值，从前往后每 K 个每 K 个的输出，可能就很难实现 $1?4$ 这一步，即1的后继结点地址应该是结点4的地址。我在发现单向的静态链表难以实现之后转为双向静态链表，然后每 K 步从后往前输出。我反向输出了$2?1$，但我没有考虑到1此时的后继结点应该是4而不是3了。另外一个思路，用类似于指针单链表的处理方式，从前往后遍历，改变每一个结点的前驱和后继指针的指向，最后再一次性输出。缺点在于涉及到很多的指针操作，实现细节上容易出问题。试错了三四次后，我确定了如下的思路。

1. 定义静态链表。其中结点的性质由 int 型变量 order 定义，表示结点在链表中的序号（从0开始），无效结点的 order 值为 maxn；
2. 初始化。令 order 的初值均为 maxn，表示初始时所有结点都为无效结点；
3. 由题目给出的链表首地址 first 遍历整条链表，并记录每个有效结点在链表中的序号（即给 order 赋值），同时计数有效结点的个数 len。然后把 len 的值赋给 n，因为无效结点不输出；
4. 对结点进行排序，排序函数 cmp 的排序原则是直接按照结点的 order 从小到大排序。由于有效结点的 order 从0开始，无效结点的 order 均为 maxn，因此排序后前面的结点都是有效结点；
5. 输出链表。这题的题目条件较为烦琐。由于需要每 k 个结点反转1次，因此可以把 n 个结点分为 n / k 个完整的块，这时如果 n % k 不为0，那么后面会剩余一个不完整块，这个不完整块是不需要反转的；

枚举这些完整的块，对每一个块从后往前输出结点信息。唯一要注意的就是每一个块的最后一个结点的 next 的处理：设当前处理的是 i 号完整块的最后一个结点。

• 如果 i 号块不是最后一个完整块，那么 next 就是 (i + 1) 号块的最后一个结点，也 (i + 2) * k - 1 号结点（(i + 2) * k 表明的是第 i + 2 号完整块的第一个结点，减一就成了 (i + 1) 号完整块的最后一个结点）。
• 如果 i 号块是最后一个完整块，同样分为两种情况：

1. 如果 n % k 为0，说明这是整个单链表的最后一个结点，输出-1。
2. 如果 n % k 不为0，说明在这个完整块后面还有剩余不足 k 个结点的块。首先，这个完整块的最后一个结点的 next 是 (i + 1) * k 号结点，即不完整块的第一个结点；接下来，从前往后输出不完整块的所有结点。
3. 这两个分支可以自己动手模拟一下。

注意点：

• 要考虑可能存在无效结点的情况，即不是由题目给出的头结点引出的单链表上的结点，这些结点是要去掉的，最终不予输出。
• 反转链表只改变结点的 next 地址，而不会改变本身的地址，因此 addr 和 data 可以视为绑定的。
• %05d 的输出格式会使 -1 的输出称为 -0001，因此一定要将-1的输出跟其他地址的输出分开来考虑。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;struct Node{
     // 定义静态链表
int addr, data, next;
int order; // 结点在链表上的序号,无效结点记为 maxn
} node[maxn];bool cmp(Node a, Node b){
    return a.order < b.order; // 按 order 从小到大排序
}int main()
{
    for(int i = 0; i < maxn; ++i)node[i].order = maxn; // 全部初始化为无效结点int first, n, k, addr;scanf("%d%d%d", &first, &n, &k); // 起始地址、结点个数、步长for(int i = 0; i < n; ++i){
    scanf ("%d", &addr);scanf ("%d%d", &node[addr].data, &node[addr].next);node[addr].addr = addr;}int p = first, cnt = 0; // cnt 计数有效结点的数目while(p != -1) // 遍历链表找出单链表的所有有效结点{
    node[p].order = cnt++; // 结点在单链表中的序号p= node [p].next; // 下一个结点}sort(node, node + maxn, cmp); // 按单链表从头到尾顺序排列n = cnt;for(int i = 0; i < n / k; ++i) // 枚举完整的 n / k 块，输出单链表{
    for (int j = (i + 1) * k - 1; j > i * k; --j) // 第 i 号块倒着输出printf("%05d %d %05d\n", node[j].addr, node[j].data, node[j - 1].addr);//每一块的最后一个结点的 next 地址的处理printf("%05d %d ",node[i * k].addr, node[i * k].data);if(i < n / k - 1) // 如果不是最后一块,就指向下一块的最后一个结点printf("%05d\n", node[(i + 2) * k - 1].addr);else // 是最后一块时{
    if(n % k == 0) // 恰好是最后一个结点，输出-1printf("-1\n");else // 剩下的不完整块不需要反转输出{
    printf("%05d\n", node [(i + 1)* k].addr);for (int i = n / k * k; i < n; ++i){
    printf("%05d %d ", node[i].addr, node[i].data);if(i < n - 1)printf("%05d\n", node[i + 1].addr);elseprintf("-1\n");}}}}return 0;
}

---

1075

---

1076

---

1077

---

1078 Hashing

题意：
给出散列表长 TSize 和欲插入的元素，将这些元素按读入的顺序插入散列表中，其中散列函数为H(key) = key % TSize，解决冲突采用只往正向增加的二次探查法。另外，如果题目给出的 TSize 不是素数，那么需要将 TSize 重新赋值为第一个比 TSize 大的素数再进行元素插入。

思路：
思路

1. 首先，对于一个输入的哈希表大小 m，如果不是素数，则必须找到第一个比它大的素数。
2. 开一个 bool 型数组 hashTable[]，hashTable[x] == false 表示 x 号位未使用。对每个插入的元素 num，计算 num % m 并判断对应位置是否被使用。如果未被使用，那么就找到可以插入的位置并输出。
3. 如果已被使用，根据二次方探查法，令步长 step 初值为1，然后令下一个检测值为 (num + step * step) % m，判断该位置是否已被占用：如果已被占用，则令 ++step，再进行判断。当 step 自增达到 m 时如果还没有找到可用位置，则表明这个这个元素无法被插入。

注意点：

• Quadratic probing 是指二次方探查法，即当 H(a) 发生冲突时，让 a 按 $a+1^2,a?1^2,a+2^2,a?2^2,a+3^2,a?3^2.\dots$ 的顺序调整 a 的值。本题中已经说明只要往正向解决冲突，因此需要按 $a+1^2,a+2^2,a+3^2....$ 的顺序调整 a 的值。
• 出现“格式错误”的话需要注意，在最后一个输出结束后不能有空格。

为什么 step 自增到 m 仍找不到插入位置，对于大于等于 m 的值都不可能找到位置呢？
证明：
设 $0\le x<m$，那么
$(a+(m+x)(m+x))\%m$
$=(a+m^2+2mx+x^2)\%m$
$=(a+x^2)\%m+m^2\%m+2mx\%m$
$=(a+x^2)\%m?=0$
因此对于大于等于 m 的值都不可能找到位置插入，注意此处 $m^2\%m$ 以及 $2mx\%m$ 的结果都为0。

#include <iostream>
#include <cstdio>
using namespace std;bool hashTable[11111] = {
    false}; // hashTable[x] == false 表示 x 号位未使用bool isPrime(int a) // 判断 a 是否为素数
{
    if (a <= 1) return false;for (int i = 2; i * i <= a; ++i)if (a % i == 0)return false;return true;
}int main()
{
    int m, n, num, d;cin >> m >> n; // 初始哈希表大小，n 个待散列数据while (isPrime(m) == false)++m; // 寻找第一个大于等于 m 的素数while (n--){
    cin >> num; // 待散列数d = num % m; // 用 d 存储余数，后面的过程就不用再计算if (hashTable[d] == false) // 如果 d 号位未使用，则插入{
    cout << d;hashTable[d] = true;if (n != 0)cout << " ";}else{
    int step = 1;while (step < m){
    d = (num + step * step) % m;if (hashTable[d] == false){
    cout << d;hashTable[d] = true;break;}++step;}if (step >= m) // 找不到插入的地方cout << '-';if (n != 0)cout << " ";}}return 0;
}

---

1079

---

1080

---

一定要自己写一遍哦~~~