首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[Leetcode][python]Max Points on a Line/直线上最多的点数

[Leetcode][python]Max Points on a Line/直线上最多的点数

作者头像
蛮三刀酱
发布2019-03-26 15:45:27
7850
发布2019-03-26 15:45:27
举报

题目大意

在一个平面上有n个点,求一条直线最多能够经过多少个这些点。

解题思路

哈希表保存斜率

代码

注意有个坑: 测试集[[0,0],[94911151,94911150],[94911152,94911151]],由于数字大,直接内置除法斜率会算成一样的,用numpy库运算

import numpy as np
class Solution:
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        n = len(points)
        slope_map = {}
        result = 0
        for i in range(n):
            # print(slope_map)
            slope_map.clear()
            same, vertical = 1, 0
            slope_max = 0
            for j in range(i + 1, n):
                dx, dy = points[i].x - points[j].x, points[i].y - points[j].y
                if dx == dy == 0:  # 同一个点
                    same += 1
                elif dx == 0:  # 斜率无限大,垂直
                    vertical += 1
                else:
                    slope = (dy * np.longdouble(1)) / dx
                    # slope = float(dy) / float(dx)
                    # print(slope)
                    slope_map[slope] = slope_map.get(slope, 0) + 1
                    slope_max = max(slope_max, slope_map[slope])
            result = max(result, max(slope_max, vertical) + same)
        return result

总结

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年12月19日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目大意
  • 解题思路
  • 代码
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档