/Leetcode2019

Leetcode practice with Python , Java and javascript

Primary LanguagePython

Leetcode Sharing

Index

刷題目的

刷題工具

個人推薦以下兩套不錯的刷題工具:

  • IDE (VS code 或 Pycharm)
  • Leetcode plugin
  • IDE(vscode, Jetbrain IDEs)
  • leetcode-cli

刷題的正確姿勢

  • 如何思考
  • 如何解題
  • 那些不該做的事

如何思考

  1. 從頭瀏覽一遍題目的敘述,了解Input和Output的Data Type和Data Structure,以及解法的限制條件。
  2. 限制條件可能是隱性的,利用題目給定的example和Input變數範圍決定解法,有時候暴力法也是一種可接受的解。

如何解題

  1. 規劃解題步驟,寫psuedo code或是流程圖。
  2. 寫下通解
  3. 處理通解無法覆蓋的corner case
  4. 優化以上兩個部份,直到submit通過
    p.s. 如果corner case的比重過高,需要從頭思考通解的寫法。

那些不該做的事

  1. 不要在同一道題上糾結過久,一道題目如果思考時間過長,代表對解法尚未掌握,應該把時間拿去學習解題的相關知識,而不是被困在同一道題上。
  2. 不要複製貼上別人的解法,或是看著別人的解法照搬不誤。很容易陷入能力錯覺的陷阱裡,寫完題你感覺已經熟練掌握了,其實還是一竅不通。你應該是看完別人的解法,間隔一段時間後再回來解題,重覆以上步驟,直到你不必看別人的詳解也能答題的時候才算徹底掌握。
  3. 不要只會最佳解。解題應當要能夠分析各種解法的利弊,了解演算法背後的原理,而不是死背硬套。
  4. 不要在解法裡頭用過多的程式去處理corner case,假如提供的解法老是有test case不通過,應該回頭審視解法的邏輯,而不是一直改code直到通過。

Leetcode題型分類

  • 數學
  • bit operation
  • Array&字串
  • 資料結構(Linked list & binary tree)
  • 演算法(Dynamic Programming& Graphic)

數學

許多經典的題目有公式解,例如求和1+2+...+n=n(n+1)/2,或是數學概念,例如給定三邊長判斷是否為合法的三角形,需要用到三角形的兩邊和必大於第三邊的概念。
Leetcode Easy的數學題目大部分是考觀念,而不是考程式能力,少部分的需要從基本的數學觀念延伸求解,數學類型的題目只能靠基本功和邏輯推理能力。

例題:給定一個有序的陣列,e.g.[1,1,2,3,4,4,5],請從陣列裡題找出三個可以組成三角形的數字,其具有最大週長。

bit operation 位運算

記住,計算機裡頭所有的資料都是以二位元的方式儲存的,因此位運算(and, or, xor, not)的速度會優於數學運算。
位運算的題型大致上有兩種,一是給定一個二位元表示的字串,此題型可以用遍歷的方式判斷每個位元是'1'或'0'後進行操作。第二種是直接給一個數字,要求你回傳該數定以二位元表示後的一些特徵。例如,數字n以二位元表示時有幾個1。

解題技巧

  • 目標函數(時間複雜度)
  • Traverse
  • Recursion
  • BFS & DFS
  • Dynamic programming

主旨

我們要做的其實只有兩件事:定位到我們要的元素,接著對該元素進行相關的操作,重複以上兩個步驟直到所有的元素都處理完畢。
當我們定位或是操作的步驟過於繁雜時,才需要考慮演算法或是數學來優化我們的處理過程。

目標函數

對於常見的資料結構(Array, List, binary tree etc),我們的目標是遍歷一次找出解,且不用額外的空間,時間複雜度是O(n)、空間複雜度是O(1)。
當時間複雜度達不到我們預期時,可以考慮用空間換時間的方式,例如時間複雜度O(n^2),我們可以試著讓它成為時間複雜度O(n),空間複雜度O(n)。
某些特殊情況,我們不需要處理全部的資料,可以透過部分操作得到我們要的結果,例如找出陣列中第k大的值,時間複雜度為logn。

刷題之後

  • 工作
  • 求職