从内建容器到善用资料结构特性

题组回顾与观念统整

在前三天的刷题实战中，我们一起完成了这三个经典的「基本」题：

• LeetCode 双刀流： 1. Two Sum
• LeetCode 双刀流： 412. FizzBuzz
• LeetCode 双刀流： 26. Remove Duplicates from Sorted Array

会用「基本」倒也不是说这是最简单的三个题目，而是这几题都是「只要会写程序的人都有机会可以实现」的问题。我会将这种等级的题目称为「基本题」，不需要额外的资料结构或演算法的技能，只需要有变数与流程控制（条件判断、回圈）操作的能力，基本上就可以解得出来的题目。不过「解得出来」跟「解得漂亮」中间还是有一些距离，而这个距离则需要有更多的经验与技巧的累积。以前三天的题目为例：

➤「Two Sum」

在「Two Sum」这一题从「方法 ①：双层回圈」直觉开始，尝试使用 JavaScript 物件（或 Python 字典）作为杂凑表（Hashmap）的技巧，利用空间换取时间的想法从双层回圈优化成一个回圈的「方法 ②：一层回圈 + 杂凑表」。最後，刻意导入了「方法 ③：半个回圈 + 双指针」的概念（虽然本题无法直接使用），不过对於回圈的操作添增一种新招式。

➤「FizzBuzz」

「FizzBuzz」虽然看似简单的但有许多细节值得深究，也是一个相当经典的题目。很多人看完描述之後，一定心想「这麽简单的题目，不就是条件判断吗？」，不过实际操作过「方法 ①：暴力法」、「方法 ②：字串组装」和「方法 ③：Hashing」，一定有一种意犹未尽的兴奋感。

➤「Remove Duplicates from Sorted Array」

第三个「Remove Duplicates from Sorted Array」则从重复（Duplicates）这个常见的应用着手，从同一个观念出发实现了「方法 ①：暴力法」和「方法 ②：双指针」，这两种方法中可以感受其实双指针跟暴力法并没有那麽遥远，有时候只是换个方向思考而已。而这一题的「方法 ③：其他资料结构」，想跟大家延伸的是可以利用「资料结构」的特性，透过型态间转换也能够达到去除重复的效果。

掌握程序内建的基本容器

什麽是资料结构（Data Structure）？「资料」是指由多个元素所组成的有限集合，这些元素的组合关系称为「结构」。实际上，资料数值是存放在电脑的记忆体中，当需要时才拿出来被 CPU 使用。而这些资料在使用时会被定义成一组抽象资料型态，让程序能够存取资料的方式就称为资料结构。

换句话说，就是「一组资料在程序当中的储存/组织方式」，有时候我们也会称为「容器（Collection/Container）」。不同的程序语言会内建提供一些常见的资料结构，例如在 JavaScript 提供「阵列（Array）」和「物件（Object）」、Python 则提供「列表（List）」和「字典（Dictionary）」。

阵列与列表

JavaScript 提供的「阵列」和 Python 提供的「列表」被我们视为是最基本的容器结构，他们都是「可改变元素内容的有序容器（mutual sequence）」。但根据资料结构书本上比较严谨的定义来说，阵列跟列表是不一样的，阵列是指由相同形态所组成的有序容器、但列表没有这个限制（因为 Python 本来就是弱型别的语言，选择列表也是很合理的）。

所以我们这样说，在 Python 中我们可利用「列表」做到其他语言「阵列」的工作，但实际上阵列跟列表是不一样的。顺带一提，虽然 Python 也有内建的阵列结构，但我们更常用的是 NumPy 中的 NdArray。

物件与字典

JavaScript 提供的「物件」和 Python 提供的「字典」是一种「无序且由 key-value pair 的元素所组成的容器」， 因为无序所以需要 key 来自定义顺序。这是一种很类似於 Hashmap 或 Hash Table（杂凑表）的资料结构严格来说底层实作有一点差别，不过使用上我们可以将物件与字典的 key-value 特性视为是一种运算上的 Hashmap。我们刚好在前三题都有利用到这个想法，使用 hash 暂存资讯，也就是我们常常说的利用空间换取时间的概念。

善用资料结构特性

最後想跟大家讲的是，除了「阵列与列表」、「物件与字典」这些基本的容器之外，在不同的程序语言也都有提供其他的资料结构可以使用，或是你可以利用现有的容器组装出不同的资料结构。我们在前几天用到的「Set（集合）」和「Map」就是，过去我们可能会强调逻辑运算的思维（也就是比较复杂的回圈跟判断），不过当你掌握不同语言提供的容器、善用资料结构特性也能够让你写出更精简更优化的程序码。

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

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