leetcode最小面积_Code Review Swift 算法题: 最小面积矩形 Leetcode 的动人之处
題目描述: 939. 最小面積矩形
給定在 xy 平面上的一組點，確定由這些點組成的矩形的最小面積，其中矩形的邊平行于 x 軸和 y 軸。
如果沒有任何矩形，就返回 0。
示例 1：
輸入：[[1,1],[1,3],[3,1],[3,3],[2,2]]
輸出：4
示例 2：
輸入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
輸出：2
提示：
1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
所有的點都是不同的。
官方題解: 通過對角線找點
( 這個中文站沒有的，主站有英文的。
中文博客，很多的。
本文，簡單大白話講 )
直覺這么走:
對于數組中的每一對點，設想他們是一個矩形的對角線，然后就簡單了。
矩形有兩條對角線，如果另外一條對角線上面的點，也在給定的數組里面，就找出了一個滿足要求的矩形。
用散列集合確認四個點。
舉個例子:
有了兩個點 (1, 1) 和 (5, 5) 。看一下 (1, 5) 和 (5, 1) 有沒有。
有，就找到了一個滿足要求的矩形。
然后，找出所有的矩形中，面積最小的。
算法這么走:
把所有的點，放入一個哈希集合。
對于每一對點，如果哈希集合 set 中包含，相關矩形四個不同的頂點，
( 換句話說， 交換下 x 與 y， 如果能在哈希集合中找到另一條對角線的兩個點 )
該矩形的面積是，一個可能的解。
PS : 使用散列集合，就是找起來方便。化 O(n) 為 O(1).
查找，不是通過元素遍歷，是通過哈希值。
散列集合聽起來... , 實際就是 Set.
使用哈希，更常見的是字典，字典可以理解為哈希表 (散列表).
缺點就是，算哈希值的時候，有碰撞風險。
(就是集合里面，多個不同的元素，算出來的哈希值相同。
有些尷尬。
一般是把相同哈希值的元素，放入一個數組。查找到這種情況，又是遍歷了 )
題解 ( 改進前):
因為 Swift 中的元組沒實現哈希協議，
(Python 中的元組，自帶哈希)
所以要用散列集合，就要實現坐標的結構體。
我參照了一下這個 StackOverFlow 的鏈接， 就寫出了下面的。
這么寫，性能比較差，Leetcode 報超時: Time Limit Exceeded
var hashValue: Int{
return "(\(x),\(y))".hashValue
}
復制代碼
根據題目的限制，我改進了一下哈希的 get 屬性，就通過了
var hashValue: Int{
return x * 100000 + y
}
復制代碼
( 關于 Leetcode 用 Swift 語言答題的, 報超時另一經驗是，遍歷字符串的時候，先把字符串轉化為數組。
Swift 遍歷數組的性能，要好一些 )
改進前
// 為了利用散列集合，構建結構體
struct Point: Hashable{
var x: Int
var y: Int
init(_ x: Int, _ y: Int) {
self.x = x
self.y = y
}
var hashValue: Int{
return x * 100000 + y
}
static func == (_ lhs: Point, _ rhs: Point) -> Bool{
return lhs.x == rhs.x && lhs.y == rhs.y
}
}
func minAreaRect(_ points: [[Int]]) -> Int {
let newPoints = points.map({ (point: [Int]) -> Point in
return Point(point[0], point[1])
})
// 先把所有有效的點找出來 ( 就是，沒有重復的 )
let pointSet = Set(newPoints)
var minArea = Int.max
// 然后兩次循環，每一對點，都嘗試搭配一次，找出每一個可能的矩形
for point in points{
for innerPoint in points{
if point[0] != innerPoint[0] , point[1] != innerPoint[1] , pointSet.contains(Point(point[0], innerPoint[1])) ,pointSet.contains(Point(innerPoint[0], point[1])) {
// 找出最小的矩形
minArea = min(minArea, abs((innerPoint[1] - point[1] ) * (innerPoint[0] - point[0])))
}
}
}
if minArea == Int.max {
return 0
}
else{
return minArea
}
}
復制代碼
結構體有些冗余，不但實現了 Hashable， 還實現了 Hashable 派生出來的 Equatable 協議
Code Review:
算法上的改進 ( 使用數學提升性能， 初中的 )
for point in points{
for innerPoint in points{
if ( // ... 判斷條件 ) {
// 找出最小的矩形
minArea = min(minArea, abs((innerPoint[1] - point[1] ) * (innerPoint[0] - point[0])))
}
}
}
復制代碼
根據解題思路，對角線的兩頂點。
可以設想一頂點是左下，一頂點是右上，
( 因為設想對角線的位置，決定了后面兩個點的坐標怎么取 )
右上的頂點 x , y 值自然比 左下的大，這樣就省去了取絕對值的操作。
for lowerLeft in points {
for upperRight in points {
if ( // ... 判斷條件 ) {
let area = (upperRight[0] - lowerLeft[0]) * (upperRight[1] - lowerLeft[1])
minArea = min(minArea, area)
}
}
}
復制代碼
Swift 語言上的改進，
這個題目中的 Point 結構體，賦值后，就沒有再修改 (寫入)。 可以改 var 為 let .
Swift 4.2 中，如果結構體所有的成員變量都遵守 Hashable協議，
編譯器回自動給該結構體創建 Hashable 協議的方法。
struct Point: Hashable {
let x: Int
let y: Int
}
復制代碼
結構體有自己默認的初始化方法，不用補充一個
改進閉包
let newPoints = points.map({ (point: [Int]) -> Point in
return Point(point[0], point[1])
})
let pointSet = Set(newPoints)
復制代碼
Swift 語言有類型推導特性，就不用顯式聲明類型了。編譯器能夠自動推導出參數和返回值的類型
let newPoints = points.map { point in Point(x: point[0], y: point[1]) }
let pointSet = Set(newPoints)
復制代碼
經過上一步的整理，代碼比較簡潔，可以進一步合并
let pointSet = Set(points.map { point in Point(x: point[0], y: point[1]) })
復制代碼
改進后的代碼:
struct Point: Hashable {
let x: Int
let y: Int
}
func minAreaRect(_ points: [[Int]]) -> Int {
let pointSet = Set(points.map { point in Point(x: point[0], y: point[1]) })
var minArea = Int.max
for lowerLeft in points {
for upperRight in points {
if upperRight[0] > lowerLeft[0]
&& upperRight[1] > lowerLeft[1]
&& pointSet.contains(Point(x: lowerLeft[0], y: upperRight[1]))
&& pointSet.contains(Point(x: upperRight[0], y: lowerLeft[1])) {
let area = (upperRight[0] - lowerLeft[0]) * (upperRight[1] - lowerLeft[1])
minArea = min(minArea, area)
}
}
}
return minArea == Int.max ? 0 : minArea
}
復制代碼
Leetcode 的動人之處挺多的，本文繼續 8 看代碼的姿勢
查看競賽回顧
( Leetcode 的競賽很強大，每個星期天都有 )
進入競賽，
下滑到競賽回顧，點擊感興趣的一場
(就是找到想做的題目)
下滑，選擇更多
點擊感興趣的題目
看到代碼。
( 代碼這么多，肯定看不完 )
有了 Leetcode 討論區，為什么還推薦這樣看代碼？
( 雖然是很強的人，寫的代碼 )
因為這是競賽的時候寫的代碼，很趕時間。
哪里有后面的那么多的設計。
很不優雅，糙，快，直觀。( 大神的代碼思路，較容易的理解 ... )
題目做不出來，可以了解一下。
( 想看高手的，可以...
沒 dollar 買會員，想做題, 例如第 772 ，靠百度。這里可以看代碼思路， 第 69 場周賽 )
Leetcode 的精華，是測試用例
測試用例多，有時候各種想不到，讓程序員的思維更加周全
例如這道題，有用例 130
這個用例，體會到了我代碼的脆弱
if point[0] != innerPoint[0] , point[1] != innerPoint[1] , pointSet.contains(Point(innerPoint[0], point[1])) ,pointSet.contains(Point(innerPoint[1], point[0])) {
// 找出最小的矩形
minArea = min(minArea, abs((innerPoint[1] - point[1] ) * (innerPoint[0] - point[0])))
}
復制代碼
另一對頂點的語義，取反了
總結
以上是生活随笔為你收集整理的leetcode最小面积_Code Review Swift 算法题: 最小面积矩形 Leetcode 的动人之处的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： jsch设置代理_尽管在JSch中设置了
- 下一篇： 的源码管理器中有感叹图标_玄说前端面试层