PAT (Advanced Level) Practice（更新中）

超、凢脫俗 2021-12-20 06:31 179阅读 0赞

### Source: ###

> [PAT (Advanced Level) Practice][PAT _Advanced Level_ Practice]

### Reference: ###

>  \[1\]胡凡,曾磊.算法笔记\[M\].机械工业出版社.2016.7

### Outline: ###

*  基础数据结构：
    
     *  线性表：栈，队列，链表，顺序表
     *  树：[二叉树的建立和遍历][Link 1]，[完全二叉树][Link 2]，[二叉查找树][Link 3]，[平衡二叉树][Link 4]，[堆][Link 5]，[哈夫曼树][Link 6]
     *  图：[图的存储和遍历][Link 7]
 *  经典高级算法：
    
     *  深度优先搜索，广度优点搜索，回溯剪枝
     *  贪心，[并查集][Link 8]，哈希映射[  
        ][Link 9]
     *  [最短路径][Link 10]（只考察过单源），[拓扑排序][Link 9]（18年9月第一次涉及相关概念，未正式考过），[关键路径][Link 11]（未考过）
 *  实现对复杂实际问题的模拟求解
    
     *  模拟题

### Catalogue: ###

*  [PAT A1155 Heap Paths (30 分)][PAT A1155_Heap Paths_30]【完全二叉树】【堆】【深度优先搜索】
 *  [PAT A1154 Vertex Coloring (25 分)][PAT A1154_Vertex Coloring_25]【图的存储和遍历】【哈希映射】
 *  [PAT A1153 Decode Registration Card of PAT (25 分)][PAT A1153_Decode Registration Card of PAT_25]【模拟题】
 *  [PAT A1152 Google Recruitment (20 分)][PAT A1152_Google Recruitment_20]【素数】
 *  
 *  [PAT A1151 LCA in a Binary Tree (30 分)][PAT A1151_LCA in a Binary Tree_30]【二叉树的建立】【二叉树的遍历】
 *  [PAT A1150 Travelling Salesman Problem (25 分)][PAT A1150_Travelling Salesman Problem_25]【图的存储和遍历】
 *  [PAT A1149 Dangerous Goods Packaging (25 分)][PAT A1149_Dangerous Goods Packaging_25]【哈希映射】
 *  [PAT A1148 Werewolf - Simple Version (20 分)][PAT A1148_Werewolf - Simple Version_20]【模拟题】
 *  
 *  [PAT A1147 Heaps (30 分)][PAT A1147_Heaps_30]【堆】【二叉树的遍历】
 *  [PAT A1146 Topological Order (25 分)][PAT A1146 Topological Order _25]【图的存储和遍历】【拓扑排序】
 *  [PAT A1145 Hashing - Average Search Time (25 分)][PAT A1145_Hashing - Average Search Time_25]【哈希映射】
 *  [PAT A1144 The Missing Number (20 分)][PAT A1144_The Missing Number_20]【哈希映射】
 *  
 *  [PAT A1143 Lowest Common Ancestor (30 分)][PAT A1143_Lowest Common Ancestor_30]【二叉查找树】【二叉树的建立】【二叉树的遍历】
 *  [PAT A1142 Maximal Clique (25 分)][PAT A1142_Maximal Clique_25]【图的存储和遍历】
 *  [PAT A1141 PAT Ranking of Institutions (25 分)][PAT A1141_PAT Ranking of Institutions_25]【模拟题】
 *  [PAT A1140 Look-and-say Sequence (20 分)][PAT A1140_Look-and-say Sequence_20]【模拟题】
 *  
 *  [PAT A1138 Postorder Traversal (25 分)][PAT A1138_Postorder Traversal_25]【二叉树的遍历】
 *  [PAT A1137 Final Grading (25 分)][PAT A1137_Final Grading_25]【模拟题】
 *  [PAT A1136 A Delayed Palindrome (20 分)][PAT A1136_A Delayed Palindrome_20]【模拟题】
 *  
 *  [PAT A1135 Is It A Red-Black Tree (30 分)][PAT A1135_Is It A Red-Black Tree_30]【二叉查找树】
 *  [PAT A1134 Vertex Cover (25 分)][PAT A1134_Vertex Cover_25]【图的存储和遍历】
 *  [PAT A1133 Splitting A Linked List (25 分）][PAT A1133_Splitting A Linked List_25]【链表】【哈希映射】
 *  [PAT A1132 Cut Integer (20 分)][PAT A1132_Cut Integer_20]【模拟题】
 *  
 *  [PAT A1129 Recommendation System (25 分)][PAT A1129_Recommendation System_25]【模拟题】
 *  [PAT A1128 N Queens Puzzle (20 分)][PAT A1128_N Queens Puzzle_20]【模拟题】
 *  
 *  [PAT A1127 ZigZagging on a Tree (30 分)][PAT A1127_ZigZagging on a Tree_30]【二叉树的建立】【二叉树的遍历】
 *  [PAT A1126 Eulerian Path (25 分)][PAT A1126_Eulerian Path_25]【图的存储和遍历】
 *  [PAT A1125 Chain the Ropes (25 分)][PAT A1125_Chain the Ropes_25]【哈夫曼树】【贪心】
 *  
 *  [PAT A1123 Is It a Complete AVL Tree (30 分)][PAT A1123_Is It a Complete AVL Tree_30]【平衡二叉树】【完全二叉树】【二叉树的遍历】
 *  [PAT A1122 Hamiltonian Cycle (25 分)][PAT A1122_Hamiltonian Cycle_25]【图的存储和遍历】
 *  [PAT A1120 Friend Numbers (20 分)][PAT A1120_Friend Numbers_20]【模拟题】
 *  
 *  [PAT A1119 Pre- and Post-order Traversals (30 分)][PAT A1119_Pre- and Post-order Traversals_30]【二叉树的建立】
 *  [PAT A1118 Birds in Forest (25 分)][PAT A1118_Birds in Forest_25]【并查集】
 *  [PAT A1116 Come on! Let's C (20 分)][PAT A1116_Come on_ Let_s C_20]【素数】
 *  
 *  [PAT A1115 Counting Nodes in a BST (30 分)][PAT A1115_Counting Nodes in a BST_30]【二叉查找树】
 *  [PAT A1114 Family Property (25 分)][PAT A1114_Family Property_25]【并查集】
 *  [PAT A1113 Integer Set Partition (25 分)][PAT A1113_Integer Set Partition_25]【模拟题】
 *  
 *  [PAT A1111 Online Map (30 分)][PAT A1111_Online Map_30]【最短路径】
 *  [PAT A1110 Complete Binary Tree (25 分)][PAT A1110_Complete Binary Tree_25]【完全二叉树】
 *  [PAT A1109 Group Photo (25 分)][PAT A1109_Group Photo_25]【模拟题】
 *  [PAT A1108 Finding Average (20 分)][PAT A1108_Finding Average_20]【字符串处理】
 *  
 *  [PAT A1107 Social Clusters (30 分)][PAT A1107_Social Clusters_30]【并查集】
 *  [PAT A1106 Lowest Price in Supply Chain (25 分)][PAT A1106_Lowest Price in Supply Chain_25]【二叉树的建立和遍历】
 *  [PAT A1105 Spiral Matrix (25 分)][PAT A1105_Spiral Matrix_25]【模拟题】
 *  
 *  [PAT A1099 Build A Binary Search Tree (30 分)][PAT A1099_Build A Binary Search Tree_30]【二叉树的建立】【二叉树的遍历】【二叉查找树】
 *  [PAT A1098 Insertion or Heap Sort (25 分)][PAT A1098_Insertion or Heap Sort_25]【堆】【插入排序】
 *  [PAT A1094 The Largest Generation (25 分)][PAT A1094_The Largest Generation_25]【二叉树的建立和遍历】
 *  
 *  [PAT A1090 Highest Price in Supply Chain (25 分)][PAT A1090_Highest Price in Supply Chain_25]【二叉树的建立和遍历】
 *  [PAT A1087 All Roads Lead to Rome (30 分)][PAT A1087_All Roads Lead to Rome_30]【最短路径】
 *  
 *  [PAT A1079 Total Sales of Supply Chain (25 分)][PAT A1079_Total Sales of Supply Chain_25]【二叉树的建立和遍历】
 *  [PAT A1078 Hashing (25 分)][PAT A1078_Hashing_25]【哈希映射】【素数】
 *  [PAT A1076 Forwards on Weibo (30 分)][PAT A1076_Forwards on Weibo_30]【图的存储和遍历】【广度优先搜索】
 *  
 *  [PAT A1072 Gas Station (30 分)][PAT A1072_Gas Station_30]【最短路径】
 *  
 *  [PAT A1066 Root of AVL Tree (25 分)][PAT A1066_Root of AVL Tree_25]【平衡二叉树】
 *  [PAT A1064 Complete Binary Search Tree (30 分)][PAT A1064_Complete Binary Search Tree_30]【完全二叉树】【二叉查找树】【二叉树的遍历】
 *  
 *  [PAT A1053 Path of Equal Weight (30 分)][PAT A1053_Path of Equal Weight_30]【二叉树的建立和遍历】
 *  
 *  [PAT A1043 Is It a Binary Search Tree (25 分)][PAT A1043_Is It a Binary Search Tree_25]【二叉查找树】【二叉树的建立】【二叉树的遍历】
 *  
 *  [PAT A1034 Head of a Gang (30 分)][PAT A1034_Head of a Gang_30]【图的存储和遍历】【深度优先搜索】
 *  
 *  [PAT A1030 Travel Plan (30 分)][PAT A1030_Travel Plan_30]【最短路径】
 *  [PAT A1021 Deepest Root (25 分)][PAT A1021_Deepest Root_25]【图的存储和遍历】【深度优先搜索】
 *  
 *  [PAT A1018 Public Bike Management (30 分)][PAT A1018_Public Bike Management_30]【最短路径】
 *  [PAT A1015 Reversible Primes (20 分)][PAT A1015_Reversible Primes_20]【进制转换】【素数】
 *  [PAT A1013 Battle Over Cities (25 分)][PAT A1013_Battle Over Cities_25]【图的存储和遍历】
 *  
 *  [PAT A1004 Counting Leaves (30 分)][PAT A1004_Counting Leaves_30]【二叉树的建立和遍历】
 *  [PAT A1003 Emergency (25 分)][PAT A1003_Emergency_25]【最短路径】

转载于:https://www.cnblogs.com/blue-lin/p/10940646.html

[PAT _Advanced Level_ Practice]: https://pintia.cn/problem-sets/994805342720868352/problems/type/7
[Link 1]: https://www.cnblogs.com/blue-lin/p/11102341.html
[Link 2]: https://www.cnblogs.com/blue-lin/p/10970168.html
[Link 3]: https://www.cnblogs.com/blue-lin/p/11082782.html
[Link 4]: https://www.cnblogs.com/blue-lin/p/10970187.html
[Link 5]: https://www.cnblogs.com/blue-lin/p/10834867.html
[Link 6]: https://www.cnblogs.com/blue-lin/p/11064493.html
[Link 7]: https://www.cnblogs.com/blue-lin/p/10878108.html
[Link 8]: https://www.cnblogs.com/blue-lin/p/11072511.html
[Link 9]: https://www.cnblogs.com/blue-lin/p/11040020.html
[Link 10]: https://www.cnblogs.com/blue-lin/p/11045148.html
[Link 11]: https://www.cnblogs.com/blue-lin/p/11041233.html
[PAT A1155_Heap Paths_30]: https://www.cnblogs.com/blue-lin/p/10829028.html
[PAT A1154_Vertex Coloring_25]: https://www.cnblogs.com/blue-lin/p/10847163.html
[PAT A1153_Decode Registration Card of PAT_25]: https://www.cnblogs.com/blue-lin/p/10853440.html
[PAT A1152_Google Recruitment_20]: https://www.cnblogs.com/blue-lin/p/10853591.html
[PAT A1151_LCA in a Binary Tree_30]: https://www.cnblogs.com/blue-lin/p/10864683.html
[PAT A1150_Travelling Salesman Problem_25]: https://www.cnblogs.com/blue-lin/p/10877802.html
[PAT A1149_Dangerous Goods Packaging_25]: https://www.cnblogs.com/blue-lin/p/10877855.html
[PAT A1148_Werewolf - Simple Version_20]: https://www.cnblogs.com/blue-lin/p/10877910.html
[PAT A1147_Heaps_30]: https://www.cnblogs.com/blue-lin/p/10890688.html
[PAT A1146 Topological Order _25]: https://www.cnblogs.com/blue-lin/p/10890934.html
[PAT A1145_Hashing - Average Search Time_25]: https://www.cnblogs.com/blue-lin/p/10914087.html
[PAT A1144_The Missing Number_20]: https://www.cnblogs.com/blue-lin/p/10914164.html
[PAT A1143_Lowest Common Ancestor_30]: https://www.cnblogs.com/blue-lin/p/10914437.html
[PAT A1142_Maximal Clique_25]: https://www.cnblogs.com/blue-lin/p/10915194.html
[PAT A1141_PAT Ranking of Institutions_25]: https://www.cnblogs.com/blue-lin/p/10916684.html
[PAT A1140_Look-and-say Sequence_20]: https://www.cnblogs.com/blue-lin/p/10917168.html
[PAT A1138_Postorder Traversal_25]: https://www.cnblogs.com/blue-lin/p/10928213.html
[PAT A1137_Final Grading_25]: https://www.cnblogs.com/blue-lin/p/10932423.html
[PAT A1136_A Delayed Palindrome_20]: https://www.cnblogs.com/blue-lin/p/10920330.html
[PAT A1135_Is It A Red-Black Tree_30]: https://www.cnblogs.com/blue-lin/p/10940375.html
[PAT A1134_Vertex Cover_25]: https://www.cnblogs.com/blue-lin/p/10946532.html
[PAT A1133_Splitting A Linked List_25]: https://www.cnblogs.com/blue-lin/p/11078360.html
[PAT A1132_Cut Integer_20]: https://www.cnblogs.com/blue-lin/p/10920429.html
[PAT A1129_Recommendation System_25]: https://www.cnblogs.com/blue-lin/p/10957549.html
[PAT A1128_N Queens Puzzle_20]: https://www.cnblogs.com/blue-lin/p/10921801.html
[PAT A1127_ZigZagging on a Tree_30]: https://www.cnblogs.com/blue-lin/p/10957755.html
[PAT A1126_Eulerian Path_25]: https://www.cnblogs.com/blue-lin/p/10960945.html
[PAT A1125_Chain the Ropes_25]: https://www.cnblogs.com/blue-lin/p/10961417.html
[PAT A1123_Is It a Complete AVL Tree_30]: https://www.cnblogs.com/blue-lin/p/10970085.html
[PAT A1122_Hamiltonian Cycle_25]: https://www.cnblogs.com/blue-lin/p/10970562.html
[PAT A1120_Friend Numbers_20]: https://www.cnblogs.com/blue-lin/p/10946553.html
[PAT A1119_Pre- and Post-order Traversals_30]: https://www.cnblogs.com/blue-lin/p/11000527.html
[PAT A1118_Birds in Forest_25]: https://www.cnblogs.com/blue-lin/p/11005772.html
[PAT A1116_Come on_ Let_s C_20]: https://www.cnblogs.com/blue-lin/p/11005952.html
[PAT A1115_Counting Nodes in a BST_30]: https://www.cnblogs.com/blue-lin/p/11006098.html
[PAT A1114_Family Property_25]: https://www.cnblogs.com/blue-lin/p/11073307.html
[PAT A1113_Integer Set Partition_25]: https://www.cnblogs.com/blue-lin/p/10946599.html
[PAT A1111_Online Map_30]: https://www.cnblogs.com/blue-lin/p/11032445.html
[PAT A1110_Complete Binary Tree_25]: https://www.cnblogs.com/blue-lin/p/11032261.html
[PAT A1109_Group Photo_25]: https://www.cnblogs.com/blue-lin/p/11032077.html
[PAT A1108_Finding Average_20]: https://www.cnblogs.com/blue-lin/p/11031717.html
[PAT A1107_Social Clusters_30]: https://www.cnblogs.com/blue-lin/p/11072913.html
[PAT A1106_Lowest Price in Supply Chain_25]: https://www.cnblogs.com/blue-lin/p/11102577.html
[PAT A1105_Spiral Matrix_25]: https://www.cnblogs.com/blue-lin/p/10991319.html
[PAT A1099_Build A Binary Search Tree_30]: https://www.cnblogs.com/blue-lin/p/11090635.html
[PAT A1098_Insertion or Heap Sort_25]: https://www.cnblogs.com/blue-lin/p/10835027.html
[PAT A1094_The Largest Generation_25]: https://www.cnblogs.com/blue-lin/p/11102780.html
[PAT A1090_Highest Price in Supply Chain_25]: https://www.cnblogs.com/blue-lin/p/11103007.html
[PAT A1087_All Roads Lead to Rome_30]: https://www.cnblogs.com/blue-lin/p/11045608.html
[PAT A1079_Total Sales of Supply Chain_25]: https://www.cnblogs.com/blue-lin/p/11103156.html
[PAT A1078_Hashing_25]: https://www.cnblogs.com/blue-lin/p/10859009.html
[PAT A1076_Forwards on Weibo_30]: https://www.cnblogs.com/blue-lin/p/10890553.html
[PAT A1072_Gas Station_30]: https://www.cnblogs.com/blue-lin/p/11046287.html
[PAT A1066_Root of AVL Tree_25]: https://www.cnblogs.com/blue-lin/p/11077654.html
[PAT A1064_Complete Binary Search Tree_30]: https://www.cnblogs.com/blue-lin/p/11090857.html
[PAT A1053_Path of Equal Weight_30]: https://www.cnblogs.com/blue-lin/p/11103446.html
[PAT A1043_Is It a Binary Search Tree_25]: https://www.cnblogs.com/blue-lin/p/11091224.html
[PAT A1034_Head of a Gang_30]: https://www.cnblogs.com/blue-lin/p/10887558.html
[PAT A1030_Travel Plan_30]: https://www.cnblogs.com/blue-lin/p/11051261.html
[PAT A1021_Deepest Root_25]: https://www.cnblogs.com/blue-lin/p/10887069.html
[PAT A1018_Public Bike Management_30]: https://www.cnblogs.com/blue-lin/p/11051669.html
[PAT A1015_Reversible Primes_20]: https://www.cnblogs.com/blue-lin/p/10853931.html
[PAT A1013_Battle Over Cities_25]: https://www.cnblogs.com/blue-lin/p/10878338.html
[PAT A1004_Counting Leaves_30]: https://www.cnblogs.com/blue-lin/p/11103632.html
[PAT A1003_Emergency_25]: https://www.cnblogs.com/blue-lin/p/11051952.html