Java 题解 | #直线上的牛#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param points int整型二维数组
     * @return int整型
     */
    public int maxPoints (int[][] points) {
        // write code here
        int n = points.length;
        if (n <= 2) {
            return n; // 0个或者1个点时，直线上的点最多是它本身
        }

        int maxCount = 0;
        for (int i = 0; i < n; i++) {
            Map<String, Integer> slopeCount = new HashMap<>(); // 斜率 -> 点的个数
            int duplicateCount = 0; // 和i点重复的点的个数

            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                int dx = points[i][0] - points[j][0];
                int dy = points[i][1] - points[j][1];

                if (dx == 0 && dy == 0) {
                    duplicateCount++;
                } else {
                    int gcdVal = gcd(dx, dy);
                    String slope = (dy / gcdVal) + "/" + (dx / gcdVal);
                    slopeCount.put(slope, slopeCount.getOrDefault(slope, 0) + 1);
                }
            }

            maxCount = Math.max(maxCount, duplicateCount);
            for (Map.Entry<String, Integer> entry : slopeCount.entrySet()) {
                int count = entry.getValue();
                maxCount = Math.max(maxCount, count + duplicateCount);
            }
        }

        return maxCount + 1; // 加1是因为还需要考虑i点本身
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

Java编程语言。

该题考察的是在给定一些点的情况下，找到一条直线上最多的点数。可以使用斜率来进行判断。对于每个点，计算它与其他点的斜率（通过计算两点之间的横纵坐标差值，并求它们的最大公约数来获取斜率的分数形式表示），并统计相同斜率的点的个数。

代码的文字解释大纲如下：

1. 获取点的个数n，如果n小于等于2，直接返回n。
2. 定义一个变量maxCount用于记录最大点数，初始化为0。
3. 遍历每个点，使用HashMap slopeCount来存储斜率和对应的点的个数，定义变量duplicateCount记录和当前点重复的点的个数，初始化为0。
4. 遍历其他点（排除当前点），计算当前点与其他点的横纵坐标差值，求它们的最大公约数，得到斜率的分数形式表示。
5. 如果两点重合（dx和dy都为0），则重复计数器duplicateCount加1；否则，将斜率slope转换为字符串形式，并在slopeCount中进行统计。
6. 更新maxCount为duplicateCount和maxCount中的较大值。
7. 遍历slopeCount中的每个斜率和对应的点数，更新maxCount为count + duplicateCount和maxCount中的较大值。
8. 返回maxCount + 1作为结果，其中加1是因为还需要考虑当前点本身。
9. 实现私有方法gcd，用于计算最大公约数，使用辗转相除法进行计算。