题解 | #直线上的牛#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

本题考察如何判断多个点是否在同一条直线上，以及如何统计在同一条直线上的点的个数。

题目解答方法的文字分析

我们可以使用斜率来判断多个点是否在同一条直线上，并使用哈希表来统计在同一条直线上的点的个数。

具体步骤如下：

1. 遍历points中的每一对点i和j，计算i点和j点的斜率。
2. 将斜率作为键，使用unordered_map来记录每个斜率对应的点的个数。
3. 遍历哈希表，找到在同一条直线上的点的个数的最大值max_count。
4. 返回max_count + 1作为结果，加1是因为还需要考虑i点本身。

需要注意的是，由于斜率可能是一个浮点数，为了避免精度问题，我们可以使用最简分数形式表示斜率。具体做法是求i点和j点的横纵坐标的差的最大公约数，然后将横纵坐标的差都除以最大公约数得到最简分数形式的斜率。

本题解析所用的编程语言 (C++)

C++

完整且正确的编程代码

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();
        if (n <= 2) {
            return n; // 0个或者1个点时，直线上的点最多是它本身
        }

        int max_count = 0;
        for (int i = 0; i < n; i++) {
            unordered_map<string, int> slope_count; // 斜率 -> 点的个数
            int duplicate_count = 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) {
                    duplicate_count++;
                } else {
                    int gcd_val = gcd(dx, dy);
                    string slope = to_string(dy / gcd_val) + '/' + to_string(dx / gcd_val);
                    slope_count[slope]++;
                }
            }

            max_count = max(max_count, duplicate_count);
            for (auto& [slope, count] : slope_count) {
                max_count = max(max_count, count + duplicate_count);
            }
        }

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

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

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！