美文网首页
最多有多少个点在同一条直线上

最多有多少个点在同一条直线上

作者: Haward_ | 来源:发表于2019-03-15 21:04 被阅读0次

给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。
https://leetcode-cn.com/problems/max-points-on-a-line/

class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b

class Solution:
    def maxPoints(self, points):
        size = len(points)
        if size in [0,1]:
            return size
        res = 0
        for i in range(size):
            cur_max = 1
            d = {}
            count = 0
            dup = 0
            for j in range(size):
                if j!=i:
                    deta_x = points[i].x - points[j].x
                    deta_y = points[i].y - points[j].y
                    if deta_x == 0 and deta_y == 0:
                        dup += 1
                    elif deta_x == 0:
                        if count == 0:
                            count = 2
                        else:
                            count += 1
                        cur_max = max(count,cur_max)
                    else:
                        k = deta_y/deta_x
                        if d.get(k) == None:
                            d[k] = 2
                        else:
                            d[k] += 1
                        cur_max = max(d[k],cur_max)
            res = max(res,cur_max + dup)
        return res

相关文章

  • 最多有多少个点在同一条直线上

    给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。https://leetcode-cn.co...

  • Day74 直线上最多的点数

    给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。 https://leetcode-cn.c...

  • 直线上最多的点数

    问题描述: 给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。 示例 1: 输入: 输出: 解...

  • 149. 直线上最多的点数

    给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。 示例 1: 输入: [[1,1],[2,2...

  • Leetcode 149. 直线上最多的点数

    给定一个二维平面,平面上有n个点,求最多有多少个点在同一条直线上。 分析: 暴力破解 根据两点确定一条直线原理,我...

  • LintCode最多有多少个点在一条直线上

    给出二维平面上的n个点,求最多有多少点在同一条直线上。 这道题搞得我非常恼火,很早以前就做出来了,一直都是WA,但...

  • Leetcode.149.Max Points on a Lin

    题目 二维坐标上给定多个点, 输出最多有多少个点在一条直线上. 思路 遍历计算两点的斜率, 运用gcd记录斜率, ...

  • 2017-09-20 S弯笔记草稿

    中间偏右进库,背直。 雨刷点在白线之间的黄线上,主要在黄线上 黄线两条边都看到点,在黄线上打方向沿着弧度走 背直 ...

  • 【数字书写】数字0-9在田字格中的书写格式

    “1”的写法 两个点:第一个点在上边线上,竖中线稍微偏左的位置;第二个点在下边线上,左边线稍微偏右的位置。用直直的...

  • LeetCode 力扣 128. 最长连续序列

    题目描述(困难难度) 给一个数组,求出连续的数字最多有多少个,时间复杂度要求是 O(n)。 解法一 首先想一下最直...

网友评论

      本文标题:最多有多少个点在同一条直线上

      本文链接:https://www.haomeiwen.com/subject/igfepqtx.html