题目描述: 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, 如果能在哈希集合中找到另一条对角线的两个点 )
该矩形的面积是, 一个可能的解.
题解 ( 改进前):
因为 Swift 中的元组没实现哈希协议,
(Python 中的元组, 自带哈希)
所以要用散列集合, 就要实现坐标的结构体.
我参照了一下这个 Stack Overflow 的链接, 就写出了下面的.
这么写, 性能比较差, 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 链接: Minimum Area Rectangle
感谢 Martin R code review 我的代码
相关代码: https://github.com/BoxDengJZ/leet_algo_101
来源: https://juejin.im/post/5c063e3ce51d451dc63085b0