55. Jump Game

55. Jump Game

難度: Medium

類型: Array, Dynamic Programming, Greedy

CPP程式下載: 55.cpp

前情題要:

跳躍遊戲, 能否跳到最後的位置

思考方式:

就是檢查每個位置在它之前的位置能否跳到現在的位置。

複雜度思考:

Time Complexity: O( nums.size() ) 

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 52.11 MB, Beats: 87.20%

45. Jump Game II

 45. Jump Game II

難度: Medium

類型: Array, Dynamic Programming, Greedy

CPP程式下載: 45.cpp

前情題要:

從起點跳到終點的最少跳躍數

思考方式:

1. 目前的位置加上可以跳的步數, 直到這個值超過最後一格。

2. 每跳一次, 就要找從最小步數, 到最大步數中, 可以跳到的最遠距離。

3. 直到能越過最後一格就知道需要的最少跳躍數。

4. 記得都要從最小步數(一步)開始找起, 而不是從最大步數的開始到最大步數找起, 這樣會錯過某個突然很大的步數值。

5. 每次的最小步數都是前一次的最小步數加一。

複雜度思考:

Time Complexity: O( (N+1)*N ) 

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 20.39 MB, Beats: 84.63%

44. Wildcard Matching

 44. Wildcard Matching

難度: Hard

類型: String, Dynamic Programming, Greedy, Recursion

CPP程式下載: 44.cpp

前情題要:

含任意字元 '?' 與 '*' 的 pattern match。

思考方式:

1. '*' 是一個特殊的存在, 可以代表任意字串, 也可以是空字串。'?' 則是任意一個字元, 不能為空字串。

2. 首先, 先尋找 '*' 在 pattern 字串中有幾個。若是沒有, 那就是字串 s 和 p 要完全match。若是只有一個 '*', 就把 p 字串分成 '*' 前, 以及 '*' 後兩個字串, 前字串與 s 字串從前面開始比對, 後字串從 s 字串最後方開始往前比對, 若都能 match 且 s 字串中間還有其他字元, 或是剛剛好沒有其他字元, 那麼就是 pattern match。

3. 若 '*' 在 p 字串中有兩個以上, 就把 p 字串切成三份, 第一個 '*' 前, 最後一個 '*' 後, 以及中間含 n-2 個 '*' 的字串。一樣前後字串各自從前後單獨比對。然後中間的字串每兩個 '*' 夾在中間的的字元順序與個數, s 的中間字串要和 p 的中間字串彼此字元順序要相同, 長度相同, 但可以在 s 字串中間隔幾個任意字元組合後再相同。

複雜度思考:

Time Complexity: O( (n-2)*strlen(s) ) 

Space Complexity: O( x )

結果:

Runtime: 3 ms, Beats: 96.32%

Memory: 12.97 MB, Beats: 83.03%

34. Find First and Last Position of Element in Sorted Array

 34. Find First and Last Position of Element in Sorted Array

難度: Medium

類型: Array, Binary Search

CPP程式下載: 34.cpp

前情題要:

在一個由小到大排序的陣列中, 尋找與target值相同的起始和最終位置。

思考方式:

一樣用 binary search 去找, 找到之後再用 binary search 去找左邊的起始點和右邊的起始點。

複雜度思考:

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

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 10.60 MB, Beats: 17.13%

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%