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)); }
相关推荐
python python_leetcode题解之149_Max_Points_on_a_Line.py
《LeetCode 101 - A LeetCode Grinding Guide (C++ Version)》是一本专为C++程序员设计的深入解析LeetCode算法问题的指南。这本书采用彩色版,以直观的方式讲解了各种数据结构和算法,旨在帮助读者磨练编程技能,...
《LeetCode---C++实现》是一本专注于C++编程语言解决LeetCode在线判题平台上的算法问题的书籍。LeetCode是程序员广泛使用的平台,它提供了大量的编程题目来提升编程技能和算法理解,尤其对于准备面试的程序员来说,...
1. leetCode-126-Word-LadderII.md:这涉及到第126题,词梯问题,通常是一个字符串转换问题,目标是找到两个单词之间的最短转换序列,每次只改变一个字母。 2. leetcode-224-Basic-Calculator.md:这是第224题,基础...
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode26 algo 算法与数据结构,练习代码 语言:java 8 开发工具:vscode,安装插件Java Extension Pack vscode有智能提示,可调试,有重构支持,满足代码练习要求,相比IDEA更轻量级,普通笔记本即可流畅运行。 ...
leetcode 答案Leetcode---算法 我对 Leetcode 算法问题的回答
leetcode 接口 该项目可帮助您使用首选的 IDE 或带有命令行界面 (CLI) 的编辑器来执行 leetcode。 入门 先决条件 Windows 10、MacOS、Linux Chrome版 >=90.0.4430 安装 # Prepare your virtual environment conda ...
leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站! ⦙⦙⦙⦙⦙⦙⦙⦙ 一个很打问题的方法。 问题来缓解离线思考。 编码前的源代码。 居住和与 leetcode.com。 下载你...
c c语言_leetcode 0017_letter_combinations_of_a_phone_number.zip
leetcode-训练 算法训练。 java $: javac hello.java java $: java hello c $: gcc hello.c 如果没有错误会生成a.out 可执行文件 c $: ./a.out leetcode cli leetcode version leetcode help leetcode help user ...
leetcode-machine-swift :SOS_button: 请帮助在Sources/leetcode-machine-swift/leetcode.swift设置所有 leetcode 问题。 :SOS_button: 在 swift 编码时有 xcode 总是好的。 利用自动补全、类型检查...功能可以帮助...
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
java java_leetcode-110-balanced-binary-tree
java java_leetcode-73-set-matrix-zeroes
leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站! ⦙⦙⦙⦙⦙⦙⦙⦙ 一个很打问题的方法。 问题来缓解离线思考。 编码前的源代码。 居住和与 leetcode.com。 下载你...
java java_leetcode-maximum-depth-of-binary-tree
java java_leetcode-99-recover-binary-search-tree
java java_leetcode-115-distinct-subsquences