1110 区块反转 – PAT乙级真题

给定一个单链表 L,我们将每 K 个结点看成一个区块(链表最后若不足 K 个结点,也看成一个区块),请编写程序将 L 中所有区块的链接反转。例如:给定 L 为 1→2→3→4→5→6→7→8,K 为 3,则输出应该为 7→8→4→5→6→1→2→3。

输入格式:

每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤105)、以及正整数 K (≤N),即区块的大小。结点的地址是 5 位非负整数,NULL 地址用 −1 表示。

接下来有 N 行,每行格式为:

Address Data Next

其中 Address 是结点地址,Data 是该结点保存的整数数据,Next 是下一结点的地址。

输出格式:

对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。

输入样例:

00100 8 3
71120 7 88666
00000 4 99999
00100 1 12309
68237 6 71120
33218 3 00000
99999 5 68237
88666 8 -1
12309 2 33218

输出样例:

71120 7 88666
88666 8 00000
00000 4 99999
99999 5 68237
68237 6 00100
00100 1 12309
12309 2 33218
33218 3 -1

分析:L为输入链表,ans为答案链表,二维数组E为区块链表。先将链表数据记录在结构体A中,遍历A将链表正确顺序记录在链表L中,然后需要重新定义链表长度n(因为有输入中有无效的假结点信息)。遍历链表L,将每K个结点所分隔成的区块保存在二维数组E中,再从后往前将区块链表E中的值添加到答案链表ans中,最后根据格式输出ans链表就好啦~ 

 

1109 擅长C – PAT乙级真题

当你被面试官要求用 C 写一个“Hello World”时,有本事像下图显示的那样写一个出来吗?

输入格式:

输入首先给出 26 个英文大写字母 A-Z,每个字母用一个 7×5 的、由 C 和 . 组成的矩阵构成。最后在一行中给出一个句子,以回车结束。句子是由若干个单词(每个包含不超过 10 个连续的大写英文字母)组成的,单词间以任何非大写英文字母分隔。

题目保证至少给出一个单词。

输出格式:

对每个单词,将其每个字母用矩阵形式在一行中输出,字母间有一列空格分隔。单词的首尾不得有多余空格。

相邻的两个单词间必须有一空行分隔。输出的首尾不得有多余空行。

输入样例:

输出样例:

分析:三维数组a中储存26个字母对应的图形矩阵,out中储存每行要输出的图形矩阵,同时初始化out所有元素为空格。字符串中可能存在乱七八糟的字符,所以用getline做句子的输入。句子的单词间以任何非大写字母分隔,用while循环遍历找到下标j为非大写字母所在下标,i为当前单词首下标,然后根据单词中每一个字母,将输出图形记录到out中,最后输出out数组~flag用来标记之前是否输出过一个单词,如果输出过,flag=1,则当再次需要输出单词之前需要先输出一个’\n’~

1108 String复读机 – PAT乙级真题

给定一个长度不超过 104 的、仅由英文字母构成的字符串。请将字符重新调整顺序,按 StringString.... (注意区分大小写)这样的顺序输出,并忽略其它字符。当然,六种字符的个数不一定是一样多的,若某种字符已经输出完,则余下的字符仍按 String 的顺序打印,直到所有字符都被输出。例如 gnirtSSs 要调整成 StringS 输出,其中 s 是多余字符被忽略。

输入格式:

输入在一行中给出一个长度不超过 104 的、仅由英文字母构成的非空字符串。

输出格式:

在一行中按题目要求输出排序后的字符串。题目保证输出非空。

输入样例:

sTRidlinSayBingStrropriiSHSiRiagIgtSSr

输出样例:

StringStringSrigSriSiSii

分析:字母的ASCII不会超过128,将输入的字符串in中所有字母出现的次数存储在数组a[128]中,然后重复遍历”String”字母,如果a数组中还有剩余某个对应字符就输出,并将该字符的剩余次数-1,flag = 1表示这轮循环还有输出,直到不再有输出(flag == 0)为止~ 

1107 老鼠爱大米 – PAT乙级真题

翁恺老师曾经设计过一款 Java 挑战游戏,叫“老鼠爱大米”(或许因为他的外号叫“胖胖鼠”)。每个玩家用 Java 代码控制一只鼠,目标是抢吃尽可能多的大米让自己变成胖胖鼠,最胖的那只就是冠军。

因为游戏时间不能太长,我们把玩家分成 N 组,每组 M 只老鼠同场竞技,然后从 N 个分组冠军中直接选出最胖的冠军胖胖鼠。现在就请你写个程序来得到冠军的体重。

输入格式:

输入在第一行中给出 2 个正整数:N(≤100)为组数,M(≤10)为每组玩家个数。随后 N 行,每行给出一组玩家控制的 M 只老鼠最后的体重,均为不超过 104 的非负整数。数字间以空格分隔。

输出格式:

首先在第一行顺次输出各组冠军的体重,数字间以 1 个空格分隔,行首尾不得有多余空格。随后在第二行输出冠军胖胖鼠的体重。

输入样例:

3 5
62 53 88 72 81
12 31 9 0 2
91 42 39 6 48

输出样例:

88 31 91
91

分析:d记录小组最胖老鼠,D记录总胖冠军鼠。直接取最大值就可以了~

 

1106 2019数列 – PAT乙级真题

把 2019 各个数位上的数字 2、0、1、9 作为一个数列的前 4 项,用它们去构造一个无穷数列,其中第 n(>4)项是它前 4 项之和的个位数字。例如第 5 项为 2, 因为 2+0+1+9=12,个位数是 2。

本题就请你编写程序,列出这个序列的前 n 项。

输入格式:

输入给出正整数 n(≤1000)。

输出格式:

在一行中输出数列的前 n 项,数字间不要有空格。

输入样例:

10

输出样例:

2019224758

分析:数组a[4]中始终保留前4项数字,如果n小于4,就输出前n项;如果n大于等于4,就先输出前四项,然后不断累加a[4]所有元素的值,并对10取余得到个位数字,输出后将a[4]替换为新的前4项方便下一次累加取余~ 

 

1105 链表合并 – PAT乙级真题

给定两个单链表 L1​=a1​→a2​→⋯→an−1​→an​ 和 L2​=b1​→b2​→⋯→bm−1​→bm​。如果 n≥2m,你的任务是将比较短的那个链表逆序,然后将之并入比较长的那个链表,得到一个形如 a1​→a2​→bm​→a3​→a4​→bm−1​⋯ 的结果。例如给定两个链表分别为 6→7 和 1→2→3→4→5,你应该输出 1→2→7→3→4→6→5。

输入格式:

输入首先在第一行中给出两个链表 L1​ 和 L2​ 的头结点的地址,以及正整数
N (≤105),即给定的结点总数。一个结点的地址是一个 5 位数的非负整数,空地址 NULL 用 -1 表示。

随后 N 行,每行按以下格式给出一个结点的信息:

Address Data Next

其中 Address 是结点的地址,Data 是不超过 105 的正整数,Next 是下一个结点的地址。题目保证没有空链表,并且较长的链表至少是较短链表的两倍长。

输出格式:

按顺序输出结果链表,每个结点占一行,格式与输入相同。

输入样例:

00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1

输出样例:

01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1

分析:用vector<int> L1、L2存储题目中给定的两个链表,vector<int> ans保存合并后的链表。将较长的一个链表存储在L1中,如果原本L1较短,则将L1与L2用swap函数互相置换~在链表合并的过程中,i从0开始,将L1中每个结点添加到ans中,如果当前i是奇数(i & 1不等于0)就把L2的一个结点添加到ans中,直到L2中没有剩余元素~如此反复,就大功告成啦。