2021/4/2 OJ每日一题1196: 数星星（二）（结构体专题）python

1196: 数星星（二）（结构体专题）

一天，小明坐在院子里数星星，Gardon就出了个难题给他，让他数数天上的星星最多有多少个是在同一条直线上的。天上的星星太多了，小明马上就看花了眼，你能写个程序来帮他计算么？

输入 ：

首先输入一个整数N(N<=300)，接下来的N对数每对表示一个星星的位置（星星的坐标在-10000到10000之间，精确到小数点后1位）。没有两个星星会在同一个位置。

输出 ：

一个整数，表示一条直线上最多星星的数目。

python代码：

class Solution:def maxPoints(self, points) -> int:def gongyue(x, y):if x < y:x, y = y, xr = x % ywhile r != 0:x = yy = rr = x % yreturn ylp = len(points)if lp < 3:return lpresult = 2for p1 in range(lp - 1):d = {'chuizhi': 0, 'pingxing': 0}temp = 1p1x, p1y = points[p1]mostpoints = 0for p2 in range(p1 + 1, lp):p2x, p2y = points[p2]if p1x == p2x and p1y == p2y:temp += 1elif p1x == p2x:d['chuizhi'] += 1mostpoints = max(mostpoints, d['chuizhi'])elif p2y == p1y:d['pingxing'] += 1mostpoints = max(mostpoints, d['pingxing'])else:hy = (p2y - p1y)hx = (p2x - p1x)a = gongyue(abs(hy), abs(hx))hy = hy // ahx = hx // aif hy < 0:hy = -hyhx = -hxd[(hy, hx)] = d.get((hy, hx), 0) + 1mostpoints = max(mostpoints, d[(hy, hx)])result = max(result, mostpoints + temp)return resultn = int(input())
lis = []
while n > 0:n -= 1lis.append(list(map(eval, input().split())))
si = Solution()
print(si.maxPoints(lis))

注：主要是解决黄色部分的问题。
参考来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-points-on-a-line
人生苦短，我用python。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！