Swift   发布时间:2022-03-31  发布网站:大佬教程  code.js-code.com
大佬教程收集整理的这篇文章主要介绍了[Swift]LeetCode149. 直线上最多的点数 | Max Points on a Line大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。

概述

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   +

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,[5,3],[4,[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

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

示例 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 = 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 }

大佬总结

以上是大佬教程为你收集整理的[Swift]LeetCode149. 直线上最多的点数 | Max Points on a Line全部内容,希望文章能够帮你解决[Swift]LeetCode149. 直线上最多的点数 | Max Points on a Line所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。