PAT甲级题型总结（更新中）

动态规划：

1007 Maximum Subsequence Sum (25 分)最大连续子序列和

1040 Longest Symmetric String (25 分)

1045 Favorite Color Stripe (30 分)最长不下降子序列(LIS)

链表处理：

1032 Sharing (25 分)散列+数组模拟链表

• 1052. Linked List Sorting (25)-PAT甲级真题
• 1074. Reversing Linked List (25)-PAT甲级真题   乙级 1025 反转链表 (25 分)

• 1097. Deduplication on a Linked List (25)-PAT甲级真题

哈希散列

乙级1038 统计同成绩学生 (20 分)

乙级1039 到底买不买 (20 分)

1041 Be Unique (20 分)

• 1048. Find Coins (25)-PAT甲级真题(Hash散列)

• 1050. String Subtraction (20)-PAT甲级真题（哈希）
• 1078 Hashing (25 分)
• 1084. Broken Keyboard (20)-PAT甲级试题(乙级1029 旧键盘 (20 分))（getline string::npos用法    乙级1033 旧键盘打字 (20 分)）

• 1092. To Buy or Not to Buy (20)-PAT甲级真题

排序：

1089 Insert or Merge (25 分)乙级1035 插入与归并 (25 分)

1062 Talent and Virtue (25 分)       乙级1015 德才论 (25 分)

1098 Insertion or Heap Sort (25 分) 堆排序&插入排序

二叉搜索树：

• 1043. Is It a Binary Search Tree (25)-PAT甲级真题

1064

• Complete Binary Search Tree (30)-PAT甲级真题

• 1099. Build A Binary Search Tree (30)-PAT甲级真题

树的遍历：

• 1053. Path of Equal Weight (30)-PAT甲级真题(树的遍历)

• 1079. Total Sales of Supply Chain (25)-PAT甲级真题（dfs,bfs,树的遍历）
• 1090. Highest Price in Supply Chain (25)-PAT甲级真题

     1094. The Largest Generation (25)-PAT甲级真题（bfs,dfs,树的遍历）

贪心算法：

• 1038. Recover the Smallest Number (30)-PAT甲级真题（贪心算法）

1067 Sort with Swap(0, i) (25 分)

1070 Mooncake (25 分)     乙级1020 月饼 (25 分)

STL的使用

• 1054. The Dominant Color (20)-PAT甲级真题（map的使用，把map当做升序的数组使用）

• 1063. Set Similarity (25)-PAT甲级真题(set的使用)

查找

1085 Perfect Sequence (25 分)

栈模拟

1051 Pop Sequence (25 分)

最短路径

• 1003. Emergency (25)-PAT甲级真题（Dijkstra算法）
• 1018. Public Bike Management (30)-PAT甲级真题（Dijkstra + DFS）

图的遍历

1076 Forwards on Weibo (30 分)（bfs）