1760. Minimum Limit of Balls in a Bag

 1760. Minimum Limit of Balls in a Bag

難度: Medium

類型: Array, Binary Search

CPP程式下載: 1760.cpp

前情題要:

第 i 個袋子裡有 nums[i] 個球, 有 MaxOperations 次可以把袋子分裝成兩袋的機會, 所有袋子裡最多的球數當作 cost, 那麼能夠達到最小的 cost 為何?

思考方式:

Binary Search, 每次把範圍縮一半, 直到找到最小值。

複雜度思考:

Time Complexity: O( log2(N) ) 

Space Complexity: O( x )

結果:

Runtime: 27 ms, Beats: 83.93%

Memory: 59.69 MB, Beats: 96.72%

2762. Continuous Subarrays

 2762. Continuous Subarrays

難度: Medium

類型: Array, Queue,Sliding Window, Heap (Priority Queue), Ordered Set, Monotonic Queue

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

前情題要:

連續的子陣列。任意個子陣列裡的值相減必須小於等於2

思考方式:

1. 用 Sliding Window 的方式, 抓 high low index。

2. 解出來不難, 但要夠快, 能排名在前面不容易。

3. 2762_1.cpp, 用 multiset, 能自動排序且數值可以重複, 最右邊的最大值減掉最左邊的最小值, 就能判斷是否符合 substring 要相減 "<=2" 的條件。每次sliding window 的左邊 low index 移動前, 要先找到multiset中相同值並移除。這可以做到 230~240 ms 的速度, 約Beat 22~23%, 而且multiset存了太多數值, 空間約156MB, Beat 19%。

4. 2762_2.cpp, 相減要小於等於2, 所以取任一值當中心點, 其他的數字只可能在 -2~+2 的範圍, 所以只需要存五個值的出現次數 "freq_range[5]"。當移動sliding window 的左邊 low index 時, 根據 low index 位置數值和前次的 low index 數值的差, 來移動freq_range[5]; freq_range[2]永遠都是目前 low index那個值出現的次數。一直保留前次的high index, 並讓sliding window試著往右邊推進。因為只有存五個值的freq, 所以移動起來容易(運算少), 而且不須存大量的資料。在時間和空間上都有效率。不過就是程式比較繁瑣, 要考慮的 boundary condition 比較多。

複雜度思考:

Time Complexity: O( 2*N ) 

Space Complexity: O( 16*sizeof(int) + sizeof(long long) )

結果:

Runtime: 78 ms, Beats: 91.90%

Memory: 111.69 MB, Beats: 97.92%

790. Domino and Tromino Tiling

 790. Domino and Tromino Tiling

難度: Medium

類型: Dynamic Programming

CPP程式下載: 790.cpp

前情題要:

2*1 的骨牌, 與2*2缺一格的骨牌組合(可旋轉)。有多少種組合方式能得到一個2*n的長條形。(數字很大, 必須 modulo 10^9+7)

思考方式:

老實說, 這一題對我來說很難。而且我認為這題是數學題, 而不是 Dynamic Programming。如果想得到很棒的數學表示方式, 那就能用很精簡的程式算出答案。

1. 定義 F(N) 和 G(N)。F(N) 是組成2*N的長條形的可能組合個數。G(N)是組成2*N長條形卻缺了右下一格的組合個數。

2. F(N)=2*G(N-1)+F(N-2)+F(N-1) :

    (2-1) G(N-1), 右下缺一個的形狀, 配上左上缺一個的 Tromino tile。能構成 F(N)。

    (2-2) G(N-1), 右上缺一個的形狀, 配上左上缺一個的 Tromino tile。能構成 F(N)。

    (2-3) F(N-2), 配上兩個橫置並排 2*1 的骨牌, 能構成 F(N)

    (2-4) F(N-1), 配上一個 2*1 的骨牌, 能構成 F(N)

3. G(N)=G(N-1)+F(N-2) :

    (3-1) G(N-1) 缺右下的改成缺右上的, 個數一樣, 再搭配一個2*1的骨牌橫置擺在右上那一排, 就成了G(N)缺右下的。

    (3-2) F(N-2) 就是 2*(N-2) 的長條形配上一個2*2但右下缺一格的骨牌, 就成了G(N)。

複雜度思考:

Time Complexity: O( 2*N ) 

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 8.33 MB, Beats: 8.94%

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%