PAT刷题经验(1)，看此一遍文章就够了！ |
您所在的位置：网站首页 › pat平台所有编程题答案数据结构 › PAT刷题经验(1)，看此一遍文章就够了！ |
|
目录 PAT乙级和甲级是什么 考PAT对学习 | 考研 | 工作的作用是什么 刷PAT乙级和甲级需要掌握哪些知识 关于PAT刷题中编程语言选择和开发环境IDE选择的⼀些愚见 PAT乙级和甲级是什么 和其他算法竞赛考试⽐起来，知道 PAT 的⼈确实不多～所以我在这⾥简单介绍⼀下～ PAT 是⼀场算法考试，考试的分数只要不是 0 分就会获得 PAT 相应等级的证书～ PAT 有三个等级：⼄级（ Basic ）、甲级（ Advanced ）、顶级（ Top ），考试时间都是 3 ⼩时，满分都是 100分，每年组织三次考试，分别在 3 ⽉、 9 ⽉、 12 ⽉～⼀般安排在⽉初或⽉中的周六，具体⽐赛时间在 报名前才会公布～全国有很多考点，每个考点所拥有的开发环境和版本也不⼀样，可以在官⽹（ https://www.patest.org/location ）这⾥看到各考点的开发环境～⼀般情况下我们会选择最近的那个考点， 不过也不⼀定，⽐如离你最近的那个考点提供的 C/C++ 语⾔编译环境没有 Dev-C++ 只有 Visual Studio ，⽽你⼜⾮常喜欢 Dev-C++ 写代码，那也可以选有 Dev-C++ 的考点～⽐如在我第⼀次参加 PAT 的时候，南京当时还没有考点，我就去了提供 Dev-C++ 的浙江⼤学紫⾦港校区参加考试～还有⼀点就 是，报名要趁早，有的时候某个考场报满了就⽆法在该考场报名只能去其他考场报名啦（⽐如我⼀个 ⼩伙伴报名晚了，南京考场都报满了，只能报了苏州，做⾼铁去苏州参加 PAT 考试 … ）报名费之前是 200元，现在是 256 元～（⽐蓝桥杯竞赛报名费便宜耶 - - ） 整个 PAT 考试的流程是：等到开放报名⼊⼝的时候在官⽹报名 -> ⾃⼰把⽹⻚上的准考证打印⼀下 -> 考 试当天带着身份证、准考证和笔去考场 -> 在电脑上做题⽬（和平时刷题⼀样提交后就能看到这道题的得分）-> 等到 3 ⼩时考试时间到（考 100 分就可以提前交卷出考场啦） -> 考完等⼤概半⼩时，考点当场打印证书，拿着证书回家～ ⼄级是 5 道中⽂题⽬，分别是 15 分、 20 分、 20 分、 20 分、 25 分，官⽹题库链接： https://pintia.cn/probl em-sets/994805260223102976/problems 甲级是 4 道英⽂题⽬，分别是 20 分、 25 分、 25 分、 30 分，官⽹题库链接： https://pintia.cn/problem-set s/994805342720868352/problems 顶级是 3 道英⽂题⽬，由于顶级题⽬偏难，⼀般 ACM ⼤佬才参加顶级，加上我⾃⼰也没有参加过，所以就不多介绍啦～（相信参加顶级的⼀定对PAT ⽐较了解不需要我来介绍啦 = = ） 最近 PAT 题库中还推出了基础编程题⽬集，⽐⼄级还要更基础（简单）⼀些，如果觉得⼄级的难度还不够简单可以去体验⼀下题库～链接： https://pintia.cn/problem-sets/14/problems （⼀般情况下我觉得直接从⼄级or 甲级开始刷题就 ok 啦～） 刷题的话还是在官⽹ pintia （ PTA ）的题库刷⽐较好，我听说有些⼈是从⽜客⽹或者其他地⽅刷题的，然⽽很多时候虽然可能题⽬相似，但内部具体的测试样例还是有些不⼀样的，所以同样⼀段代码提交上去可能会产⽣不同的结果，⽐如我博客某篇题解代码，很多⼈来评论说在⽜客⽹上⽆法通过，但在官⽹能通过，说我的代码没有考虑周全，最后发现是⽜客⽹的内部测试样例没有按照题意来设计… 当然有的时候也会发现官⽹通过了⽜客⽹没通过时确实是⾃⼰的代码有疏漏，没有考虑到⼀些边界情况，正好官⽹的判题样例也没有考虑到… （这个时候我会把⾃⼰的代码完善⼀下）～官⽹的题库从上到下的顺序就是每⼀次PAT 考试产⽣的题⽬，在考试过程中也使⽤的是和官⽹ OJ 题库中同样的判题系统，相⽐较⽽⾔更真实可靠～所以还是推荐⽤官⽹PTA （ https://pintia.cn/ ）直接刷题吖～ 考PAT对学习 | 考研 | 工作的作用是什么 这也是很多⼈会在刚知道 PAT 的时候问我的问题～ 学习⽅⾯：刷算法题当然对提⾼算法有很⼤帮助呀～刷完⼄级，基本上就理解和掌握了基础的数据结构（数组、链表、字符串）～也会了⼀些⽐基础的算法（⽐如排序、查找、递归），最重要的是，很多⼈刚⼊代码的坑，⾃⼰的思维⽆法准确的⽤代码来描述，想到的解决思路却⽆法⽤代码表达出来，⼄级刷完就完全可以解决这个问题啦～刷完甲级，⾸先已经能看懂英⽂的算法题⽬描述了～然后还能理解和熟练使⽤⼀些经典的算法，⽐如最短路径、并查集、树、图、深度优先搜索、⼴度优先搜索、贪⼼算法、拓扑排序、哈希等等～对⾃⼰的算法能⼒的提⾼是显著的～ 考研⽅⾯：⾸先说浙⼤计算机院，浙⼤计算机系的考研是分为初试和复试，复试⼜分为机试和⾯试，机试的题⽬就是类似于PAT 甲级考试的题⽬（每年机试过后的题⽬也会增加到甲级题库后⾯），⽽且机试可以申请免试，只要具有前⼀年的3 ⽉、 9 ⽉、 12 ⽉的任意⼀次 PAT 甲级的证书即可～要知道把所有的机会都压在机试那⼀次是⽐冒险的，⼀般情况下⼤家都会在3 ⽉复试之前拿着前⼀年 3 次 PAT 考试中最⾼的那次成绩申请浙⼤计算机系考研的复试机试免考，这样就可以在复试中更加稳妥啦～不仅是甲级的成绩可以免机试，顶级的成绩也可以，顶级成绩乘以1.5 可以充当机试成绩（最⾼ 100 分），例如顶级考了67 分及以上，就可以和甲级 100 分⼀样～我认识的很多其他学校的考研 or 保研的学⽣也会参加PAT考试，为了得到⼀张满意成绩的证书，这样就能在考研 or 保研的⾯试过程中更加具有竞争⼒～ ⼯作⽅⾯：⾸先说 PAT 企业联盟， PAT 和很多企业合作，这也是为什么 PAT 定在 3 ⽉（春招） 9 ⽉（秋招）12 ⽉（秋招补招 or 寒假实习）的原因～在 PAT 报名的时候填写⾃⼰的个⼈信息，如果是有求职意向的，可以对⾃⼰的个⼈简历写详细些，让企业知道你是打算找⼯作的并且更加了解你拥有的技能和想应聘的职业，这样在考完后会收到很多企业的邀请⾯试的邮件～也可以主动拿着PAT 的证书在有效期内（有的是⼀年，有的是两年，不同公司规定不同）去这些和PAT 联盟的企业，⼀般都可以免笔试并优先录取，⽐如Google 中国的要求是：甲级前 15 名、顶级前 20 名且 80 分以上， 2 年有效，可以免除笔试，直接进⼊Google 的⾯试阶段；微软的要求是：甲级 90 分以上，并且排名在当场考试前 30 名，同时符合微 软项⽬招聘的要求（毕业时间和专业等），可免技术笔试进⾯试 … 还有其他⼀些公司，例如⼩⽶、华为、⽹易、美团、雅⻁、阿⾥、淘宝、腾讯等… 都对 PAT 的成绩以及能够给予的优惠有详细说明，具体企业联盟详情在官⽹的这⾥可以看到 https://www.patest.org/company 。⽐如我收到过百度、⽹易雷⽕的⾯试邀请邮件，还接到过⼀些企业的电话，但是由于当时我才⼤⼆⼤三没有打算找⼯作所以也就没有去参加⾯试… ⽽且我的个⼈简历⾥⾯也明确写了⽬前不打算找⼯作，所以打电话找我的企业不算多，不过身边有朋友通过PAT 进了⽹易，接到微软的⾯试邀请等～所以对于求职还是很有帮助的～⽽且身边很多考PAT 的都是⾮科班打算转计算机的，如果想要找计算机类的⼯作，考 PAT 通过企业联盟应聘确实是个可⾏的捷径～即使不是PAT 企业联盟中的企业，如果公司知道 PAT （我刚知道 PAT 时候 PAT 名⽓和影响⼒还很⼩，这些年逐渐扩⼤）对丰富简历or ⾯试应聘也是很有帮助的～ 刷PAT乙级和甲级需要掌握哪些知识 1. 官⽹对于 PAT ⼄级考试应具备的能⼒是这样描述的： 1. 基本的C/C++ 的代码设计能⼒，以及相关开发环境的基本调试技巧； 2. 理解并掌握最基本的数据存储结构，即：数组、链表； 3. 理解并熟练编程实现与基本数据结构相关的基础算法，包括递归、排序、查找等； 4. 能够分析算法的时间复杂度、空间复杂度和算法稳定性； 5. 具备问题抽象和建模的初步能⼒，并能够⽤所学⽅法解决实际问题。 概括来说⼄级的要求就是，⼀⻔编程语⾔ + 最基本的数据结构～ 2. 官⽹对于 PAT 甲级考试应具备的能⼒是这样描述的： 1. 具有充分的英⽂阅读理解能⼒； 2. 理解并掌握基础数据结构，包括：线性表、树、图； 3. 理解并熟练编程实现经典⾼级算法，包括哈希映射、并查集、最短路径、拓扑排序、关键路径、贪⼼、深度优先搜索、⼴度优先搜索、回溯剪枝等； 4. 具备较强的问题抽象和建模能⼒，能实现对复杂实际问题的模拟求解。 概括来说甲级的要求就是，在⼄级的基础上，能阅读英⽂题意 + 基础数据结构 + ⼀些经典算法～ 其实我们在准备 PAT 的过程中⽆需关⼼⼄级和甲级考察哪些知识点，因为⽬前 PAT 的题库中题⽬已经⾜够的多，以上知识点在题库中都已经完全涉及，我们只需要刷完题库、熟练掌握题库中的那些题型就能掌握到PAT 需要考察的所有知识点～甚⾄能根据题库中不同类型题⽬出现的频率推断常考的题型是哪些、复习的重点应该放在哪⽅⾯等（关于常考题型和复习重点我在下⽂会提及）～ 关于PAT刷题中编程语言选择和开发环境IDE选择的⼀些愚见 虽然 PAT 不规定编程语⾔，在刷题的时候也可以看到⽀持 31 种编译器，语⾔包括 C 、 C++ 、 Java 、 Python 、 Ruby 、 Go 、 JavaScript 、 PHP 等，但是根据考点提供的开发环 境可以看到，基本上只有⽀持 C/C++ 的 Dev-C++ 、 CodeBlocks 、 Visual Studio 、 VC++6.0 等，和⽀ 持 Java 的 Eclipse 、 NetBean 、 MyEclipse 等，少部分考场会有⽀持 Python 的 PyCharm …虽然之前 我在考场遇到过直接⽤记事本写 Python 代码的⼤佬（因为我当时的那个考场没有 Python 编译器）， 也可以直接通过⽹⻚OJ 提交看报错信息，然⽽如果要调试查看变量的值的话还是⾮常的不⽅便 … 所以 那些不是主流的语⾔应该很少会有⼈使⽤它们刷PAT 吧（毕竟不像 LeetCode ⼤家都是在⽹⻚上直接在线写代码提交），刷PAT ⽤的最多的编程语⾔还是 Java 和 C/C++ ，那关于 C 、 C++ 、 Java 如何选择呢？ C 语⾔作为⼀⻔⾯向过程语⾔，是很多计算机初学者必学的⼀⻔编程语⾔，绝⼤多数计算机系⼤⼀就会教C 语⾔，所以⼤多数⼈对 C 语⾔还是很熟悉的（不熟悉没学过也没有关系，书籍推荐部分我会讲到如何⾼效学习C 语⾔）～ C 语⾔也确实是⼀⻔执⾏效率⾼的语⾔，然⽽最⼤的缺陷是，它缺少⼀些必要的、封装好的、可以直接使⽤的数据结构，⽐如我们知道数据结构⾥⾯除了数组链表还有栈、队列、集合、映射等，做题的时候会需要⽤到这些数据结构，如果仅仅使⽤C 语⾔，可能需要⼿动⽤数组或者链表实现它再使⽤，⽽⼀些⽐C 语⾔⾼级的语⾔（这⾥的⾼级是指⾼度封装、对程序员更加友好）已经封装实现好了⼀些常⽤的数据结构，需要⽤的时候直接拿来⽤就可以～⽐如排序，使⽤C 语⾔可能要⼿写⼀个是冒泡排序或者快排，⽽更⾼级的语⾔已经封装好了为⾼效的排序算法，需要⽤的时候加个 #include 头⽂件然后直接⼀⾏ sort(begin(a), end(a)); 代码即可实现排序，这样能让我们在刷算法过程中把更多的精⼒集中在如何解决算法逻辑⽽⾮如何⽤语⾔实现⼀个常⽤的数据结构⽅⾯，⼤⼤提⾼做题的速度、降低代码的错误率～ 我知道⼤学计算机系或者想要做开发的必学 Java ，包括绝⼤多数⼈⾯向对象的⼊⻔语⾔也是 Java ，所以很多⼈就会想⽤ Java 刷算法，毕竟是将来⼯作和开发需要⽤到的语⾔～ Java 中确实有很多好⽤的集合框架封装好了各类常⽤数据结构，然⽽ Java 作为⼀⻔优秀的⼯程开发语⾔，在刷算法的时候却有些显得⼒不从⼼。我在刚刷算法的时候也是使⽤的 Java ，⼀开始 PAT ⼄级的题⽬还好，勉强只有⼏题⽆法AC ，都是因为运⾏超时 … ⽽刷甲级的时候就明显感觉出 Java 在运⾏时间⽅⾯的劣势了，有些题⽬连 C/C++ 都需要优化算法才能保证不超时，更何况⽤ Java … ⽽ PAT 对于同⼀道题⽬不同语⾔的时间限制要求是统⼀的，如果⽤ C/C++ 没有超时的题⽬⼀样的算法思路换了 Java 描述就超时了 … 岂 不是很⼼塞… （虽然官⽅说可以修改 Java 输⼊⽅式提⾼运⾏效率，然⽽我试过了，还是会有⼀些 30分的题⽬始终⽆法完全AC… ）如果你不介意不能在 PAT 甲级中获得⼀个满意的成绩，只是希望通过 PAT 题库来锻炼⾃⼰的代码能⼒和编程语⾔运⽤能⼒，倒是可以考虑全程使⽤ Java 刷题 … （当然我感觉如果单纯想提⾼代码能⼒和算法⽔平，刷LeetCode 会更节约时间）～如果执意想⽤ Java 学算法，⽽且是0 基础，可以参考下⽂从 0 基础到蓝桥杯省赛⼀等奖的⾼效学习路径 & 书籍推荐部分中关于 Java 组如何备考蓝桥杯的学习路径和参考书籍～ 接下来说 C++ 。可能对于没有接触过 C++ 的⼈来说这是⼀⻔陌⽣的语⾔，毕竟很多⼈对它的第⼀印 象是：这是⼀⻔全新的和⾯向过程的C语⾔完全不⼀样的⾯向对象编程语⾔，进⽽产⽣畏惧感，其实不然。下⾯是⼀段关于 C++ 的简介： C++ 是 C 语⾔的继承，它既可以进⾏ C 语⾔的过程化程序设计，⼜可以进⾏以抽象数据类型为特点的基于对象的程序设计，还可以进⾏以继承和多态为特点的⾯向对象的程序设计。C++ 擅⻓⾯向对象程序设计的同时，还可以进⾏基于过程的程序设计，因⽽C++ 就适应的问题规模⽽论，⼤⼩由之。 C++ 不仅拥有计算机⾼效运⾏的实⽤性特征，同时还致⼒于提⾼⼤规模程序的编程质量与程序设计 语⾔的问题描述能⼒。 所以说， C++ 是⼀⻔可以兼容 C 语⾔语法的⾯向对象语⾔。其实对于刷算法来说，它是否是⾯向对象语⾔并不重要，它关于⾯向对象的部分（继承封装多态之类）我们也可以完全不学习，⽽且对于已经懂C 语⾔的⼈来说，想要⽤ C++ 刷算法，⼏乎没有多少学习成本。也就是说，你完全可以在 C++ 的⽂件⾥⾯使⽤C 语⾔的语法，这不会产⽣报错。⽽那些好⽤的 C++ 特性⼜可以随意的使⽤，像是增强版功能的C 语⾔。对于刷算法来说， C++ 最⼤的好处是拥有 STL （标准模版库），就像 Java 的集合框架⼀样， C++ ⾥⾯封装了很多常⽤的数据结构，⽽只需掌握 STL 和 C++ 的⼀些和 C 语⾔稍有区别的基本语法，就完全可以使⽤ C++ 来刷 PAT 、 LeetCode 和蓝桥杯，这对算法之路是⼤有裨益的～下⾯是⼀段 关于 STL 的简介 STL 是 Standard Template Library （标准模板库）的简称，从根本上说， STL 是⼀些 “ 容器 ” 的集合， 这些“ 容器 ” 有 list ， vector ， set ， map 等， STL 也是算法和其他⼀些组件的集合。 STL 的⽬的是标准化 组件，这样就不⽤重新开发，可以使⽤现成的组件。STL 现在是 C++ 的⼀部分，因此不⽤安装额外的 库⽂件。 什么意思呢，⽐如说刷算法过程中需要⽤到集合 set ，我们知道 set 的特点是集合内的元素不重复（特别地，在 C++ ⾥⾯， set 是会⾃动排序的集合， unordered_set 是不会⾃动排序的集合），⽐如 在set ⾥分别放进 4 、 1 、 1 、 2 、 3 这⼏个元素， set ⾥会⾃动变成 1 、 2 、 3 、 4 ，如果我们只会 C 语⾔，可能需要⼀个个把数据放到数组⾥⾯，然后⼿动编写⼀些代码，检查进来的每⼀个元素在数组中是否已经存在，如果存在就不要再放进数组，最后对整个数组进⾏排序，才能达到set 的效果。但是如果直接使⽤ C++ ，我们就可以在头⽂件⾥⾯加个 #include ，然后直接把 set 当作⼀个类似于数组的容器，把所有元素直接丢到⾃⼰定义的这个set 类型的容器⾥，就会⾃动实现去重（去除重复元素）和排序的步骤～⽐如说题⽬要求将最后所有的答案去重后按从⼩到⼤的顺序输出，就可以直接将所有的答案元素放到set ⾥⾯输出即可～这样我们在刷题过程中就能更好地集中精⼒解决代码思路、算法⽅⾯的问题，⽽不是⼀个简单的答案输出或语法⽅⾯的问题，在考试过程中也能⼤⼤地节省时间，降低代码的错误率～ 更重要的是，使⽤ C++ 能写出更加精简的代码，简短的代码对于刷算法过程中思路的梳理和把握是⾮常有好处的～看过我blog 代码的⼈应该都会发现，我每道题的代码绝⼤多数都⽐简短，这并⾮是我 做完题⽬后将代码修修改改有意为之，你们所看到的代码就是我当时做这道题的过程中产⽣的代码，可能是因为曾经刷LeetCode 养成的好习惯，因为 LeetCode 评论区有很多优秀简洁的代码，我会不断地向他们学习，写代码过程中也会想好思路再写，写的过程中也会不断反问⾃⼰是不是⼀定要这么复杂，进⽽不断优化⾃⼰的思路。因为代码写⻓了就容易产⽣错误，更容易使⾃⼰思维混乱，⼀旦题⽬没能AC ，找 bug 和调试的过程也是⾮常地麻烦～⽽且我已经在 blog 上尽可能还原了当时写完题⽬后产⽣的代码原样，我不希望通过后期经过⼈⼯修改刻意简化的代码让很多初学者接触学习，这对初学者理解代码思路也是⼗分不利的。曾经 Github 上有很多⼤佬帮我优化过⼀些代码，我只接受了其中部分代码，如果我觉得这不是刚看到题⽬写代码时候就能想到的思路，就不会接受这段代码～本文转自柳婼大神！！！我是柳婼大神的小迷弟！！！ 若有侵权，会立刻删除，抱歉抱歉。 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |