一、知识点:
循环、HashMap
二、文字分析:
使用两层循环,结合斜率和哈希表来计算最多有多少头牛在同一条直线上。
对于数组中的每一对点 (points[i], points[j])
,首先计算它们之间的横纵坐标差值 dx
和 dy
。如果 dx
和 dy
都为0,则表示这两个点是重复的点,将其计数并跳过后面的处理。
然后,将 dx
和 dy
分别除以它们的最大公约数,以避免得到的斜率不够精确。使用字符串 "dx/dy"
作为斜率的键,并将它们出现的次数记录在哈希表中。
在内层循环结束后,找到哈希表中出现次数最多的斜率,加上重复的点的数量,并与当前的最大计数比较,更新最大值。
最后返回最大计数。
三、编程语言:
java
四、正确代码:
import java.util.*; public class Solution { public int maxPoints(int[][] points) { int n = points.length; if (n <= 2) { return n; } int maxCount = 0; for (int i = 0; i < n; i++) { Map<String, Integer> slopeMap = new HashMap<>(); int samePointCount = 1; int maxPointCount = 0; for (int j = i + 1; j < n; j++) { int dx = points[i][0] - points[j][0]; int dy = points[i][1] - points[j][1]; if (dx == 0 && dy == 0) { samePointCount++; continue; } int gcd = gcd(dx, dy); dx /= gcd; dy /= gcd; String slope = dx + "/" + dy; int count = slopeMap.getOrDefault(slope, 0) + 1; slopeMap.put(slope, count); maxPointCount = Math.max(maxPointCount, count); } maxCount = Math.max(maxCount, samePointCount + maxPointCount); } return maxCount; } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } }