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

- 日理万妓 2022-06-03 04:51 486阅读 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 条评论，486人围观）

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

相关阅读

相关 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 赞/ 26 阅读

相关【LeetCode】149. 直线上最多的点数

> 2021.6.24号每日一题文章目录题目链接题目简介题目解析题目代码题目链接 [149.

比眉伴天荒/ 2022年10月09日 12:17/ 0 赞/ 96 阅读

相关 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 赞/ 152 阅读

相关 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 赞/ 160 阅读

相关 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 赞/ 142 阅读

相关 LeetCode149—Max Points on a Line

原题 [原题链接][Link 1] > Given n points on a 2D plane, find the maximum number of points

￡神魔★判官ぃ/ 2022年07月15日 09:21/ 0 赞/ 135 阅读

相关 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 赞/ 209 阅读

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

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

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

相关 [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 赞/ 197 阅读

相关 149. Max Points on a Line

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

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