[Swift]LeetCode149.直线上最多的点数|MaxPointsonaLine

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新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: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

Example 2:

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

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

示例 1:

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

示例 2:

输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[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 = 0
15         for i in 0 ..< points.count {
16             var map: [String: Int] = [:]
17             var same: Int = 0
18             var maxP: Int = 0
19             for j in i + 1 ..< points.count {
20                 var x = points[j].x - points[i].x
21                 var y = points[j].y - points[i].y
22                 if x == 0 && y == 0 {
23                     // same point
24                     same += 1
25                     continue
26                 }
27                 let gcd = findGCD(x, y)
28                 if gcd != 0 {
29                     x /= gcd
30                     y /= gcd
31                 }
32                 let d = "\(x)@\(y))"
33                 map[d, default: 0] += 1
34                 maxP = max(maxP, map[d]!)
35             }
36             result = max(result, maxP + same + 1) // 1 for itself
37         }
38         return result
39     }
40     
41     func findGCD(_ a: Int, _ b: Int) -> Int { 
42         if b == 0 {
43             return a
44         }
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.count
16         }
17         var result = 0
18         for i in 0..<points.count {
19             var overlap = 0
20             var infinite = 0
21             var zero = 0
22             var tempMax = 0
23             var map = [Int: [Int: Int]]()
24             for j in i + 1..<points.count {
25                 var xDiff = points[j].x - points[i].x
26                 var yDiff = points[j].y - points[i].y
27                 if xDiff == 0 && yDiff == 0 {
28                     overlap += 1
29                 } else if xDiff == 0 {
30                     infinite += 1
31                 } else if yDiff == 0 {
32                     zero += 1
33                 } else {
34                     let gcd = getGcd(xDiff, yDiff)
35                     xDiff /= gcd
36                     yDiff /= gcd
37                     if map[xDiff] != nil {
38                         map[xDiff]![yDiff] = (map[xDiff]![yDiff] ?? 0) + 1
39                     } 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 + 1
48     }
49     
50     private func getGcd(_ a: Int, _ b: Int) -> Int {
51         var a = a
52         var b = b
53         while b != 0 {
54             let temp = b
55             b = a % b
56             a = temp
57         }
58         return a
59     }
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.count
16         }
17         var maxPointsCount = 2
18         for i in 0 ..< points.count {
19             var dict = [P: Int]()
20             var maxCount = 1
21             var vertical = 1
22             var duplicateI = 0
23             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 += 1
27                     } else if points[j].x - points[i].x == 0 {
28                         vertical += 1
29                     } else {
30                         let dy = points[j].y - points[i].y
31                         let dx = points[j].x - points[i].x
32                         let gcd = getGCD(dx, dy)
33                         if let count = dict[P(dy / gcd, dx / gcd)] {
34                             dict[P(dy / gcd, dx / gcd)] = count + 1
35                             if count + 1 > maxCount {
36                                 maxCount = count + 1
37                             }
38                          } else {
39                             dict[P(dy / gcd, dx / gcd)] = 2
40                          }
41                     }
42                 }
43             }
44             maxPointsCount = max(maxPointsCount, maxCount + duplicateI, vertical + duplicateI)
45         }
46         return maxPointsCount
47     }
48     
49     func getGCD(_ dx: Int, _ dy: Int) -> Int {
50         var x = dx
51         var y = dy
52         while y != 0 {
53             let temp = y
54             y = x % y
55             x = temp
56         }
57         return x
58     }
59     class P: Hashable {
60         let x: Int
61         let y: Int
62         var hashValue: Int {
63             return (x + y).hashValue
64         }
65         init(_ x: Int, _ y: Int) {
66             self.x = x
67             self.y = y
68         }
69         static func == (lhs: P, rhs: P) -> Bool {
70             return lhs.x == rhs.x && lhs.y == rhs.y
71         }
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 = 0
19         
20         for i in 0 ..< points.count {
21             map.removeAll()
22             
23             var localMax = 0
24             var duplicate = 0
25             
26             for j in  i + 1 ..< points.count {
27                 
28                 var x = points[j].x - points[i].x
29                 var y = points[j].y - points[i].y
30                 
31                 if x == 0 && y == 0 {
32                     duplicate += 1
33                     continue
34                 }
35                 
36                 let gcd = generateGCD(x, y)
37                 
38                 if gcd != 0 {
39                     x = x / gcd
40                     y = y / gcd
41                 }
42                 
43                 if let value = map[[x, y]] {
44                     map[[x, y]] = value + 1
45                 } else {
46                     map[[x, y]] = 1
47                 }
48                 
49                 localMax = max(localMax, map[[x, y]]!)
50             }
51             
52             maxPoints  = max(maxPoints, localMax+duplicate+1)
53         }
54         return maxPoints
55         
56     }
57     
58     func generateGCD(_ x: Int, _ y: Int) -> Int {
59         
60         if y == 0 {
61             return x
62         } 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 = 0
15         var n:Int = points.count
16         for i in 0..<n
17         {
18             var duplicate:Int = 1
19             for j in (i + 1)..<n
20             {
21                 var cnt:Int = 0
22                 var x1:Int = points[i].x
23                 var y1:Int = points[i].y
24                 var x2:Int = points[j].x
25                 var y2:Int = points[j].y
26                 if x1 == x2 && y1 == y2
27                 {
28                     duplicate += 1
29                     continue
30                 }
31                 for k in 0..<n
32                 {
33                     var x3:Int = points[k].x
34                     var y3:Int = points[k].y
35                     if x1*y2 + x2*y3 + x3*y1 - x3*y2 - x2*y1 - x1 * y3 == 0
36                     { 
37                         cnt += 1
38                     }
39                 }
40                 res = max(res, cnt)
41             }
42             res = max(res, duplicate)
43         }
44         return Int(res)
45     }
46 }