33. Search in Rotated Sorted Array

 33. Search in Rotated Sorted Array

難度: Medium

類型: Array, Binary Search

CPP程式下載: 33.cpp

前情題要:

在一個旋轉移動過原本小到大排序的陣列中, 尋找一個target數字。

思考方式:

這題也是, 想到方法就簡單, 沒想到方法就會超時。方法不好想, 但是容易看得懂。

1. 原本的陣列是小到大排序過的, 所以每個數字的右邊都是比較大的數或是0。

2. 用 binary search 比較快, 如果陣列的中間那個值比最左邊的值大, 代表他在上升序列中, 最大值和0都在他的右邊。這時候如果 target 值在中間那個和最左邊值的中間, 那就看左邊的序列就好。反之就看右邊的序列。

3. 如果中間的那個值比左邊小, 代表最大值和0都在中間那個數字的左邊。如果target小於最右邊的值, 但大於中間那個數字, 則代表target值要位於中間偏右, 反之則在左半側。

4. 一直縮小一半, 直到找到 target 的值或是已經夾擊找到最後一個值都不等於 target。

複雜度思考:

Time Complexity: O( log2(N) ) 

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 10.10 MB, Beats: 66.35%

29. Divide Two Integers

 29. Divide Two Integers

難度: Medium

類型: Math, Bit Manipulation

CPP程式下載: 29.cpp

前情題要:

兩個整數的除法, 但不能用到乘法與餘數(Mod)的運算。

思考方式:

如果知道方法的話, 這一題很簡單, 只要小心處理正負與極值就好。

1. 先判斷除數和被除數的正負, 之後就知道商的正負號。後面就都用正整數做除法。

2. 把十進位的除法改為二進位的除法就好。先把除數一直乘二直到最大但不大過被除數。然後兩個數字相減, 得到餘數。餘數再和除數退一位(bit)再比較, 大於就相減,然後商多1。最後的商也是二進位。就轉成10進位就可以了。

3. 處理商的極值若超過2^31, 就改為2^31 (正負都是)。

複雜度思考:

Time Complexity: O( 2*31 ) (最多)

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 8.48 MB, Beats: 96.80%

22. Generate Parentheses

 22. Generate Parentheses

難度: Medium

類型: String, Dynamic Programming, Backtracking

CPP程式下載: 22.cpp

前情題要:

列出所有N 個括弧的可能組合

思考方式:

1. 利用 Set 的唯一性, 我們就不避自己實作比對的程式。把所有可能的組合往裡面丟就好。

2. 給一組括弧當開始。

    兩組括弧就是在字串最左邊加上"()", 找到第一個"("之後加上"()", 最後在字串最右邊加上"()‧‧。

    三組括弧就是在字串最左邊加上"()", 找到第一個"("之後加上"()", 找到第二個"("之後加上"()", 最後在字串最右邊加上"()‧‧。

    後面以此類推

3. 最後記得把Set的每個 string, 都存到 vector <string> 中。

複雜度思考:

Time Complexity: O( N+(N-1)+....+2 ) 

Space Complexity: O( x )

結果:

Runtime: 3 ms, Beats: 71.36%

Memory: 11.29 MB, Beats: 96.48%

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%

10. Regular Expression Matching

 10. Regular Expression Matching

難度: Hard

類型: String, Dynamic Programming, Recursion

CPP程式下載: 10_1.cpp 10_2.cpp 10_3.cpp 10_4.cpp

前情題要:

一個 source string, 一個 pattern string, 規則如下:

'．': 代表任一字元

'＊': 代表 0個到多個前一個字元。

如果 source string 可以符合 pattern string 的規則, 就回傳 true, 反之則回傳 false。

思考方式:

1. 這邊的’＊’, 與原本認知的"0個到多個任意符號", 並不相同。注意, 是"0個到多個的前一個符號"。譬如 "r*", 就是0到多個r。譬如 ".*" 才是0到多個任意符號。如果這邊沒有注意到, 會多走很多冤枉路。

2. 10_1.cpp 跟 10_2.cpp, 是不同時間寫出來的, 基本上 10_1.cpp 好一點點。10_2.cpp 是先找到 '*' 再回推, 所以計算上會稍稍多走一點冤枉路。不過差不太多, 10_1.cpp 最快花費869ms, 空間約10.2MB; 10_2.cpp 最快花費963ms, 空間約9.4MB。

3. 後來我發現 "isMatch(s.substr(j), p.substr(i+1))" 上。首先 substr 是會複製一個 string 出來, 而 isMatch 的輸入string, 是傳 string 實體, 而不是傳位置, 這代表每次 recursion 呼叫一次, 就複製一個新的 string 然後進到函數前再被複製一次。然而很多次 recursion 的呼叫累積下來, 浪費了很多時間。這邊要改。

4. 10_3.cpp 就是改了recusion 呼叫的函數, 改成傳 array pointer。很明顯的, 從結果來看, 時間上的花費從 869~1100ms 降到了526~550ms, 而空間上的花費從9.4MB降到了7.9MB~8.1MB。

5. 10_4.cpp, 與10_3.cpp相比則是優化了流程, 一邊找 '*' 的同時, 也一邊比較第 i-1或i-2 位置之前的char* p 與 char* s。這邊可以看到時間上優化有限, 進步到507~519ms, 而空間上沒差別, 也是 7.9MB~8.1MB。

到這邊先告一段落, 再來進步有限。有更好的方法歡迎留言討論~

複雜度思考:

Time: O ( N! )

Memory: O ((M+N+2)*sizeof(char))

結果:

636 / 636 testcases passed

Runtime: 507 ms, Beats: 7.43%

Memory: 7.92 MB, Beats: 94.83%

9. Palindrome Number

 9. Palindrome Number

難度: Easy

類型: Math

CPP程式下載: 9.cpp

前情題要:

判斷整數是否左右對稱

思考方式:

其實這題真的很簡單, 照題目寫的,直覺去做就好。

複雜度思考:

Time Complexity: O( log10(x) ) 

Space Complexity: O( 1 )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 8.49 MB, Beats: 92.27%

8. String to Integer (atoi)

 8. String to Integer (atoi)

難度: Medium

類型: String

CPP程式下載: 8.cpp

前情題要:

字串轉整數

思考方式:

其實這題很簡單, 反而難的地方在判斷邊界, 如果反轉後數字超過 int32 的範圍, 要回傳那邊的極值。

複雜度思考:

Time Complexity: O( s_size ) 

Space Complexity: O( 1 )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 8.97 MB, Beats: 97.55%

7. Reverse Integer

 7. Reverse Integer

難度: Medium

類型: Math

CPP程式下載: 7.cpp

前情題要:

把數字做十進位的反轉

思考方式:

其實這題很簡單, 反而難的地方在判斷邊界, 如果反轉後數字超過 int32 的範圍, 要回傳 0。我程式裡的 a10 跟 a01, 就是為了判斷這個而生。

複雜度思考:

因為 0x7FFFFFFF = 2,147,483,647。十進位共10位數

Time Complexity: O( 10 ) 

Space Complexity: O( 1 )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 8.47 MB, Beats: 82.10%

6. Zigzag Conversion

6. Zigzag Conversion

難度: Medium

類型: String

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

==========================

前情題要:

將輸入的字串 s, 用深度numRows的 Zigzag 下去排列, 然後從第一列所有的 chars, 接著第二列, ...., 直到最後一列的 chars讀出來放到另一個字串, 並回傳這個字串。

==========================

思考方式:

1-1. 先建立一個 array, 每個index對應的值, 就是代表這個位置在第幾列。一開始是逐漸遞增列數, 到了最大的 numRows 後, 下面就逐漸遞減列數, 直到排到第一列, 之後再遞增, 一直循環。

1-2. 然後就每一列分別跑一輪字串s, 把第一列填完, 填第二列的, .... 直到填完最後一列的輸出字串。

1-3. 這方法簡單而暴力, 但是費時。所以後來又改寫第二種方法

2-1. 藉由觀察發現, 第一列和最後一列, 在填進第一個 char 後, 都會間隔 (numRows-1)*2) 的 char 又填回同一列。

2-2. 藉由觀察發現, 第 i 列, 會在填進第一個 char 後, 先間隔 (numRows-i)*2 個 char, 回到同一列, 然後再間隔 (i-1)*2 個 char, 回到同一列, 然後不斷兩種間隔循環。

2-3. 這方法必須觀察出規則才好寫, 然後要先判斷每個 index 是否超出輸入string 的長度再填入。

==========================

複雜度思考:

方法1:

Time: O (s_size*numRow+s_size)

Memory: O (s_size)

方法2:

Time: O (s_size)

Memory: O (s_size)

==========================

結果:

方法1:

Runtime: 10 ms, Beats: 35.03%

Memory: 11.80 MB, Beats: 77.02%

方法2:

Runtime: 0 ms, Beats: 100%

Memory: 10.79 MB, Beats: 97.02%

5. Longest Palindromic Substring

 5. Longest Palindromic Substring

難度: Medium

類型: Two Pointers, String, Dynamic Programming

CPP程式下載: 5.cpp

==========================

前情題要:

找最長且左右對稱的子字串

==========================

思考方式:

分成子字串個數是偶數, 以及奇數。

1. 若是奇數, 則每個char (s[i]) 當中心, 他左右的兩個 chars 相同, 就繼續往兩邊擴, 長度從1變3, 從3便5, 以此類推, 只要不相同, 就檢查下一個 s[i+1]。

2. 若是奇數, 那 s[i] 就該跟 s[i+1] 相同, s[i-1] 要跟 s[i+2]相同, 以此類推。

3. 無論 1 或 2. 記得紀錄最長的對稱字串的頭尾 index。回傳最大對稱子字串時拿來用。

==========================

複雜度思考:

Time: O (M*(M-1))

Memory: O (1)

==========================

結果:

Runtime: 7 ms, Beats: 88.75%

Memory: 9.42 MB, Beats: 71.64%

12. Integer to Roman

Code

Testcase

Test Result

Test Result

12. Integer to Roman 

難度: Medium

類型: Hash Table, Math, String

CPP程式下載: 12.cpp

==========================

整數轉羅馬數字

跟  13. Roman to Integer 相反

==========================

前情題要:

==========================

思考方式:

其實滿簡單的, 就查表然後照順序填進去。

==========================

複雜度思考:

Time: O (M)

Memory: O (1)

==========================

結果:

Runtime: 0 ms, Beats: 100%

Memory: 9.19 MB, Beats: 84.44%