这波操作.....，就挺不某疆的，因为某疆的薪资是真的没有这么低~
算法题：直线上最多的点数
题目解析
那咋办？
实现思路
遍历每个点，把它当作基点。 对于每个基点，计算其他点与它的斜率。 用一个哈希表统计每个斜率出现的次数。 每次统计完后，取最大值，更新结果。
斜率可能是小数，要注意精度问题。常规操作是用分数来表示斜率，分子和分母取最大公约数化简。 垂直的点用特殊标记，比如斜率是 Infinity。如果两个点重合，算到重复点中即可。
手撸代码
import java.util.HashMap;
public class MaxPointsOnLine {
public int maxPoints(int[][] points) {
if (points == null || points.length == 0) return 0;
int maxPoints = 1;
for (int i = 0; i < points.length; i++) {
HashMap<String, Integer> slopeMap = new HashMap<>();
int overlap = 0;
int localMax = 0;
for (int j = i + 1; j < points.length; j++) {
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
if (dx == 0 && dy == 0) {
overlap++;
continue;
}
int gcd = getGCD(dx, dy); // 分子分母化简
dx /= gcd;
dy /= gcd;
// 构造唯一斜率字符串
String slope = dx + "/" + dy;
slopeMap.put(slope, slopeMap.getOrDefault(slope, 0) + 1);
localMax = Math.max(localMax, slopeMap.get(slope));
}
maxPoints = Math.max(maxPoints, localMax + overlap + 1); // 加上基点和重叠点
}
return maxPoints;
}
// 辗转相除法求最大公约数
private int getGCD(int a, int b) {
if (b == 0) return a;
return getGCD(b, a % b);
}
public static void main(String[] args) {
MaxPointsOnLine solution = new MaxPointsOnLine();
int[][] points = {{1, 1}, {2, 2}, {3, 3}, {4, 2}};
System.out.println(solution.maxPoints(points)); // 输出：3
}
}
有趣的细节
哈希表存斜率：用 dx/dy的形式存储，避免浮点数精度问题。想用小数直接比对的，基本就是“踩坑手册”上的常客。重合点处理：别忘了基点和重复点会影响计数，就像代码中的 overlap变量。GCD化简：这是亮点。用最大公约数化简分子和分母，像处理分数一样优雅。
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
