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

- 日理万妓 2022-06-03 04:51 444阅读 0赞

## 题目大意 ##

在一个平面上有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

## 总结 ##

发表评论取消回复

表情：

评论列表（有 0 条评论，444人围观）

还没有评论，来说两句吧...

相关阅读

相关 bupt|118. Three Points On A Line

时间限制 1000 ms 内存限制 65536 KB 题目描述 Given points on a 2D plane, judge whether there’re th

柔情只为你懂/ 2023年05月22日 08:45/ 0 赞/ 10 阅读

相关 leetcode 149. Max Points on a Line |149. 直线上最多的点数（Java）

题目 [https://leetcode.com/problems/max-points-on-a-line/][https_leetcode.com_problems_

今天药忘吃喽~/ 2022年09月01日 15:43/ 0 赞/ 143 阅读

相关 Max Points on a Line--LeetCode

Given n points on a 2D plane, find the maximum number of points that lie on the same str

旧城等待，/ 2022年08月07日 13:35/ 0 赞/ 147 阅读

相关【leetcode每日一题】149.Max Points on a line

题目：Given n points on a 2D plane, find the maximum number of points that lie on the same

清疚/ 2022年08月04日 12:56/ 0 赞/ 113 阅读

相关 lintcode Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same str

本是古典何须时尚/ 2022年07月15日 13:19/ 0 赞/ 124 阅读

相关 3.max-points-on-a-line 直线上的最多点

题目描述 Given n points on a 2D plane, find the maximum number of points that lie on the

我不是女神ヾ/ 2022年06月06日 07:20/ 0 赞/ 189 阅读

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

题目大意在一个平面上有n个点，求一条直线最多能够经过多少个这些点。解题思路哈希表保存斜率代码注意有个坑：测试集\[\[0,0\],\[94

- 日理万妓/ 2022年06月03日 04:51/ 0 赞/ 445 阅读

相关 LeetCode刷题笔记（穷举）：max-points-on-a-line

-------------------- 转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net

向右看齐/ 2022年05月31日 01:35/ 0 赞/ 159 阅读

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

Max Points on a Line > Given n points on a 2D plane, find the maximum number of point

港控/mmm°/ 2022年02月17日 02:43/ 0 赞/ 180 阅读

相关 149. Max Points on a Line

class Solution { public int maxPoints(Point[] points) { if(point

系统管理员/ 2021年12月22日 06:55/ 0 赞/ 184 阅读