iT邦幫忙

2021 iThome 鐵人賽

DAY 9
1
Software Development

LeetCode 雙刀流:Python x JavaScript系列 第 9

從內建容器到善用資料結構特性

題組回顧與觀念統整

在前三天的刷題實戰中,我們一起完成了這三個經典的「基本」題:

會用「基本」倒也不是說這是最簡單的三個題目,而是這幾題都是「只要會寫程式的人都有機會可以實現」的問題。我會將這種等級的題目稱為「基本題」,不需要額外的資料結構或演算法的技能,只需要有變數與流程控制(條件判斷、迴圈)操作的能力,基本上就可以解得出來的題目。不過「解得出來」跟「解得漂亮」中間還是有一些距離,而這個距離則需要有更多的經驗與技巧的累積。以前三天的題目為例:

➤「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 擔任資料工程師,同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗,持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享,邀請你加入 訂閱 接收最新資訊。


上一篇
LeetCode 雙刀流: 26. Remove Duplicates from Sorted Array
下一篇
LeetCode 雙刀流:206. Reverse Linked List
系列文
LeetCode 雙刀流:Python x JavaScript30

1 則留言

0

我要留言

立即登入留言