leetcode-149. 直线上最多的点数(map+判重)[通俗易懂]

leetcode-149. 直线上最多的点数(map+判重)[通俗易懂]给定一个二维平面,平面上有 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+—–

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一个二维平面,平面上有 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
const double eps = 1e-10;
const int N = 1e3 + 10;
bool cmp(const double &a,const double &b){ 
   
    return abs(a - b) < eps;
}
struct Node{ 
   
    double k;
    Node(double _k){ 
   
        k = _k;
    }
    bool operator<(const Node &b)const{ 
   
        if(cmp(k,b.k))return false;
        else return k < b.k;
    }
};
class Solution { 
   
public:
    map<Node,int>m;
    int maxPoints(vector<vector<int>>& points) { 
   
        int ans = 0;
        int n = points.size();
        if(n == 1 || n == 0)return n;
        for(int i = 0;i < n;i ++){ 
   
            m.clear();
            int same = 0;
            for(int j = 0;j < n;j ++){ 
   
                if(j == i)continue;
                int x1 = points[i][0],y1 = points[i][1];
                int x2 = points[j][0],y2 = points[j][1];
                if(x1 == x2){ 
   
                    same ++;
                    continue;
                }
                Node t(double(y1 - y2) / (x1 - x2));
                if(m.find(t) == m.end())m[t] = 0;
                m[t] ++;
            }
            for(auto &a : m){ 
   
                ans = max(ans,a.second);
            }
            ans = max(ans,same);
        }
        return ans + 1;
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169067.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Django(47)drf请求生命周期分析

    Django(47)drf请求生命周期分析前言一般我们写完序列化以后,我们就会开始写视图了,drf中我们一般使用CBV的方式,也就是类视图的方式,最基础的我们会使用fromrest_framework.viewsimportAPIVi

  • Tomcat配置ssl协议及遇到的问题https页面无法访问

    Tomcat配置ssl协议及遇到的问题https页面无法访问

  • Python基础之lambda表达式

    Python基础之lambda表达式目录1、lambda函数介绍2、lambda函数与def函数的区别3、lambda案例4、map方法混搭有时在使用函数时不需要给函数分配一个名称,该函数就是“匿名函数”。在python中使用lambda表达式表示匿名函数语法:lambda参数列表:lambda体lambda是关键字声明,在lambda表达式中,参数列表与函数中的参数列表一样,但不需要用小括号括起来,冒号后面是lambda体,lambda表达式的主要代码在lambda体处编写,类似于函数体。提示:lambda体不能是一个代码块,不能包含多条

    2022年10月17日
  • SpringBoot——整合Shiro完成登录检验

    SpringBoot——整合Shiro完成登录检验SpringBoot——整合Shiro完成登录检验

  • 常用的测试用例设计方法有那些类型_测试用例设计

    常用的测试用例设计方法有那些类型_测试用例设计扎实的基础是成功的一半,学号好基础,才能更好的进步!常见的测试用例设计方法主要会涉及以下几种:1、等价类2、边界值3、场景法4、判定表5、因果图6、错误推断法7、正交测试法(正交表)(今天主要解释前三种最为常用)选择合适的测试用例方法,有助于你去更好的梳理出逻辑关联关系,让你的测试覆盖率更高,更高效率的覆盖到所有测试点。一、等价类划分法1)定义依据需求输入划分为若干等价类,从等价类中选定一个测试…

    2022年10月11日
  • PFX 证书转 JKS

    PFX 证书转 JKS在阿里云上申请了一个SSL证书(Symantec免费版SSL),下载下来的是pfx格式的证书。使用的是jetty服务器,需要转换为jks格式。下载的压缩包:PFX证书转JKSkeytool-importkeystore-srckeystoremycert.pfx-srcstoretypepkcs12-destkeystoremycert.jks-d…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号