[LeetCode] 增強自我能力檢視表

我這邊列了一下前陣子幾個自己從寫LeetCode練習中,發現不管面試FAAG,或一些不錯的公司,或是工作上的應用都很重要的觀念,大家可以參考當作檢視自己寫程式的過程,不斷突破自己的簡單檢查表。

我寫的題目很少(目前總共301題,150 medium, 120 easy, 31 hard),所以之後也許會繼續增加筆記吧(欸)

Image for post
Image for post

只是每一題都能學到蠻多東西,很多知識都容易讓我想到以前工作上的某些project (●▼●;)

1.有些情境,recursive比iterative省空間。

例如你要traverse一個樹狀結構時,recursive的空間複雜度是O(H),iterative則是那一個level的node數目,也就是O(2^H),H是樹高。

2.Binary Search tree vs. binary tree,兩個是完全不同的東西。

在練習tree traversal系列題目時候,你分析時間複雜度時,自己要記得。
因為時間複雜度,一個是O(n),一個是O(H)。

3.在寫tree traversal或2條linked list時候的null判斷寫法

以前我都會寫

if (left == null && right == null)

練習幾題後發現,其實你可以寫成

 if (left == right)

4.array跟map,都可以做成key-value的map資料結構概念,但如果你能知道資料量大小,宣告成array,在做add/get時候,速度會比宣告成map快很多。

因為HashMap在新增element時候,如果到達threshold,會開始「rehashing」,底層會new一個空間更大的HashMap,把現有的copy過去,這會花掉不少時間,也是為何面對比較大的資料量時,資料結構使用array,在最後整體效能上,速度會比較快。

5.ArrayList set, get, isEmpty are all O(1)

6.For both LinkedList & ArrayList,”clear” is O(n), so it will be faster to re-initialize the data structure

ex.

res = new ArrayList<>();

rather than

res.clear();

7.List to String array 的轉換方式

List<String> res = new ArrayList<>();res.toArray(new String[res.size()]);

8.當你用HashMap,並將value部分宣告成Integer,應用Integer拿取而非int。

例如HashMap<String, Integer>,應該避免這個錯誤拿取方式

int i = map.get(key)

這是在某些case才會出現的error,算是running time error。

Because int cannot be compared with null, you should use Integer

Integer i = map.get(key)

Then you can do this

if ( i != null) …

9.HashSet可以直接轉成ArrayList

例如

HashSet<String> set = new HashSet<String>();set.add("Hi");new ArrayList<String>(set);

這篇就寫到這,觀念重點就是

1.你的程式隨時都要有人能接手,寫程式的獨立性,或是能把它寫成library …等等,這都是基本砥礪自己的觀念。

2.LeetCode討論區的code,不見得全部都寫得很漂亮,或是具有所謂獨立性,自己要能分辨出來。

3.程式上時間空間複雜度的取捨,應用到工作上就是效能的考量。

4.很多東西不見得工作上用不到,記得面試的當時,我recursive解法雖然能解出來很多題目,但寫的還不是很快……可像我現在的公司,跟上一間公司,寫的project都會用到recursive。

以上這些也都是在面試FAAG,還有其他不錯的公司時候,有些我應用到的觀念,工作上現在也蠻常在應用的。

分享出來給大家當參考,每過一段時間拿出來檢視一下自己能力,也許可以當作improvement check list吧 (〃∀〃)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store