刷题後的归纳与淬链 - 常见的解题技巧「模板」

为什麽要刷题？

在经历过了二十天左右的刷题练习经验，我们从不同的题目中尝试了各种有趣的程序题目。

回到我们这个铁人赛的初衷，还记得为什麽要刷题吗？

就如同我们前面所说，「程序设计」不只是程序语法而已，更重要的是能不能看得懂程序码的技巧，并且理解程序中的运作原理。对程序设计的掌握可以分为几个阶段，从「写得出」程序到「写得好」程序，这是一个持续迭代的优化过程。对於程序逻辑不熟的尚未熟悉者，可以将 LeetCode 刷题作为是第一阶段的入门砖。但如果是已经有一点程序经验的人，可以将 LeetCode 刷题视为持续锻链程序能力的题库。总之，我自己觉得写出会动程序不难，但要把程序写好非常难。追逐程序实作技巧也许短期内会觉得很刻意，但立志写出一个精简高效的程序才是身为一个工程师该有的浪漫。

写程序不只是学习程序语法，更需要搭配实作练习

那究竟该如何持续锻链程序的技巧，找资料结构或演算法的理论课或是书来读就好了吗？

理论课其实也是从各种经验跟问题所归纳出来的方法，所以理论课其实就是在教你各种手法跟操作（很多时候很抽象），就像你学习的数学时候会背公式那样。但更重要的其实是观念是如何建构，以及应该如何活用於题目当中，这才是解题/刷题过程中逐渐养成的。刷题的重点来源培养解题的手感，如何把从问题中使用正确的手法。刷几题才够其实是一个假议题，当然是刷越多越好啊（但现实是没有时间）。所以我会建议不要盲目地刷题，应该思考如何有系统的解题，从一个题目当中尽可能尝试练习到不同的思考角度，培养思考问题的广度。

刷题的四个阶段

完成一个题目之後，请先透过结果的时间花费与空间占用恒量自己该程序写得好不好。我们在前几天有说刷题过程中，「如何最大化一个题目的效益」也是刷题过程中重要的关键。比起盲目的刷题之外，如何从一个尽可能地持续迭代、持续优化并且思考沈淀，让你从一个题目掌握到更深更广的效益。因此提交一个正确解答之後，你要做的并不是马上就解下一题，而是思考与沈淀之下，然後尝试优化的策略。进入「一个题目」的解题过程时，可以分成「#动手之前先思考 → #初探直觉解 → #刻意优化 → #举一反三」几个阶段的优化过程。

资料结构与演算法

资料结构这一门学科专注在如何利用一些抽象的结构有效在程序中储存资料，换句话说，就是在讨论怎样更好的使用变数的方法。演算法的话则是搜集那些经典的方法，介绍那些常见的问题过去是如何设计出漂亮的方法来解决的，也可以视为是一种流程上的优化。所以，其实资料结构与演算法就是写程序，资料结构或演算法其实就是程序码经年累月淬炼出的精华，经过整理而成的武功秘笈，让我们得以站在巨人的肩膀上写出更好的程序码。

常见的资料结构

资料结构（Data Structure）是指「资料」是指由多个元素所组成的有限集合，这些元素的组合关系称为「结构」。换句话说，就是「一组资料在程序当中的储存/组织方式」，有时候我们也会称为「容器（Collection/Container）」。以下列出一些经典常见的资料结构：

▣ String、Array、Object
▣ Map、Set
▣ Linked-List
▣ Stacks、Queues
▣ Tree and Graph
▣ Hash Table

除了使用内建的阵列或物件之外，我们也可以利用内建物件拼凑出其他的资料型态，称为抽象资料结构。这里的抽象指的是「不管内部怎麽实作，只要可以符合指定的操作的特性」就可以称为是资料结构。资料结构目的是提升「空间」复杂度，让你更有效率地把资料存到电脑里，这里的「效率」指的是节省空间。

常见的演算法

演算法是在程序中解决问题的流程控制，更精准一点来说是指「在 有限时间与步骤 内，按部就班完成特定功能的有限个指令所组成的程序码」，而有两个重要的特性需要依循：

• 依序的指令集合（Ordered set）：依序且定义明确的指令集合，程序能够依序执行
• 明确的步骤（Unambiguous steps）：每个步骤定义清楚明确，过程可以被 SOP 化

换句话说，演算法的话则是整理那些经典的解题方法，以下是常见的算法：

▣ Search、Sort
▣ Recursion
▣ Backtracking
▣ Greedy
▣ Divide and Conquer
▣ Dynamic Programming

演算法的目的在於提升「时间」复杂度。一般的「流程控制」是透过条件和回圈定义程序的运作，而演算法则是更有效率地控制程序流程。

解题关键字与常见技巧

不过除了常见的资料结构跟演算法之外，在面临 LeetCode 的题目或是真实世界常见的算法问题时，也会有一些「额外」 的解题技巧。前面谈到的资料结构和演算法「经典理论」，能够建立系统性的方法论，对於解法能有一个全局观。不过实际上在解题时，会根据不同的情境产生很多零碎的「解题技巧」，他们也是广义的资料结构/演算法的一部分，可是被视为一种解题策略。

Hash Table

杂凑表（Hash Table）是一种自定义位置的资料结构，每个元素都会有一组（key-value）的结构所组成。在解题过程中，我们常用 Python 中的 dictionary 或是 JavaScript 中的 Object 来模拟 Hash Table 的行为。

Two Pointer

第二种常见的技巧是「Two Pointer」，我们在 LeetCode 双刀流： 1. Two Sum 和 LeetCode 双刀流： 26. Remove Duplicates from Sorted Array 有使用到，能够透过自己的指针搭配回圈，让回圈产生多重的效果。常见的方式可以从左右两端指定索引往中间移动，也有从头开始往同个方向移动的快慢指针变型用法。

这张图的来源自 Two Pointers-Eugene and an Array ，内文也有很清楚的双指针用法。

Sliding window

Sliding window 用於找出某一个区间或一个连续范围是某满足条件的情境，类似於我们解过的 LeetCode 双刀流：53. Maximum Subarray 这一题，通常会搭配动态规划的方法来暂存资料。概念上类似下图，更细节的操作 algorithm-patterns 内容。

Traversal

遍历是树（Tree）特性的一种延伸操作，不同於线性的搜寻，因为每一个节点可能会有左/右分支，因此有不同的先後顺序找法。因此会有「要先找左边还是右边」、「要找到最底还是先把周围的找完」等等的衍生议题，而不同的找法有时候可以搭配资料结构的特性来使用。常见的遍历方法可以分为「前序」、「中序」跟「後序」，依据 Root 被找到的先後做排序。

但是必须特别强调，在刷题练习的过程时这些技巧很有可能会被当成一种「速解法」，很容易被误会成「某种题型的套路解」，反而失去的持续优化的刷题体验与乐趣。

嗨，大家好！我是维元，一名擅长网站开发与资料科学的双栖工程师，斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。