Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Solution:
public int maxPoints(Point[] points) { if(points.length < 3) return points.length; int result = 2; // at least 2 points on a line Map<Double, Integer> map = new HashMap<>(); for(Point p:points) { map.clear(); int duplicate = 1; // [(1,1),(1,1),(2,2),(2,2)] -> 4 map.put(Double.MIN_VALUE, 0); // for special case: [(1,1),(1,1),(1,1)], no slope will be put to map for(Point q:points) { if(p == q) continue; if(p.x == q.x && p.y == q.y) { duplicate++; continue; } double slope = (p.x == q.x) ? Double.MAX_VALUE : (p.y-q.y)/(double)(p.x-q.x); Integer cnt = map.get(slope); if(cnt == null) cnt = 0; map.put(slope, cnt+1); } for(Integer cnt:map.values()) { result = Math.max(result, cnt+duplicate); } } return result; }
重构了下代码:
public int maxPoints(Point[] points) { if(points == null) return 0; int maxNum = 0; Map<Double, Integer> map = new HashMap<>(); for(Point p:points) { int dup = 1; map.clear(); for(Point q:points) { if(p == q) continue; if(p.x == q.x && p.y == q.y) { dup++; continue; } double slope = slope(p, q); Integer cnt = map.get(slope); if(cnt == null) cnt = 0; map.put(slope, cnt+1); } // for special case: [(1,1),(1,1),(1,1)], no slope will be put to map if(map.size() == 0) return points.length; for(int cnt:map.values()) { maxNum = Math.max(maxNum, cnt+dup); } } return maxNum; } private double slope(Point p1, Point p2) { if(p1.x == p2.x) return Double.MAX_VALUE; return (p2.y-p1.y)/((double)(p2.x-p1.x)); }
相关推荐
大佬的leetcode刷题笔记(c++版本)
彩色版本 正版 pdf 精讲数据结构 + 算法 链表 树 图表 贪心算法 指针 动态规划 查找算法
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
LeetCode题解 - Java语言实现-181页.pdf
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
leetcode1-300.docx
leetcode 答案leetcode--python Leetcode 的答案
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
本书包含了 LeetCode Online Judge所有题目的答案,所有代码经过精心编写,编码规范良好,适合读者反复揣摩,模仿,甚至在纸上默写
500195422331430LeetCode题解 - Java语言实现.zip
leetcode 答案LeetCode--哈希表 以上是我对“哈希表”问题的回答,都被leetcode的判断所接受。
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode 1 -200题所有源码 有问题私聊我
leetcode1-240题中文题解,md格式,java版本 有题目有题解有代码 需要使用markdown打开
leetcode 答案解析 golang解答
leetcode26 algo 算法与数据结构,练习代码 语言:java 8 开发工具:vscode,安装插件Java Extension Pack vscode有智能提示,可调试,有重构支持,满足代码练习要求,相比IDEA更轻量级,普通笔记本即可流畅运行。 ...