题解 | #直线上的牛#

直线上的牛

https://www.nowcoder.com/practice/58ff4047d6194d2ca4d80869f53fa6ec

一、知识点:

循环、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);
    }
}

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务