Leetcode 是什麼?誰需要刷題?必考題有哪些

什麼是 LeetCode?

LeetCode是一個專為程式設計師提供線上程式練習題的平台。它提供了一系列的挑戰題目和面試問題,涵蓋各種程式語言和電腦科學主題,如數據結構、演算法、設計模式等,並且每一個問題都附有詳細的解說,使得用戶能夠進一步了解如何解決問題。

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


LeetCode常見問題類型分析

LeetCode 的題庫內容有:

  • Algorithm
  • Database
  • Shell
  • Concurrency

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

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

在LeetCode上,您可以找到各種程式設計問題,涵蓋許多數據結構和演算法的重要概念。這些問題可以大致分為以下幾個類型:

  1. 陣列和字串:這些是最基本的問題類型,通常需要操作和管理數據集合。範例包括找出陣列中的最大值、找出字串的子字串、反轉字串等。
  2. 鏈結串列:這類問題通常涉及到節點的添加、刪除和尋找,或是反轉鏈結串列等操作。
  3. 堆疊和佇列:這些問題通常涉及到堆疊或佇列的特性,例如”先進先出”或”後進先出”等。
  4. 樹和圖:通常涉及深度優先搜索或廣度優先搜索,或是找尋最短路徑等。
  5. 演算法和設計:涉及複雜的問題解決策略,例如二分搜尋、動態規劃、回溯法或貪婪演算法等。

提到演算法

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

演算法對一個工程師的意義?如何提升實力?


誰需要刷LeetCode

其實刷 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,所以可以有效地壓縮搜尋時間。

轉職工程師不只要刷 leetcode,16 週進度班帶你半年轉職成功


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

因為工作上的需求,除了平常使用 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),記憶體方面則有負擔。


題外話

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

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

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


Leetcode 必考題有哪些?

LeetCode上的題目非常多,並且各大公司在面試過程中可能選擇的題目都不同,因此很難給出一個定量的“必考題”列表。然而,以下是一些常見且基礎的問題題型,這些題目涵蓋了許多基礎的演算法和數據結構,是很多公司面試中常出現的題型:

  1. 二元搜尋 BInary Search:”704. Binary Search” 是基本的二元搜尋題目。
  2. 排序 Sort:”215. Kth Largest Element in an Array” 是一題考查排序的題目。
  3. 深度優先搜索 Deep First Search:”200. Number of Islands” 是一題涉及DFS的問題。
  4. 廣度優先搜索 Breadth-First Search:”127. Word Ladder” 是一題BFS的典型題目。
  5. 動態規劃 Dynamic Programming:”70. Climbing Stairs” 是一個基本的動態規劃問題。
  6. 鏈表 LinkedList:”206. Reverse Linked List” 是一個基本的鏈表操作問題。
  7. 二元樹 BinaryTree:”104. Maximum Depth of Binary Tree” 是一題考查對二元樹理解的題目。
  8. 雜湊表 HashMap:”1. Two Sum” 是一題常見的使用HashMap來解決的問題。

這些都是基本且重要的題目,對於理解對應的數據結構和演算法非常有幫助。記住,練習LeetCode的目標不是為了背題,而是為了理解並熟悉各種數據結構和演算法,提升解題技巧和速度。


使用 ChatGPT 協助 Leetcode 解題

ChatGPT作為大規模語言模型,也能用來協助Leetcode解題,使用ChatGPT協助你解決LeetCode題目可以大幅提升解題效率和理解力。以下是一些建議,教你如何使用ChatGPT來協助解決LeetCode題目:

  1. 閱讀題目:首先,仔細閱讀LeetCode上的題目描述、範例和限制條件。確保你完全理解了題目的需求。
  2. 問問題:在ChatGPT中輸入你對題目的疑問,例如「如何使用二分搜尋法解決該題目?」或者「這個題目的時間複雜度是多少?」等。ChatGPT會根據你的問題提供相應的解答和解釋。
  3. 請求提示:如果你在解題過程中遇到困難,可以向ChatGPT請求提示。例如,你可以問「這個題目應該使用哪種數據結構?」或「哪個演算法最適合解決這個問題?」等。
  4. 演算法和數據結構學習:你可以向ChatGPT詢問某個演算法或數據結構的原理、使用場景和優缺點。這有助於你在解題過程中做出更明智的選擇。
  5. 檢查解答:如果你已經完成了題目的解答,可以將你的解答貼到ChatGPT中,請求評價和建議。例如,你可以問「這個解答的時間複雜度是多少?」或「這個解答有哪些可以優化的地方?」等。
  6. 參考答案:在嘗試過程中若仍無法解決問題,可以請求ChatGPT提供參考答案。這可以幫助你更好地理解題目和解題思路。
  7. 額外練習:你可以向ChatGPT詢問類似題目,以便加強你在特定主題上的練習。例如,你可以問「有哪些類似的動態規劃題目可以練習?」。

但同時也要小心ChatGPT可能會有錯誤的答案,仍然需要double check他的產出。


結語

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

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

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

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