ETH官方钱包

前往
大廳
主題

LeetCode - 587. Erect the Fence 解題心得

Not In My Back Yard | 2022-02-14 00:00:04 | 巴幣 2 | 人氣 378

題目連結:


題目意譯:
你被給定一陣列 trees,其中 trees[i] = [xi, yi] 代表著一棵樹在花園中的位置。

你被要求使用著長度盡可能短的繩子將整個花園用圍籬圍起來,因為繩子很貴。花園有被圍好若且唯若所有樹都有被圍於繩子內。

回傳恰好位於圍籬邊上的那些樹之座標。

限制:
1 ≦ trees.length ≦ 3000
trees[i].length == 2
0 ≦ xi 、 yi ≦ 100
所有給定的座標皆相異。



範例測資:
範例 1:
輸入: points = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
輸出: [[1,1],[2,0],[3,3],[2,4],[4,2]]

範例 2:
輸入: points = [[1,2],[2,2],[4,2]]
輸出: [[4,2],[2,2],[1,2]]


解題思維:
本題實際上就是在求凸包(如這題)——正確來說是「幾乎」凸包,因為本題還需要包含進那些剛好在凸包邊上的點。

可以將在建立凸包的過程中允許共線的情況(外積 = 0),最後消掉重複的點;或是求完凸包後,重新掃過一次所有點,判斷哪些點在凸包上也是可行的。




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

創作回應

相關創作

更多創作