专栏首页蛮三刀的后端开发专栏[Leetcode][python]Max Points on a Line/直线上最多的点数

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

题目大意

在一个平面上有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 条评论
登录 后参与评论

相关文章

  • [Leetcode][python]Pascal's Triangle/Pascal's Triangle II/杨辉三角/杨辉三角 II

    后端技术漫谈
  • [Leetcode][python]Evaluate Reverse Polish Notation/逆波兰表达式求值

    有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

    后端技术漫谈
  • 【设计模式自习室】享元模式 Flyweight Pattern:减少对象数量

    在享元模式中通常会出现工厂模式,需要创建一个享元工厂来负责维护一个享元池(Flyweight Pool)用于存储具有相同内部状态的享元对象。

    后端技术漫谈
  • 2.5万汉族人的GWAS乳腺癌风险基因

    今天是大年初七,给大家带来的是2.5万汉族人的GWAS乳腺癌风险基因,希望你能学到知识。

    生信技能树
  • Flask使用mysql数据池

    人生不如戏
  • PHP的几个常用加密函数

    在网站的开发过程中,常常需要对部分数据(如用户密码)进行加密,本文主要介绍PHP的几个常见的加密函数

    wangxl
  • ArcGIS Image Server简介以及OL2中的加载

    本文讲述Arcgis Image Server相关以及在OL2中如何加载Arcgis Server发布的影像服务。

    lzugis
  • 技术规范(1): 前端技术开发规范

    ESLint最初是由Nicholas C. Zakas 于2013年6月创建的开源项目。它的目标是提供一个插件化的javascript代码检测工具。

    机械视角
  • PPT导出时嵌入字体的方法

    使用ppt的时候,很多时候会使用一些特殊字体,在其他计算机上无法正常显示。这个时候就需要导出PPT的时候进行字体嵌入。 1.1 常规方法 所谓常规方法,是指那些...

    用户1631416
  • 设计模式-单例

    登记模式:是为了克服饿汉式单例类及懒汉式单例类均不可继承的缺点而设计的。他的子类实例化的方式只能是懒汉式

    yiduwangkai

扫码关注云+社区

领取腾讯云代金券