一、知识点:
循环、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);
}
}

京公网安备 11010502036488号