大佬教程收集整理的这篇文章主要介绍了[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 +-------------> 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
给定一个二维平面，平面上有 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 = 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 = @H_772_212@"@H_772_212@\(X)@\(y))@H_772_212@" 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，请注明来意。