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)


相关推荐

  • 一篇文章,Vue快速入门!!!

    一篇文章,Vue快速入门!!!①Vue概述及第一个Vue程序(HelloWorld)1.1什么是MVVMMVVM(Model-View-ViewModel)是一种软件设计模式,由微软WPF(用于替代WinForm,以前就是用这个技术开发桌面应用程序的)和Silverlight(类似于JavaApplet,简单点说就是在浏览器上运行WPF)的架构师KenCooper和TedPeters开发,是一种简化用户界面的事件驱动编程方式。由JohnGossman(同样也是WPF和Sliverlight的架构师)与2005年在他的

  • 【安装库】matlab2020b安装及百度网盘提速

    【安装库】matlab2020b安装及百度网盘提速【安装库】matlab2020b安装及百度网盘提速matlab2020b安装一,下载百度网盘链接:https://pan.baidu.com/s/18iLFaAbWt8IntUefX3eWfA提取码:p6in如果下载很慢的话应该是没开p2p加速(最近度盘良心发现加了个p2p下载)开启方法:打开设置开启提速模式开启后会提供一部分资源给别人下载,不下载的时候也会占用一定资源,当然这是相互的,你加速的时候别人也在和你共享资源,所以p2p才快,所以加速也只对热门资源比较有效

  • JavaScript学习第五天笔记(作用域)

    JavaScript学习第五天笔记(作用域)JavaScript学习第五天笔记(作用域)

  • dos命令进入d盘文件夹(windows cd到d盘)

    如何运行命令提示符,然后使用CD命令进入制定文件夹在win系统下进入命令提示符的方式是在开始的输入框中输入“cmd”,然后按“enter”进入。cd为进入的命令。具体步骤如下:步骤一:在pc端主界面中点击“开始”菜单栏,输入“cmd”,按“enter”进入命令提示符界面。步骤二:使用cd命令进入e盘。如何运行命令提示符,然后使用CD命令进入制定文件夹?使用CD命令进入指定文件?比如在桌面文…

  • zabbix监控jmx

    zabbix监控jmx背景:目前公司用的主要语言就是java,然后在运维过程中会遇到频繁的内存溢出的情况,之前使用过elk日志分析系统可以实时的判断出内存溢出的情况,但是无法查看内存的使用情况,只能通过dump文件查看内存溢出的时候dump下来的文件去分析。这样也无法准确的判断出问题。zabbix可以监控java,并且将内存的使用情况实时的展现出来,这是一个不错的选择。JMX的全称是JavaManagement…

  • NABC模型进行需求分析

    NABC模型进行需求分析

发表回复

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

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