PAT_甲级_2020年冬季考试 7-3 File Path

2021-04-13
阅读 3 分钟
1.1k
The figure shows the tree view of directories in Windows File Explorer. When a file is selected, there is a file path shown in the above navigation bar. Now given a tree view of directories, your job is to print the file path for any selected file.

PAT_甲级_2020年冬季考试 7-2 Subsequence in Substring

2021-04-13
阅读 3 分钟
1.6k
A substring is a continuous part of a string. A subsequence is the part of a string that might be continuous or not but the order of the elements is maintained. For example, given the string atpaaabpabtt, pabt is a substring, while pat is a subsequence.

PAT_甲级_2020年冬季考试 7-1 The Closest Fibonacci Number

2021-04-13
阅读 2 分钟
1.1k
The Fibonacci sequence Fn is defined by $$F_{n+2} =F_{n+1} +F​_n \;\;for \;\;n≥0, with \;\;F_​0 =0 \;\;and\;\; F_​1 =1.$$ The closest Fibonacci number is defined as the Fibonacci number with the smallest absolute difference with the given integer N.

PAT_甲级_2020年冬季考试 7-4 Chemical Equation

2021-04-13
阅读 7 分钟
1.4k
A chemical equation is the symbolic representation of a chemical reaction in the form of symbols and formulae, wherein the reactant entities are given on the left-hand side and the product entities on the right-hand side. For example, $$CH_4+2O_2=CO_2+2H_2O$$

PAT_甲级_1105 Spiral Matrix

2021-02-28
阅读 2 分钟
1k
将给定的N个正整数按非递增的顺序,填入“螺旋矩阵”,所谓“螺旋矩阵”,是指从左上角第1个格子开始,按顺时针螺旋方向填充,要求矩阵的规模为m行n列,满足条件:m*n等于N;m>=n;且m-n取所有可能值中的最小值.

PAT_甲级_1057 Stack

2021-02-28
阅读 3 分钟
1.3k
现有一个栈,对其进行执行N次基本操作,该操作有三种类型,分别是Pop,Push和PeekMedian,代表了出栈,入栈和获取栈中元素的中位数,要求按照每一次输入的指令进行相应的输出

PAT_甲级_1129 Recommendation System

2021-02-28
阅读 2 分钟
1.1k
根据用户每次点击的东西的编号,输出他在点当前编号之前应该给这个用户推荐的商品的编号,只推荐k个,也就是输出用户曾经点击过的商品编号的最多的前k个,如果恰好两个商品有相同的点击次数,就输出编号较小的那个。

PAT_甲级_1130 Infix Expression

2021-02-27
阅读 2 分钟
1.1k
使用静态数组nodes存储每一个结点的信息,使用father数组记录所有结点的父亲结点,这样在遍历father的时候其值为0的就是根结点下标root。对于其中序遍历的输出,其特点是对于根结点没有左右括号,除此之外只要有孩子存在就一定有左右括号,单目运算一定在左边,然后就是双目运算和数字。

PAT_甲级_1128 N Queens Puzzle

2021-02-27
阅读 1 分钟
1.2k
只需判断当前N个棋子是否在同一行或者对角线上,判断的方法就是在输入每一个棋子的位置的时候就去与前面的所有棋子比较其行是否一样或者判断行标之差的绝对值是否等于列表之差的绝对值,如果是说明不是N皇后的解,输出NO,否则输出YES

PAT_甲级_1127 ZigZagging on a Tree

2021-02-27
阅读 2 分钟
1.1k
首先根据中序和后序遍历序列建立该二叉树,然后在层序遍历中使用level记录当前所在层次,每一次将当前层的所有结点都出队到temp数组中,更新子节点的level并入队,如果level是奇数就逆序temp,然后添加到ans数组中保存最终的层序遍历结果,++level。最后输出ans数组中的结果即可。

PAT_甲级_1126 Eulerian Path

2021-02-27
阅读 2 分钟
1.2k
题目大意给定N个顶点M条边的无向图,判断该图是Eulerian,semi-Eulerian还是non-Eulerian,并输出每一个顶点的度。算法思路首先得理清几个概念Eulerian path:恰好访问图中所有顶点的路径Eulerian circuit:Eulerian path的起点和终点相同Eulerian: 在一个连通图中所有顶点的度为偶数semi-Eulerian:连通图含有Eulerian ...

PAT_甲级_1125 Chain the Ropes

2021-02-27
阅读 1 分钟
1k
因为对折后的绳子在之后又会继续对折,所以尽可能将长的绳子对折次数减少才能获得最长的绳子,所以将所有的绳子进行升序排序,然后依次对折就是最后的答案。

PAT_甲级_1124 Raffle for Weibo Followers

2021-02-27
阅读 1 分钟
960
给定M条微博转发条目,针对每一个用户的转发条目,从中抽取一些人作为winner并给予奖品,第一个获奖的人是第S次转发的人,下一个获奖的人为上一个获奖人的位置加N,同一个人不能获奖两次,现在要求你输出获奖名单,对于没有人获奖的情况,输出Keep going...。

PAT_甲级_1123 Is It a Complete AVL Tree

2021-02-26
阅读 4 分钟
1.2k
首先需要对该AVL树进行建树操作(具体不细说,看代码即可),然后对该树进行层序遍历,一边输出层序变量序列,一遍判断该树是否是完全二叉树判断二叉树是否是完全二叉树的方法为:

PAT_甲级_1122 Hamiltonian Cycle

2021-02-26
阅读 2 分钟
1.2k
题目大意给定一个无向图,判断查询的路径是否是一个哈密顿圈。算法思路判断一条路径是一个哈密顿圈的方法为1、除了首尾节点其他节点没有重复,不重复的节点数目等于N2、首节点只能重复一次,所有节点数目为N+13、首尾节点得相等4、任意两点之间连通在输入每一条路径的时候,首先判断输入节点与上一个输入节点是否连通,如...

PAT_甲级_1121 Damn Single

2021-02-26
阅读 2 分钟
1k
使用一个map记录每一个人的couple,对于输入的所有的客人,只要没有出现在couple中,就说明是单身,添加进singles数组中,如果出现在了couple中但是其伴侣不在来访嘉宾中,说明此人也是单身,添加进singles数组中,最后输出singles数组即可。

PAT_甲级_1120 Friend Numbers

2021-02-26
阅读 1 分钟
1k
题目大意如果两个数字的位数和相同,那么就说明这是一个好友数,现在给定N个数字,要求按照顺序输出不同的好友数算法思路在输入每一个数字的时候计算该数字的位数和,然后添加到set集合中,set集合的大小就是不同的好友数目,最后依次输出set集合中的元素。提交结果AC代码 {代码...}

PAT_甲级_1119 Pre- and Post-order Traversals

2021-02-26
阅读 3 分钟
1.2k
在给定先序和后序序列后,我们只能通过先序第一个节点和后序最后一个节点相等来判断剩余的左右子树的范围,但是对于先序和后序中的左右子树的相对顺序是一致的,那么我们可以设置左子树的长度为leftSize,从0开始进行遍历,只要先序的左子树节点集合和后序的左子树节点集合相同(顺序可以不一样),同时先序左子树的首节点...

PAT_甲级_1118 Birds in Forest

2021-02-26
阅读 2 分钟
1.4k
现在有N张图片,每一张图片里面有K只鸟,在同一张图片中的鸟属于同一棵树,计算森林中树木的最大数目,并且对于任意一对鸟,判断是否在同一棵树上。

PAT_甲级_1117 Eddington Number

2021-02-26
阅读 1 分钟
1.1k
既然要找到E的最大值,那么在每一天的骑行距离大于N的时候,E取得最大值N,这也是E的初始值。我们可以想到,(数组的下标值+1)其实就是第几天,那么将骑行的距离逆序排序,这样对于骑行距离大于(当前下标值+1)的位置,就是E的一个可能取值(E取下标值+1),我们为了取得最大值就是不断往右移动,知道第一次出现骑行距离小于等...

PAT_甲级_1116 Come on! Let's C

2021-02-26
阅读 2 分钟
1.1k
题目大意给定一个长度为N的排名列表和长度为K的查询列表,需要你按照如下规则输出每一个查询的结果.1、排名第一的获得Mystery Award奖品2、排名为素数的获得Minion奖品3、所有其他参加比赛的人均获得Chocolate奖品4、对于非法查询输出Are you kidding?5、对于重复查询输出Checked算法思路按照规则模拟即可,使用valid数组...

PAT_甲级_1115 Counting Nodes in a BST

2021-02-25
阅读 2 分钟
991
首先我们将这n个数字依次插入到二叉搜索树中,然后使用层序遍历获取每一层节点的数目和最大层数maxLevel,L[maxLevel],L[maxLevel-1]就是最后一层和倒数第二层的节点个数

PAT_甲级_1114 Family Property

2021-02-25
阅读 3 分钟
1.1k
这是一道常规的并查集应用题目,我们首先使用families数组保存所有的输入集,并在输入的时候记录哪些是输入的成员(使用visited记录),并且合并那些是一家人的成员,这样就将所有成员都进行了归类在各自的家庭,然后计算每一个家庭的占地总面积和总房产数目,并且使用flag标记当前家庭(在[0,10000]中有意义的家庭),然后在...

PAT_甲级_1113 Integer Set Partition

2021-02-25
阅读 1 分钟
1k
题目大意给定一个集合,含有n个数字,要求将其划分为长度为n1和n2的两个集合,并且要求两个集合和之差最大,n1与n2的差距最小算法思路最为直观的感受就是将数组进行排序,然后选取n/2长度的前半部分为第一个部分,剩下的为第二部分,这样两者元素个数之差最小,和之差最大。提交结果AC代码 {代码...}

PAT_甲级_1112 Stucked Keyboard

2021-02-25
阅读 3 分钟
1.1k
一个键是坏键的前提是该字符每一次连续出现的次数一定是k的整数倍,那么我们可以先采用hasShownNotStucked哈希表记录那些一定是好键的字符,又由于坏键只记录一次就好,所以使用hasShownStucked记录记录已经出现过并确定是坏键的按键,避免重复添加。我们采用两边遍历的方式进行求解

PAT_甲级_1111 Online Map

2021-02-23
阅读 4 分钟
1.5k
题目大意现有N个节点和M条边的图,给定起点和终点,找出一条距离最短的路径和一条耗时最少的路径。其规则如下:1、对于有多条最短路径,找到耗时最短的2、对于有多条耗时最短路径找到岔路口(顶点)最少的3、如果最短路径和耗时最少路径一样,合并输出。算法思路此题为比较常规的最短路径问题,使用两次迪杰斯特拉算法就可...

PAT_甲级_1110 Complete Binary Tree

2021-02-23
阅读 2 分钟
1.3k
题目大意给定一棵含有N个节点的二叉树,判断是否是完全二叉树算法思路判断一颗二叉树是否是完全二叉树的规则:1、如果出现只有右孩子节点的,一定不是2、如果出现只有左孩子或者没有孩子节点的,记录该情况3、如果当前有孩子,并且出现了情况2,一定不是4、遍历树中所有节点后,如果没有1和3,表明该树为完全二叉树遍历方...

PAT_甲级_1109 Group Photo

2021-02-23
阅读 2 分钟
1k
题目大意有N个人照相,现将N个人排成K行,每一行都有N/K个人,并按照如下规则排列1、对于多出来的人全部在最后一排2、前一排的人都比后一排的人矮3、每一行最高的人都在中间位置4、视角从下往上看(面对着看),每一行最中间的人开始,先左再右形成非递增序列5、对于有相同身高的人,按照字典序升序排列现在要求你输出该排...

PAT_甲级_1108 Finding Average

2021-02-23
阅读 2 分钟
1.1k
给定N个输入,这些输入中只有在[-1000,1000]内并且位数在2位以内的数字才是合法的,对于不合法的输入直接输出相关信息,对于合法的数字需要计算平均值并进行输出

PAT_甲级_题目集合索引

2021-01-21
阅读 8 分钟
1.9k
在这里将PAT甲级的所有题目进行汇总在如下表格,其中没有跳转链接的表示还没有编写题解。本文会持续更新,旨在提供一站式PAT求解方案。题目题解1001 A+B Format (20分)PAT_甲级_1001 A+B Format1002 A+B for Polynomials (25分)PAT_甲级_1002 A+B for Polynomials1003 Emergency (25分)PAT_甲级_1003 Emergency1004 Coun...