[Swift]LeetCode149. 直线上最多的点数 | Max Points on a Line_app

概述Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. Example 1: Input: [[1,1],[2,2],[3,3]]Output: 3Explanation:^|| o| o| o +

Given n points on a 2D plane,find the maximum number of points that lIE on the same straight line.

Example 1:

input: [[1,1],[2,2],[3,3]]Output: 3Explanation:^||        o|     o|  o  +------------->0  1  2  3  4

Example 2:

input: [[1,[5,3],[4,[1,4]]Output: 4Explanation:^||  o|     o        o|        o|  o        o+------------------->0  1  2  3  4  5  6

给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

示例 1:

输入: [[1,3]]输出: 3解释:^||        o|     o|  o  +------------->0  1  2  3  4

示例 2:

输入: [[1,4]]输出: 4解释:^||  o|     o        o|        o|  o        o+------------------->0  1  2  3  4  5  6

44ms

 1 /** 2  * DeFinition for a point. 3  * public class Point { 4  *   public var x: Int 5  *   public var y: Int 6  *   public init(_ x: Int,_ y: Int) { 7  *     self.x = x 8  *     self.y = y 9  *   }10  * }11  */12 class Solution {13     func maxPoints(_ points: [Point]) -> Int {14         var result: Int = 015         for i in 0 ..< points.count {16             var map: [String: Int] = [:]17             var same: Int = 018             var maxP: Int = 019             for j in i + 1 ..< points.count {20                 var x = points[j].x - points[i].x21                 var y = points[j].y - points[i].y22                 if x == 0 && y == 0 {23                     // same point24                     same += 125                     continue26                 }27                 let gcd = findGCD(x,y)28                 if gcd != 0 {29                     x /= gcd30                     y /= gcd31                 }32                 let d = "\(x)@\(y))"33                 map[d,default: 0] += 134                 maxP = max(maxP,map[d]!)35             }36             result = max(result,maxP + same + 1) // 1 for itself37         }38         return result39     }40     41     func findGCD(_ a: Int,_ b: Int) -> Int { 42         if b == 0 {43             return a44         }45         return findGCD(b,a % b)46     }47 }

48ms

 1 /** 2  * DeFinition for a point. 3  * public class Point { 4  *   public var x: Int 5  *   public var y: Int 6  *   public init(_ x: Int,_ y: Int) { 7  *     self.x = x 8  *     self.y = y 9  *   }10  * }11  */12 class Solution {13     func maxPoints(_ points: [Point]) -> Int {14         guard points.count > 2 else {15             return points.count16         }17         var result = 018         for i in 0..<points.count {19             var overlap = 020             var infinite = 021             var zero = 022             var tempMax = 023             var map = [Int: [Int: Int]]()24             for j in i + 1..<points.count {25                 var xDiff = points[j].x - points[i].x26                 var yDiff = points[j].y - points[i].y27                 if xDiff == 0 && yDiff == 0 {28                     overlap += 129                 } else if xDiff == 0 {30                     infinite += 131                 } else if yDiff == 0 {32                     zero += 133                 } else {34                     let gcd = getGcd(xDiff,yDiff)35                     xDiff /= gcd36                     yDiff /= gcd37                     if map[xDiff] != nil {38                         map[xDiff]![yDiff] = (map[xDiff]![yDiff] ?? 0) + 139                     } else {40                         map[xDiff] = [yDiff: 1]41                     }42                     tempMax = max(tempMax,map[xDiff]![yDiff]!)43                 }44             }45             result = max(result,max(max(infinite,zero),tempMax) + overlap)46         }47         return result + 148     }49     50     private func getGcd(_ a: Int,_ b: Int) -> Int {51         var a = a52         var b = b53         while b != 0 {54             let temp = b55             b = a % b56             a = temp57         }58         return a59     }60 }

80ms

 1 /** 2  * DeFinition for a point. 3  * public class Point { 4  *   public var x: Int 5  *   public var y: Int 6  *   public init(_ x: Int,_ y: Int) { 7  *     self.x = x 8  *     self.y = y 9  *   }10  * }11  */12 class Solution {13     func maxPoints(_ points: [Point]) -> Int {14         guard points.count > 2 else {15             return points.count16         }17         var maxPointsCount = 218         for i in 0 ..< points.count {19             var dict = [P: Int]()20             var maxCount = 121             var vertical = 122             var duplicateI = 023             for j in 0 ..< points.count {24                 if i != j {25                     if points[i].x == points[j].x,points[i].y == points[j].y {26                         duplicateI += 127                     } else if points[j].x - points[i].x == 0 {28                         vertical += 129                     } else {30                         let dy = points[j].y - points[i].y31                         let dx = points[j].x - points[i].x32                         let gcd = getGCD(dx,dy)33                         if let count = dict[P(dy / gcd,dx / gcd)] {34                             dict[P(dy / gcd,dx / gcd)] = count + 135                             if count + 1 > maxCount {36                                 maxCount = count + 137                             }38                          } else {39                             dict[P(dy / gcd,dx / gcd)] = 240                          }41                     }42                 }43             }44             maxPointsCount = max(maxPointsCount,maxCount + duplicateI,vertical + duplicateI)45         }46         return maxPointsCount47     }48     49     func getGCD(_ dx: Int,_ dy: Int) -> Int {50         var x = dx51         var y = dy52         while y != 0 {53             let temp = y54             y = x % y55             x = temp56         }57         return x58     }59     class P: Hashable {60         let x: Int61         let y: Int62         var hashValue: Int {63             return (x + y).hashValue64         }65         init(_ x: Int,_ y: Int) {66             self.x = x67             self.y = y68         }69         static func == (lhs: P,rhs: P) -> Bool {70             return lhs.x == rhs.x && lhs.y == rhs.y71         }72     }73 }

88ms

 1 /** 2  * DeFinition for a point. 3  * public class Point { 4  *   public var x: Int 5  *   public var y: Int 6  *   public init(_ x: Int,_ y: Int) { 7  *     self.x = x 8  *     self.y = y 9  *   }10  * }11  */12 class Solution {13     func maxPoints(_ points: [Point]) -> Int {14 15         guard points.count > 2 else { return points == nil ? 0: points.count }16         17         var map: [[Int]: Int] = [[Int]: Int]()18         var maxPoints = 019         20         for i in 0 ..< points.count {21             map.removeAll()22             23             var localMax = 024             var duplicate = 025             26             for j in  i + 1 ..< points.count {27                 28                 var x = points[j].x - points[i].x29                 var y = points[j].y - points[i].y30                 31                 if x == 0 && y == 0 {32                     duplicate += 133                     continue34                 }35                 36                 let gcd = generateGCD(x,y)37                 38                 if gcd != 0 {39                     x = x / gcd40                     y = y / gcd41                 }42                 43                 if let value = map[[x,y]] {44                     map[[x,y]] = value + 145                 } else {46                     map[[x,y]] = 147                 }48                 49                 localMax = max(localMax,map[[x,y]]!)50             }51             52             maxPoints  = max(maxPoints,localMax+duplicate+1)53         }54         return maxPoints55         56     }57     58     func generateGCD(_ x: Int,_ y: Int) -> Int {59         60         if y == 0 {61             return x62         } else {63             return generateGCD(y,x % y)64         }65     }66 }

288 ms

 1 /** 2  * DeFinition for a point. 3  * public class Point { 4  *   public var x: Int 5  *   public var y: Int 6  *   public init(_ x: Int,_ y: Int) { 7  *     self.x = x 8  *     self.y = y 9  *   }10  * }11  */12 class Solution {13     func maxPoints(_ points: [Point]) -> Int {14         var res:Int = 015         var n:Int = points.count16         for i in 0..<n17         {18             var duplicate:Int = 119             for j in (i + 1)..<n20             {21                 var cnt:Int = 022                 var x1:Int = points[i].x23                 var y1:Int = points[i].y24                 var x2:Int = points[j].x25                 var y2:Int = points[j].y26                 if x1 == x2 && y1 == y227                 {28                     duplicate += 129                     continue30                 }31                 for k in 0..<n32                 {33                     var x3:Int = points[k].x34                     var y3:Int = points[k].y35                     if x1*y2 + x2*y3 + x3*y1 - x3*y2 - x2*y1 - x1 * y3 == 036                     { 37                         cnt += 138                     }39                 }40                 res = max(res,cnt)41             }42             res = max(res,duplicate)43         }44         return Int(res)45     }46 }