149. Max Points on a Line - 草稿

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

这个题目难不是很难,建立一个dict,斜率:该斜率上点的个数,算斜率特别要注意,如果使用Fraction(3,4),则会非常影响性能,使用np.longdouble(1)满足要求,真是坑爹。

from fractions import Fraction
from collections import defaultdict
import numpy as np
d = defaultdict(lambda: 100)
class Solution(object):                
    def isequalpt(self, p1, p2):
        if p1.x == p2.x and p1.y == p2.y:
            return True
        else:
            return False
    def maxPointsatPoint(self, points):
        pt = points[0]
        del points[0]
        i = 0
        maxnum = 0
        same = 1
        dic = defaultdict(lambda: 0)
        while i < len(points):
            p = points[i]
            if self.isequalpt(pt, p):
                same += 1
                # 并且把p删除
                points.remove(p)
                continue
            if pt.x != p.x:
                k = (p.y-pt.y)*np.longdouble(1)/(p.x-pt.x)
                dic[k] += 1
                maxnum = max(maxnum, dic[k])
            else:
                dic['zero'] += 1
                maxnum = max(maxnum, dic['zero'])
            i += 1
        maxnum += same
        return maxnum
     
    def maxPoints(self, points):
        """
        :type points: List[Point]
        :rtype: int
        """
        lens = len(points)  
        print lens
        if lens < 3:
            return lens
        self.dic=None
        self.maxnumAll = 0
        i = 0
        while lens > 2:
            lr = self.maxPointsatPoint(points)
            self.maxnumAll = max(self.maxnumAll, lr)
            lens = len(points)
        
        return self.maxnumAll

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏林冠宏的技术文章

分享个 之前写好的 android 文件流缓存类,专门处理 ArrayList、bean。

转载麻烦声明出处:https://cloud.tencent.com/developer/user/1148436/activities 目录:   1,前序 ...

2.3K50
来自专栏mathor

N皇后

16220
来自专栏C#

关于Dapper.NET的相关论述

   年少时,为何不为自己的梦想去拼搏一次呢?纵使头破血流,也不悔有那年少轻狂。感慨很多,最近事情也很多,博客也很少更新了,毕竟每个人都需要为自己的生活去努力。...

31270
来自专栏面朝大海春暖花开

redis实现分布式锁工具类 灰常好用

49620
来自专栏java、Spring、技术分享

Netty NioEventLoop源码解读

  NioEventLoop中维护了一个线程,线程启动时会调用NioEventLoop的run方法,执行I/O任务和非I/O任务:I/O任务:即selectio...

26030
来自专栏向治洪

ReactNative调用Android原生模块

有时候App需要访问平台API,但React Native可能还没有相应的模块包装;或者你需要复用一些Java代码,而不是用Javascript重新实现一遍;又...

22070
来自专栏wannshan(javaer,RPC)

dubbo监控机制之监控中心实现分析

这里的监控中心以dubbo-ops\dubbo-monitor-simple项目说 总的来说是监控中心启动一个sevlet容器,通过web页面向用户多维度的展...

1.4K60
来自专栏智能大石头

Cortex-M3启动深度解析

Cortex-Mx启动,备忘,以免将来忘记。 中断向量表不用说,从重置中断开始吧 LDR R0, =SystemInit BLX R0 LDR ...

20960
来自专栏强仔仔

SpringBoot中Redis的set、map、list、value、实体类等基本操作介绍

今天给大家介绍一下SpringBoot中Redis的set、map、list、value等基本操作的具体使用方法 上一节中给大家介绍了如何在SpringBoot...

73080
来自专栏电光石火

ssm整合Redis

这次谈谈Redis,关于Redis应该很多朋友就算没有用过也听过,算是这几年最流行的NoSql之一了。 

1.6K50

扫码关注云+社区

领取腾讯云代金券