您现在的位置是:首页 > 正文

leetcode:149. 直线上最多的点数

2024-04-01 05:14:11阅读 1

题目:
给定一个二维平面,平面上有 n 个点,求最多有多少个点在同一条直线上。
示例 1:
输入: [[1,1],[2,2],[3,3]]
输出: 3
解释:
^
|
| o
| o
| o
±------------>
0 1 2 3 4
示例 2:
输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出: 4
解释:
^
|
| o
| o o
| o
| o o
±------------------>
0 1 2 3 4 5 6

学习

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
class Solution {
    public int maxPoints(Point[] points) {
        if (points == null) return 0;
        
        int solution = 0;
        
        //一条直线的确定需要一个点和一个斜率。对于每一个i点,(1)一个点确定了;那么只需在map中保存斜率值,则就代表了一条直线。
        for (int i = 0; i < points.length; i++)
        {
        	//每一个i的for循环都需重新对map进行新的创建
        	//这两重循环的目的:是对每一个i点,找到i+1之后的点能确定的直线的数量和与之对应的在该直线上的点的个数。
            Map<String, Integer> map = new HashMap<>();
           //duplicate:复制品
            int duplicate = 0;
            int max = 0;
            //每一个j循环的开始是:i+1,前面的点都不考虑的原因是:如果此前的点会影响此时i和j确定的直线,那么该点在该直线上。而该点和此时的i点确定的直线已经在之前统计过了。
            //此时,i与j确定的直线如果是之前i循环中统计过的直线,那么该统计的个数是有错误的,不过,之前已经统计过了,所以可以为了减少循环范围而忽略。
            for (int j = i + 1; j < points.length; j++)
            {
            //用来计算斜率
                int deltaX = points[j].x - points[i].x;
                int deltaY = points[j].y - points[i].y;
                
                //与i点重合的点
                if (deltaX == 0 && deltaY == 0)
                {
                    duplicate++;
                    continue;
                }
                //关于斜率的表示,斜率不用小数表示,而用dy+“,”+dx来表示,但是要注意,类似:6/4和3/2是表示同一直线,所以需对dy和dx除以其最大公约数。还有,要考虑:3/0和5/0是用一条直线。-6/2和3/-1是同一条直线
                int gcd = gcd(deltaX, deltaY);
                int dX = deltaX / gcd;
                int dY = deltaY / gcd;
                
                map.put(dX + "," + dY, map.getOrDefault(dX + "," + dY, 0) + 1);
                //得到过此时i点的点的个数的最大值
                max = Math.max(max, map.get(dX + "," + dY));
            }
            //与过其他i点的最大值比较。
            solution = Math.max(solution, max + duplicate + 1);
        }
        
        return solution;
    }
    //最大公约数
    //在该函数表达中,0与任意非零整数的最大公约数为该整数本身,所以7/0,-2/0为同一直线1/0。
    //%为取余数,/为取商
    public int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a%b);
    }
}

可以这样用+直接构成一个字符串

            int dX = deltaX / gcd;
            int dY = deltaY / gcd;
            
            map.put(dX + "," + dY, map.getOrDefault(dX + "," + dY, 0) + 1);

网站文章

  • 高性能(二)

    高性能(二)

    高性能(二)

    2024-04-01 05:14:04
  • 【Linux】项目shell启动脚本简单模本

    背景:启动 tomcat + jar工程

    2024-04-01 05:13:57
  • Pytorch中的转置卷积

    反卷积反卷积(Transposed Convolution)输出大小计算起点可以整除不可以整除综合起来参考文献 反卷积(Transposed Convolution) 又称为转置卷积。 torch.n...

    2024-04-01 05:13:17
  • 安装think PHP5

    安装think PHP5

    Composer安装 Composer 是 PHP 的一个依赖管理工具。它允许你申明项目所依赖的代码库,它会在你的项目中为你安装他们。 下载地址:https://getcomposer.org/Com...

    2024-04-01 05:13:10
  • java:CAS、ABA问题详解

    1、java中的原子性操作所谓原子性操作,是指执行一系列操作时,这些操作要么全部执行,要么全部不执行,不存在只执行其中一部分的情况。2、CAS方法CAS即Compare and Swap,其是JDK提...

    2024-04-01 05:13:02
  • 系统错误:&amp;H8007007E(-2147024770)。 找不到指定的模块。解决

    系统错误:&amp;H8007007E(-2147024770)。 找不到指定的模块。 就很发呆,以前就正常。 然后发现多个ocx,那肯定是这个组件没有注册了。运行了vb库失败后,便从程序里复制了MSINET.OCX,放到了c:/windows/systems32 下面 然后在开始运行里输入:regsvr32 MSINET.OCX,进行注册 提示注册成功后,完成 程序...

    2024-04-01 05:12:20
  • layui踩坑记录之form表单下的button按钮默认自动提交

    layui踩坑记录之form表单下的button按钮默认自动提交

    因此,当我们在使用form的时候,如果没有添加标准的提交按钮,会自动默认把其他的普通按钮认为是提交按钮,因为button的type默认值为“submit”。其实就是使用form的时候,应该对应有一个提...

    2024-04-01 05:12:12
  • 加快局域网访问时间的方法策略

    法一:将网卡调至全速按下Win+Pause/Break键,单击“硬件”标签,再单击“设备管理器”从而打开“设备管理器”,双击“网络适合器”下相应网卡,在打开窗口中单击“高级”标签,选中Link Spe...

    2024-04-01 05:12:06
  • 微信小程序-处理多个文件上传

    一、方法的封装/** * 采用递归的方式上传多个文件 * filePaths 要上传的资源 * results 上传成功返回的数据 * successUp 成功个数 * failUp 失败个数 * index 上传文件的下标 */function uploadOneByOne(filePaths = [], results = [] , successUp =...

    2024-04-01 05:11:59
  • SQL过滤与应用过滤如何选择

    SQL过滤与应用过滤进行复杂查询的时候,数据可以通过SQL过滤,也可以在应用层进行过滤。应当优先采用哪一种过滤方式呢?通常来说,优化数据库后可以更快速有效的对数据进行过滤。使用客户端进行过滤的方法通常是:sql的select语句为客户端应用检索出超过实际所需的数据,然后客户端代码对返回数据进行循环提取出需要的行。使用客户端应用进行过滤时,有三个不好的影响:1.会极大的影响应用的性能2....

    2024-04-01 05:11:19