Loading...

什麼是 LeetCode?

隨著大資工時代的到來,越來越多人憑藉著非大學課程的訓練,自己練出軟體世界的基本功,尤其以網路開發為主。工程師本身的起薪高,容易吸引到大量的人才投入。當好的職缺出現在求職市場時,眾多求職者將湧入其中爭取面試機會,企業使用履歷進行篩選之外,會考驗應徵者的基本開發能力以及專案經歷。前者常見的測試方式為白板題與線上題庫測驗;後者則看求職者的作品集來了解。而 LeetCode 便是常見了解題目的手段,其記錄各式各樣的題目好讓求職者有個底。

LeetCode 的題庫內容有:

  • Algorithm
  • Database
  • Shell
  • Concurrency

最常見的以演算法為主,這次的系列將著重於此。

說穿了,刷 LeetCode 好比學生時代刷題庫,目的是熟悉題型好應對各式各樣的基本題與變形題。目的只有一個,面試中遇到的技術問題可以順利通過。

提到演算法

自然而然會連結到資料結構。深入來看,演算法是基於不同類型的資料結構開發出來的,即使是不同的資料結構,基本的 CRUD 功能是必要的,而演算法便是思索如何改善 CRUD 的速度。因此,往後在工作上面對不同的需求時,使用較符合需求的資料結構,再搭配適合該結構的演算法,便能有效提升計算速度。

題外話

其實刷 LeetCode 的需求,往往有幾種背景需要練習:

  • 學習過大學資料結構與演算法課程的學生。
  • 想要進入大公司的求職者。
  • 想要學習新語言特性的學習者。

題庫刷得再多也要記得,專案的能力也要一併培養。刷很多題庫卻沒有規劃專案的能力,往往是致命的,因為題庫的能力可以藉由反覆練習獲得,規劃專案的能力卻不太能藉由反覆練習取得,因此不少資深職缺會希望求職者擁有好的專案經驗。

個人背景

我不是大專院校資訊相關科系出身,自然沒有接觸過演算法與資料結構。學習過程以網頁開發為起點,學習 HTML、CSS、JavaScript,後續在公司的專案上接觸到 Java 與 C,整個過程由簡入難。

說實在的,沒有接觸到靜態語言前,覺得全世界都用 JS 開發是件多美好的事情。隨著經驗的累積後,慢慢了解每種語言因為獨特的能力而有存在的必要性。

  • 學習 Java 才瞭解靜態語言與物件導向的美。
  • 學習 C 才了解 JS 好用的內建函式,不一定是效能的最佳選擇,以及 By Value & By Reference 的由來。

可見的,這系列的內容將傾向個人學習資料結構與演算法的筆記心得,力求口吻平易近人,往後自己複習時可以輕鬆讀懂、他人閱讀時也能輕鬆閱讀。

我會怎麼寫?

順序是這樣的:

  • 介紹 LeetCode 與一些基本刷題知識
  • 介紹資料結構的特性。
  • 列入在 LeetCode Tag 內的資料結構優先討論。
  • 嘗試用 JS、Java、C 各解一次,目的是增進三種語言的熟練度。
  • 演算法用來輔助資料結構。

因為我最熟悉的語言是 JS,所以相關的術語概念將以 JS 為主。

刷 LeetCode 該有的基本知識

如果什麼都沒準備,以 Two Sum 來說

這邊聽我娓娓道來第一次使用 LeetCode 的情境:

註冊 LeetCode 帳號成功、點選 Problems 後,印入眼簾的是一千多題,不懂門路的我,想說過往寫題目都從第一題開始,而且難度標注是 Easy,應該是沒問題可以順利解決,於是點擊 Tow Sum

題目的內容是這樣:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
Example 1

菜雞的我,想一下後認為使用兩個 for loop 就能處理了。所以我寫出這樣的程式碼:

開心地按下 Submit 後,得到

當下只有無限的問號在我腦中,奇怪,這樣做不對嗎?

重新來一遍,會如何分析 Two Sum

首先要仔細閱讀已知的資訊,除了閱讀題目本身的描述外,點擊 Related Topics 後會看到 Array & Hash Table。對於菜雞來說,關於如何操作 Array 有個基本的概念,但是 Hash Table 就不太理解,於是找尋 Hash Table 的相關資訊,大致上有概念後,會陷入一個窘境,如何實作?

想了 20 分鐘後仍然沒頭緒,直接找答案。了解 Hash 除了常用於密碼學上,也可以應用在其他情境。在參考解答後寫了 JS 的版本:

說實在的,看答案後重新寫出來並不可恥,重點是學習這個問題背後要測試的技術是什麼,這邊只使用一次 for loop,每次進行判斷與製作 Hash Table,所以可以有效地壓縮搜尋時間。

完成基本功的我想要增加其他訓練

因為工作上的需求,除了平常使用 JS 開發之外,有時需要接觸 Java 與 C。趁這個機會同一題用三種語言寫寫看,藉此了解三個語言不同之處。

Java

可以看出,這題因為需要的觀念是 Array 與 Hash Table,JS 與 Java 在這部分的幾乎類似,因此程式碼十分相近。

C

直覺作答,使用兩個 for-loop

參考 Submission 後嘗試製作 Hash Table


我得承認,C 的處理方式跟上面兩個語言非常不同。撰寫過程中因為不了解只好再去找一次解答,了解更多 C 的相關運用。

這邊看到幾個版本:

  • 直接使用 for-loop 解題,玩味的地方在於 C 不會出現 Runtime Error。
  • 使用 struct 模擬 JS & Java 的物件好製作 Hash Table,接著使用 two pointer 的找尋答案。
  • 不使用 struct,而是用 Array 模擬物件製作 Hash Table,再用 for-loop 一個一個找尋。

C 實在是太有趣了,同一題居然有多種寫法,而且執行的結果跟 JS 有不小的差距。

從不能用暴力解(Brute Force)這件事來看,LeetCode 希望大家寫出有效率的運作模式。而有效率到底該怎麼判斷?

Leetcode 如何測量效率

在我還是個剛轉職成功,沒有實際接觸過複雜專案的菜雞時期,面對新功能的開發,心態上保持著 先求有再求好,寫出許許多多用了不同內建函式、自訂函式的程式碼。新功能當然是順利開發成功,為此感到十分開心。這時候的我,對於能完成新功能開發的自己,感到十分得意。

工作經驗增加後,有機會碰到公司內較複雜的專案,藉此打開我的眼界,程式碼的部分沒有毫無章法的寫法,反倒是有一定規律的做法(現在的我知道這是 Design Pattern),當時我負責接觸的部分是效能優化的部分,這時候才感覺到沒有思考每種資料結構特性,胡亂使用順眼的函式執行,是一件多麽可怕的事情。

回憶結束。

關於程式碼的效率,可以從兩個角度來思考:

  • 執行速度可以多快?
  • 執行時期記憶體使用量有多少?

菜雞時期接觸的專案,鮮少有大數量(萬筆以上)的資料庫,或是每天接受的 Request 數量到達幾十萬甚至是幾百萬。因此在處理資料上都是小數量為主,任何的函式在執行上看不太出來效率的差異。但是,真實世界,尤其是開發逐漸上軌道的產品,不可能面對小數量,而是讓人無法有人平估的大數量。是否善用資料結構與演算法來優化產品的邏輯運算,在這個時候就派上用場了。當然,除了優化處理效率外,還有許多跟部署有關的技術可以優化大數量的 Request,這不在本文討論的範圍內。

回到主題,判斷執行速度與記憶體的使用,可以這樣理解:

時間複雜度,Time Complexity

強調需要執行的次數。

專業上的講法會提到測量方式、測試次數的加總以及如何用 Big O 表達,個人傾向簡單講解,面對一組資料,用 for-loop 執行嗎?假如面對多組資料,能避開巢狀 for-loop 嗎?有想過在 for-loop 調整執行的內容,好減少執行的次數。

空間複雜度,Space Complexity

強調變數的使用量。

專業上的講法會提到執行時要佔用的記憶體空間,個人傾向簡單講解,面對一組資料,是否要額外宣告變數來處理?變數的數量可以控制嗎?

two sum 這題該怎麼看待

暴力解

時間複雜度的部分,第一個迴圈,陣列內每一個項目都要被執行一遍,所以執行次數是 nums.length,在分析時習慣用 N 表達。針對陣列內每一個項目,會需要第二個迴圈,執行次數是 nums.length - 1,分析用 N-1 表達。

因此這題的時間複雜度是:

空間複雜度方面,沒有額外宣告任何變數。

因此,暴力解在執行時間方面會是 O(N^2),記憶體方面幾乎沒有大負擔。

使用 Hash Table

時間複雜度的部分,僅僅只有一個迴圈,執行次數是 nums.length。

因此這題的時間複雜度是:O(N)。

空間複雜度方面,額外宣告 Hash Table,隨著 N 的數量增長,Hash Table 內的資料量將跟著成長。

因此,Hash Table 在執行時間方面會是 O(N),記憶體方面則有負擔。

題外話

Imgur

這題嘗試用不同語言撰寫,有趣的地方在於,我直覺認為靜態語言就是比動態語言快速,殊不知 C# 賞我一巴掌,而記憶體的使用方面,Java 與 C# 也賞我兩巴賞。這邊有幾點可以推論:

  • 這題的寫法,在記憶體的存取方面,對於 Java 與 C# 有比較大的負擔。
  • LeetCode 官方的模擬環境,與我認知的不太一樣。
  • Golang 出人意料的快速,怪不得 Google 自誇是 21 世紀的 C 語言。

就我個人經驗而言,撰寫 JS 與 Java 的時候幾乎沒在管記憶體,追求的只有更高的效率。直到接觸用 C 開發的機器,被 free 給嚇到,給我一個機會省思過度宣告變數的好壞。

結語

任何專業領域都一定有測不準原理的窘境,在程式設計的便是記憶體與時間的抉擇。拜摩爾定律協助半導體產業的發展,記憶體朝向大儲存量與低廉價格發展,使得空間複雜度變成次要,時間複雜度成為主要關注的重點。最典型的運用便是各式各樣的網頁,使用者不能忍受3秒以上的等待,於是瀏覽器們著重在使用記憶體,好帶給使用者快速的體驗。

那有著重空間複雜度的場合嗎?有的,在部分伺服器、嵌入式系統等,提供的是有限的記憶體,此時該思考如何在有限的記憶體下,爭取到多少時間?

當然,目前各大公司提到演算法時,仍舊著重在時間複雜度,記憶體的問題在特定產業才有可能遇到,因此,寫出能夠快速執行的程式碼幾乎是各大公司要求的基本功。

(本文作者是AC助教Victor,轉載自他的鐵人賽系列文 你總是躲不掉的,不如放膽面對 LeetCode 吧)

非本科生也想做LeetCode特訓?八週密集練功建立內化能力

成為企業渴求的程式人才!

在家學會 JavaScript 網路開發

全新「全端 Web App 開發」課程,給你看得見的學習成效!
超過 90% 轉職成功,400 位來自亞洲各國的 ALPHA Camp 校友,畢業後達成轉職、創業、出國工作的夢想!

3 分鐘選課指南

給期待創新改變的你

前端x後端x全端 完整工程師技能樹

90% 學生轉職成功,職涯競爭力更上層樓
最專業的「全端 Web App 開發」課程,上班族邊工作也能同時培養第二專長!

3 分鐘選課指南

學期一|程式設計入門

零基礎也學得會的程式入門課!

開始學帶得走的技能,為自己未來的成長鋪路

學期二|掌握網頁開發

系統化學習 JavaScript

實作打好前後端基礎,成為扎實的網頁開發者

學期三|軟體工程師養成

養成業界接軌的實戰能力

前端/全端工程師專修路徑,完成技能與求職準備,成為業界即戰力