主題

LeetCode - 554. Brick Wall 解題心得

Not In My Back Yard | 2021-05-04 00:00:04 | 巴幣 0 | 人氣 18

題目連結:


題目意譯:
有一個磚牆在你面前。牆壁為矩形,且有著若干列的磚頭。磚頭們有著相同的高度但有著不一樣的寬度。你想要畫一條從頂端到底部的鉛直線,使其穿過的磚頭數盡可能地少。

磚牆表示為一個磚頭列之列表。每磚頭列為一個整數列表代表著從左到右此列中每個磚頭的寬度。

如果你的線經過一個磚頭的邊緣,則該磚頭不被視為被穿過。你需要找出如何畫線使得穿過的磚頭數為最少,並回傳被穿過的磚頭數。

你不能直接沿著牆上的兩個鉛直邊畫線,在這個情況下理所當然地不會穿過任何磚頭。

注:
不同列的磚頭總寬度皆相同,且不會超過 INT_MAX。
每列的磚頭數介於 [1, 10,000] 範圍中。牆的高度介於 [1, 10,000] 之範圍中。牆壁上的磚頭總數不超過 20,000 個。



範例測資:
輸入: [[1,2,2,1],
        [3,1,2],
        [1,3,2],
        [2,4],
        [3,1,2],
        [1,3,1,1]]
輸出: 2
解釋:


解題思維:
將所有磚頭的右端點座標化(以牆壁左側為起點,座標值 = 0)存成一陣列 A。

例如範例測資的輸入第一列 [1,2,2,1] 其磚頭之右端座標依序為
1、
1 + 2 = 3、
1 + 2 + 2 = 5、
1 + 2 + 2 + 1 = 6
又例如其第二列 [3,1,2] 其磚頭右端點座標依序為
3、
3 + 1 = 4、
3 + 1 + 2 = 6

因此範例輸入會得到一陣列 A = [1, 3, 5, 6, 3, 4, 6, 1, 4, 6, 2, 6, 3, 4, 6, 1, 4, 5, 6]。

然後我們將 A 排序。因此範例會得到 A = [1, 1, 1, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 6, 6]

因為此例中 6 是牆壁的右側,所以我們將那些數字忽略掉得到 A = [1, 1, 1, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5]。

此時,我們可以看到每一個數字可以對應到一個畫鉛直線之位置。例如上面的 A[0] = 1 對應到鉛直線畫在座標值 1 的地方。

而因為此例 A[0] = A[1] = A[2],所以前三塊磚頭的右側皆相同,所以該條鉛直線不會穿過這三塊磚頭,而這三塊磚頭不會是在同一列的(因為右端點座標相同,所以不可能擠在同一列)。換句話說,這條線會穿過另外三列的磚頭。

因此我們可以找到連續出現最多次的數字(如這題的做法),而找到線應該畫在哪裡才能使得線靠齊最多的磚頭右緣,而這同時也表示線穿過的磚頭數越少。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作