iT邦幫忙

2021 iThome 鐵人賽

DAY 26
2
Software Development

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

刷題後的歸納與淬鍊 - 常見的解題技巧「模板」

為什麼要刷題?

在經歷過了二十天左右的刷題練習經驗,我們從不同的題目中嘗試了各種有趣的程式題目。

回到我們這個鐵人賽的初衷,還記得為什麼要刷題嗎?

就如同我們前面所說,「程式設計」不只是程式語法而已,更重要的是能不能看得懂程式碼的技巧,並且理解程式中的運作原理。對程式設計的掌握可以分為幾個階段,從「寫得出」程式到「寫得好」程式,這是一個持續迭代的優化過程。對於程式邏輯不熟的尚未熟悉者,可以將 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 SumLeetCode 雙刀流: 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 擔任資料工程師,同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗,持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享,邀請你加入 訂閱 接收最新資訊。


上一篇
各式各樣的演算法 - Greedy、Dynamic Programming 與 Divide and Conquer
下一篇
除了刷題之外的事 - Software Engineering
系列文
LeetCode 雙刀流:Python x JavaScript30

尚未有邦友留言

立即登入留言