13. Roman to Integer

 13. Roman to Integer

難度: Easy

類型: Array, Binary Search, Divide and Conquer

CPP程式下載: 13.cpp

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

羅馬數字轉整數

另外有 12. Integer to Roman

一開始原本想這題怎麼難度只有 Easy, 不過寫到後來, 真的不難。

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

前情題要:

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

思考方式:

每次遇到 1, 10, 100, 1000, 就要先看下一個 char 是多少, 才能決定這個羅馬數字是 400 或 900, 40 或 90, 4 或 9。

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

複雜度思考:

Time: O (M)

Memory: O (1)

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

結果:

Runtime: 0 ms, Beats: 100%

Memory: 10.06 MB, Beats: 84.45%

4. Median of Two Sorted Arrays

 4. Median of Two Sorted Arrays

難度: Hard

類型: Array, Binary Search, Divide and Conquer

CPP程式下載: 4.cpp

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

算出兩個已排序矩陣合併後的中間值

其實這題並不難, 不知道為何難度是 Hard

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

前情題要:

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

思考方式:

1. 已知兩個矩陣的長度(m, n), 那合併矩陣的總長度是 m+n, 如果 (1+m+n) 是 2 的倍數, 那中間就是 (1+m+n)/2, 如果不能整除, 那就是拿 (1+m+n)/2 跟 (1+m+n)/2 + 1 位置的兩個數相加除以 2。

2. 就是兩個矩陣從小到大一個一個拿出來比較, 低的放進合併矩陣。(不必真的放, 題目不需要回傳新的合併矩陣, 所以只需要算新矩陣目前的個數, 以判斷到中間值了沒有。)

註: 要注意 m 或 n 可能有一個為 0, 分清楚邊界即可。

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

複雜度思考:

Time: O (log2(m+n))

Memory: O (1)

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

結果:

Runtime: 0 ms, Beats: 100%

Memory: 95.20 MB, Beats: 47.31%

3. Longest Substring Without Repeating Characters

 3. Longest Substring Without Repeating Characters

難度: Medium

類型: Depth-First Search

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

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

找一個字串中, 最長且沒有重複字元的連續子字串長度多少。

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

前情題要:

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

思考方式:

1. 簡單就記錄目前用過的每個 char 的對應位置值為 1, 且這個 char 是 array 中第幾個 index。每次檢查新的 char 是不是在目前的 substring 出現過, 是的話, 這就是目前 substring 的最大長度, 跟目前記錄的最大長度比較, 是否要更新, 然後回到前一個相同 char 的下一個 index 再開始往後計算。

2. 這也可以用 Sliding Window 處理, 兩個 index 參數, 分別代表 sliding window 的頭尾, 沒遇到相同的 char, 頭就一直往下走。如果遇到重複的 char, 就把尾巴一直往後移動, 並更新使用過的 char 清單。我認為這個方式會比我目前附的算法更快, 但目前算法的 Runtime 已經 beat 超過一半的人了, 就有時間再更新吧!!

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

複雜度思考:

3_1.cpp:

Time Complexity: O( 2*N )

Space Complexity: O( 256*(sizeof(INT)+sizeof(bool) )

3_2.cpp:

Time Complexity: O( 2*N )

Space Complexity: O( 256*(sizeof(bool) )

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

結果:

3_1.cpp:

Runtime: 6 ms, Beats: 71.54%

Memory: 11.32 MB, Beats: 89.00%

3_2.cpp:

Runtime: 0 ms, Beats: 100%

Memory: 10.84 MB, Beats: 94.25%

2. Add Two Numbers

 2. Add Two Numbers

難度: Medium

類型: Array, Hash Table

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

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

兩個 digits 的 ListNodes 相加, 結果用另一個 ListNode 回傳。

數字是從低位數到高位數填進 ListNode 的, 除非該數字是0, 不然不會有以 0 開頭的 ListNode。

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

前情題要:

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

思考方式:

就跟算數學一樣從低位算到高位, 記得考慮進位的數字 (carry)。

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

複雜度思考:

Time Complexity: O( max(L1.size(), L2.size()) )

Space Complexity: O( max(L1.size(), L2.size()) +1 )

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

結果: (2_2.cpp 的為例)

Runtime: 0 ms, Beats: 100%

Memory: 77.02 MB, Beats: 73.08%

1. Two Sum

 1. Two Sum

難度: Easy

類型: Array, Hash Table

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

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

Hash Table 的題目, LeetCode 的第一題, 與某一線外商的 coding interview 的介紹影片題目相近。

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

前情題要:

簡單說就是找到兩個 nums verctor<int> 中的index, 他們對應的值相加等於 target

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

思考方式與複雜度:

1. 一樣從簡單直覺開始, 就兩個數字, 第一個數字的 index i從 0~nums_size; 另一個數字的 index j 從 i+1~nums_size; 找到兩個相加等於 target 就回傳 {i,j}。這樣的 time O(N^2), 但由於不需要多餘的memory complexity O(1)

2. 另一個比較快的方式, 用 unordered_map, 因為題目有寫唯一解, 所以就不必用到 multimap。每一個 nums 的element值, 都檢查有沒有它的 complement 值在 unordered_map 裡, 有的話就是找到答案, 把該 index 和在 unordered_map 裡的 index 組起來回傳答案。如果沒找到, 就把這個值的 complement 當作 key, index當作value, 存進 unordered_map 中, 如果最後一個 element 都找不到 complement, 就回傳空集合{}, 同時記得debug, 因為題目說有唯一解。這個時間複雜度O(N), 空間複雜度也是O(N)。

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

結果:

Accepted    63 / 63 testcases passed

1. 第一種方法

Runtime: 34 ms, Beats: 41.30%

Memory: 13.99 MB, Beats: 92.87%

2. 第二種方法

Runtime: 0 ms, Beats: 100%

Memory: 14.73 MB, Beats: 50.22%

2448. Minimum Cost to Make Array Equal

2448. 讓陣列的值全部香等所需的最低花費 

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

2448. Minimum Cost to Make Array Equal

難度: Hard

類型: Matrix

CPP程式下載: 2448.cpp

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

覺得 minimum cost 類型的題目很生疏, 挑幾題來練習, 難度還是Hard

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

前情題要:

nums中第 i 個 elelment 要加一或減一所需的花費為 cost[i]

把所有 nums 中的成員都變成一樣的值, 求所需的最少花費

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

思考方式:

1. 最低的花費必定在 min_num 和 max_num 中間。

2. 有點像二次曲線找 minimum 的cost值, 有一個最低點, 然後兩邊的cost都越來越高。

3. 因為最後相同的值(target)必定是正整數, 所以可能有兩個target值都能得到minimum cost。

4. 用 binary search 比較快, 一次切西瓜挑中間值。

5. 每次 search 要算連續的兩個正整數, 中間值無條件捨去, 以及它的值加一。

6. 留意 boundary (邊界), 才能正確地找到最低花費, 停下來。

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

複雜度思考:

就 binary search 的模式。時間上就 N*log2(N)。空間上並沒有複製 vector, 也沒有做多餘的 memory table。

Time: O (N*log2(N))

Memory: O (1)

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

結果:

Accepted 48 / 48 testcases passed

Runtime: 0 ms, Beats: 100%

Memory: 42.20 MB, Beats: 78.24%

3139. Minimum Cost to Equalize Array, part 2

 3139. 讓矩陣每個元素的值都相同的最小花費 (Beats 100%) 

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

3139. Minimum Cost to Equalize Array

難度: Hard

類型: Array, Greedy, Enumberation

CPP程式下載: 3139_2.cpp

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

覺得 minimum cost 類型的題目很生疏, 挑幾題來練習, 結果挑上一個難題。

這次不直接對"vector<int> nums"做操作, 直接用算的。

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

前情題要:

cost1 是矩陣內的一個元素值加1, 所需要的花費

cost2 是矩陣內的兩個元素值都加1, 所需要的花費

Input: vector<int> nums , int cost1, int cost2

Output: Minimum cost

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 106
• 1 <= cost1 <= 106
• 1 <= cost2 <= 106

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

思考方式:

1. 算出最小值, 最大值, 還有"vector<int> nums"所有數字加總。

2. 如果 cost1 * 2 <= cost2, 那直接每個數字都直接加一操作, 就可得到最小花費。

3. 考量例外情況, 如果nums_size 是1, 回傳 0, 如果num_size是2, 只能做 cost1的操作, 結果就如同 step2。

4. 接著就是cost1 * 2 > cost2, 這情形要先做 cost2, 先盡量把所有的數字都變成最大值, 然後剩下的再用 cost1 補齊, 或是繼續做 cost2操作 (max_num也會同時被加一, cost2 操作)。

5. 但步驟4不一定得到最小花費, 可能還能繼續做 cost2 的操作, 所有數字在大於 max_num 的情形下達成一致。

6. 引進 target 值的概念, 就是最後每個數字都被加到變成 target。 target 從 max_num 開始, 逐漸加1。

7. cost2操作就是一次兩個數字都加1, 最大的gap在"target - min_num"上, 如果這個gap值大於 "total gap = (target* nums_size  - sum_num)" 的一半, 代表 當其他數字都被加到 target, 原本最小的那個值, 還沒到 target, 就需要用 cost1 操作來補足。

8. 如果最大的gap小於或等於total gap的一半, 代表最後會剛好被cost2操作補滿, 或是剩下一個 cost1的花費。

9. 停止時機, 如果 target + 1 後, 算出來的 minimum cost沒有更低, 就可以結束了。不然後面只會越來越大, 不會再出現更低的 minimum cost了。

註1: Coding 時要注意, int * int 可能會超過最大值, int+int 也可能超過最大值, 此時記得把某一個int 被臨時宣告成 (long), 後面運算的結果才會被當成是 long 然後不會產生 runtime (overflow) error。

註2: 記得在accumulate中輸入最後一個參數是 0L, 這個L很重要, 不然也會產生 runtime error, 而且錯誤的行號並不會指出你程式內的位置。

accumulate(nums.begin(), nums.end(), 0L);

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

複雜度思考:

難的是要想到這樣的運算方式。通常要經歷失敗過程數次才能想通。

這樣的運算沒有重疊的迴圈, 最麻煩的只有算出 max, min, sum, 時間上並沒有多餘的浪費。

在記憶體上也沒有另外產生新的 verctor 來暫存, 所以在空間上也是很有效率的。

Time: O (n+x)

Memory: O (x)

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

結果:

636 / 636 testcases passed

Runtime: 0 ms, Beats: 100%

Memory: 94.34 MB, Beats: 86.44%