19. Remove Nth Node From End of List

 19. Remove Nth Node From End of List

難度: Medium

類型: Linked list, Two Pointers,

CPP程式下載: 19.cpp

前情題要:

移除從後面數過來第N個Node

思考方式:

因為是 Linked list, 要掃過一輪才知道是共有幾個Node。

1. 可以掃兩輪, 第二輪就知道要移除的那個 Node, 把它前一個 Node 的 next 指向下一個Node 即可。

2. 因為我看到總共最大不超過30個Node, 那我直接把每個Node的位置都存起來, 就不必跑第二輪。花記憶體空間, 但較快。不過因為一輪最多也才30次, 應該差別也不大, 反而比較浪費記憶體空間。不過已經寫完就算了。

複雜度思考:

Time Complexity: O( N ) 

Space Complexity: O( N*sizeof(ListNode* )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 14.97 MB, Beats: 59.51%

17. Letter Combinations of a Phone Number

 17. Letter Combinations of a Phone Number

難度: Medium

類型: Table, String, Backtracking

CPP程式下載: 17.cpp

前情題要:

就如傳統按鍵手機把數字轉成英文字母

思考方式:

因為最多只按四下, 最多不過 4^4=256 次, 簡單寫就好。

複雜度思考:

Time Complexity: O( 4^4 ) 

Space Complexity: O( 1 )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 8.96 MB, Beats: 95.04%

16. 3Sum Closest

 16. 3Sum Closest

難度: Medium

類型: Array, Two Pointers, Sorting

CPP程式下載: 16.cpp

前情題要:

三個數字加起來最接近 target

思考方式:

1. Vector 先排序

2. 用 2Sum 的 left, right, 再加上最左邊的數字index i。

3. 如果目前的 index i 和下一個 index (i+1), 對應到的nums值是相同的時候, i=i+1 這次的計算可以跳過, 因為前一個 i 就已經算過所有可能的答案了。

複雜度思考:

Time Complexity: O( (N-2)*(N-2) ) 

Space Complexity: O( 1 )

結果:

Runtime: 3 ms, Beats: 98.17%

Memory: 13.96 MB, Beats: 61.72%

15. 3Sum

 15. 3Sum

難度: Medium

類型: Array, Two Pointers, Sorting

CPP程式下載: 15.cpp

前情題要:

任三個數字加起來等於0

思考方式:

1. Vector 先排序

2. 用 2Sum 的 left, right, 再加上最左邊的數字index i。

3. 找到對的組合時, 填進 Set。(Set 會判斷是否唯一)

4. 把 Set 用 Vector.assign(set.begin(), set.end()) 的方式轉成 Vector 再 return。

5. 雖然沒在前段班(50.95%花49ms), 但也相差不遠。就先優化到這就夠了。

複雜度思考:

Time Complexity: O( (N-2)*(N-2) ) 

Space Complexity: O( 1 )

結果:

Runtime: 107 ms, Beats: 21.32%

Memory: 34.62 MB, Beats: 22.29%

18. 4Sum

 18. 4Sum

難度: Medium

類型: Array, Two Pointers, Sorting

CPP程式下載: 18_1.cpp 18_2.cpp

前情題要:

四個數字加總起來等於 target

思考方式:

1. Vector 先排序

2. 用 2Sum 的 left (n2), right (n3), 再加上頭尾 (n1, n4)。

3. 找到對的組合時, 填進 Set。(Set 會判斷是否唯一)

4. 把 Set 用 Vector.assign(set.begin(), set.end()) 的方式轉成 Vector 再 return。

5. 18_1.cpp 的 n1與n4迴圈, 並沒有優化, 花的時間是 200ms 上下。如果如18_2.cpp 連續抓四個值的和來判斷迴圈是否需要繼續或結束, 花的時間降到41ms多一些。雖然沒在前段班(15.34%花7ms, 64.37%花23ms), 但也相差不遠。就先優化到這就夠了。

複雜度思考:

Time Complexity: O( (N-3)*(N-3)*(N-3) ) 

Space Complexity: O( 1 )

結果:

Runtime: 41 ms, Beats: 17.95%

Memory: 25.13 MB, Beats: 15.61%

14. Longest Common Prefix

 14. Longest Common Prefix

難度: Easy

類型: String, Trie

CPP程式下載: 14.cpp

前情題要:

判斷Vector String 中最長相同的開頭字串。

思考方式:

這題很簡單, 只是要留意, 如果 Vector 中只有一個字串的情況。

複雜度思考:

Time Complexity: O( N*min_string_length ) 

Space Complexity: O( N*sizeof(int) )

註: N 是 vector 中的字串個數

結果:

Runtime: 0 ms, Beats: 100%

Memory: 11.58 MB, Beats: 99.65%

11. Container With Most Water

 11. Container With Most Water

難度: Medium

類型: String, Two Pointers, Greedy,

Python3 程式下載: 11_1.py 11_2.py

前情題要:

容納最多水的容器。 左右個一個桿子, 較矮的那個桿子高度, 乗上兩個桿子的距離, 就是能容納的水量。

思考方式:

這題沒想到好方法前一直Time Limit Exceeded, 想到方法後就很簡單。Two Pointers, 一個在最左, 一個在最右, 然後算出容積。如果哪邊桿子比較矮, 就把那邊的桿子向中間移動, 尋找更高的桿子。如果兩邊一樣高, 就一起往內找更高的桿子。

1. 用python寫, 純粹是誤以為線上面試要改用python。後來確認後, 其他題又改回 C++ 來 coding 了。

2. 11_1.py, 跟 11_2.py 剛好可以拿來對比。11_1.py 一次向內移動一格, 而 11_2.py 是往內移動到更高的桿子為止。時間上從 11_1.py 花費 39ms, 進步到 11_2.py 花費 25ms。但我覺得差異不大。

複雜度思考:

Time Complexity: O( list length n ) 

Space Complexity: O( 1 )

結果:

Runtime: 25 ms, Beats: 98.01%

Memory: 24.51 MB, Beats: 24.01%