PAT_甲级_1105 Spiral Matrix
2021-02-28
阅读 2 分钟
978将给定的N个正整数按非递增的顺序，填入“螺旋矩阵”,所谓“螺旋矩阵”，是指从左上角第1个格子开始，按顺时针螺旋方向填充,要求矩阵的规模为m行n列，满足条件：m*n等于N；m>=n；且m-n取所有可能值中的最小值.
PAT_甲级_1057 Stack
2021-02-28
阅读 3 分钟
1.2k现有一个栈，对其进行执行N次基本操作，该操作有三种类型，分别是Pop,Push和PeekMedian，代表了出栈，入栈和获取栈中元素的中位数，要求按照每一次输入的指令进行相应的输出
PAT_甲级_1129 Recommendation System
2021-02-28
阅读 2 分钟
985根据用户每次点击的东西的编号，输出他在点当前编号之前应该给这个用户推荐的商品的编号，只推荐k个，也就是输出用户曾经点击过的商品编号的最多的前k个，如果恰好两个商品有相同的点击次数，就输出编号较小的那个。
PAT_甲级_1130 Infix Expression
2021-02-27
阅读 2 分钟
1k使用静态数组nodes存储每一个结点的信息，使用father数组记录所有结点的父亲结点，这样在遍历father的时候其值为0的就是根结点下标root。对于其中序遍历的输出，其特点是对于根结点没有左右括号，除此之外只要有孩子存在就一定有左右括号，单目运算一定在左边，然后就是双目运算和数字。
PAT_甲级_1128 N Queens Puzzle
2021-02-27
阅读 1 分钟
1.1k只需判断当前N个棋子是否在同一行或者对角线上，判断的方法就是在输入每一个棋子的位置的时候就去与前面的所有棋子比较其行是否一样或者判断行标之差的绝对值是否等于列表之差的绝对值，如果是说明不是N皇后的解，输出NO，否则输出YES
PAT_甲级_1126 Eulerian Path
2021-02-27
阅读 2 分钟
1.1k题目大意给定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 分钟
972因为对折后的绳子在之后又会继续对折，所以尽可能将长的绳子对折次数减少才能获得最长的绳子，所以将所有的绳子进行升序排序，然后依次对折就是最后的答案。
PAT_甲级_1124 Raffle for Weibo Followers
2021-02-27
阅读 1 分钟
895给定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 分钟
1k题目大意给定一个无向图，判断查询的路径是否是一个哈密顿圈。算法思路判断一条路径是一个哈密顿圈的方法为1、除了首尾节点其他节点没有重复,不重复的节点数目等于N2、首节点只能重复一次，所有节点数目为N+13、首尾节点得相等4、任意两点之间连通在输入每一条路径的时候，首先判断输入节点与上一个输入节点是否连通，如...
PAT_甲级_1120 Friend Numbers
2021-02-26
阅读 1 分钟
969题目大意如果两个数字的位数和相同，那么就说明这是一个好友数，现在给定N个数字，要求按照顺序输出不同的好友数算法思路在输入每一个数字的时候计算该数字的位数和，然后添加到set集合中，set集合的大小就是不同的好友数目，最后依次输出set集合中的元素。提交结果AC代码 {代码...}
PAT_甲级_1119 Pre- and Post-order Traversals
2021-02-26
阅读 3 分钟
1.1k在给定先序和后序序列后，我们只能通过先序第一个节点和后序最后一个节点相等来判断剩余的左右子树的范围，但是对于先序和后序中的左右子树的相对顺序是一致的，那么我们可以设置左子树的长度为leftSize，从0开始进行遍历，只要先序的左子树节点集合和后序的左子树节点集合相同(顺序可以不一样)，同时先序左子树的首节点...
PAT_甲级_1118 Birds in Forest
2021-02-26
阅读 2 分钟
1.3k现在有N张图片，每一张图片里面有K只鸟，在同一张图片中的鸟属于同一棵树，计算森林中树木的最大数目，并且对于任意一对鸟，判断是否在同一棵树上。
PAT_甲级_1117 Eddington Number
2021-02-26
阅读 1 分钟
1k既然要找到E的最大值,那么在每一天的骑行距离大于N的时候,E取得最大值N，这也是E的初始值。我们可以想到，(数组的下标值+1)其实就是第几天，那么将骑行的距离逆序排序，这样对于骑行距离大于(当前下标值+1)的位置，就是E的一个可能取值(E取下标值+1)，我们为了取得最大值就是不断往右移动，知道第一次出现骑行距离小于等...
PAT_甲级_1116 Come on! Let's C
2021-02-26
阅读 2 分钟
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 分钟
945首先我们将这n个数字依次插入到二叉搜索树中，然后使用层序遍历获取每一层节点的数目和最大层数maxLevel，L[maxLevel],L[maxLevel-1]就是最后一层和倒数第二层的节点个数
PAT_甲级_1113 Integer Set Partition
2021-02-25
阅读 1 分钟
932题目大意给定一个集合，含有n个数字，要求将其划分为长度为n1和n2的两个集合，并且要求两个集合和之差最大，n1与n2的差距最小算法思路最为直观的感受就是将数组进行排序，然后选取n/2长度的前半部分为第一个部分,剩下的为第二部分，这样两者元素个数之差最小，和之差最大。提交结果AC代码 {代码...}
PAT_甲级_1112 Stucked Keyboard
2021-02-25
阅读 3 分钟
1k一个键是坏键的前提是该字符每一次连续出现的次数一定是k的整数倍，那么我们可以先采用hasShownNotStucked哈希表记录那些一定是好键的字符，又由于坏键只记录一次就好，所以使用hasShownStucked记录记录已经出现过并确定是坏键的按键，避免重复添加。我们采用两边遍历的方式进行求解
PAT_甲级_1110 Complete Binary Tree
2021-02-23
阅读 2 分钟
1.2k题目大意给定一棵含有N个节点的二叉树,判断是否是完全二叉树算法思路判断一颗二叉树是否是完全二叉树的规则：1、如果出现只有右孩子节点的，一定不是2、如果出现只有左孩子或者没有孩子节点的，记录该情况3、如果当前有孩子，并且出现了情况2，一定不是4、遍历树中所有节点后，如果没有1和3，表明该树为完全二叉树遍历方...
PAT_甲级_1109 Group Photo
2021-02-23
阅读 2 分钟
933题目大意有N个人照相，现将N个人排成K行，每一行都有N/K个人，并按照如下规则排列1、对于多出来的人全部在最后一排2、前一排的人都比后一排的人矮3、每一行最高的人都在中间位置4、视角从下往上看(面对着看)，每一行最中间的人开始，先左再右形成非递增序列5、对于有相同身高的人，按照字典序升序排列现在要求你输出该排...
PAT_甲级_1108 Finding Average
2021-02-23
阅读 2 分钟
1k给定N个输入，这些输入中只有在[-1000,1000]内并且位数在2位以内的数字才是合法的，对于不合法的输入直接输出相关信息，对于合法的数字需要计算平均值并进行输出