题解 | #直线上的牛# 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 (int count : slopeCount.values()) {
                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语言。

该题考察的知识点主要有：

• 二维数组的遍历和操作。
• 使用Map来统计斜率出现的次数。
• 最大公约数的计算。

代码的文字解释如下：

1. 初始化变量duplicateCount为0，用于记录和当前点i重复的点的个数。
2. 遍历二维数组points，对于数组中除了当前点i外的每个点j：如果i和j相同，则跳过当前循环。计算点i到点j的横向偏移量dx和纵向偏移量dy。如果dx和dy都为0，说明点i和点j重复，将duplicateCount加1。否则，计算dx和dy的最大公约数gcdVal。计算斜率，将斜率作为键，并将对应的次数存入slopeCount中。
3. 初始化变量maxCount为0，用于记录最大的直线上的点数。
4. 遍历slopeCount中的值，对于每个次数count：更新maxCount为count + duplicateCount和maxCount的较大值。
5. 将maxCount加1，表示还需考虑点i本身的情况，作为最终的直线上的点数。
6. 返回maxCount作为结果。