leetcode：149. 直线上最多的点数

题目来源

• leetcode：149. 直线上最多的点数

题目描述

class Solution {
    
public:
    int maxPoints(vector<vector<int>>& points) {
    

    }
};


int main() {
    
    Solution a;

    vector<vector<int>> p {
    {
    1, 1}, {
    3, 2}, {
    5, 3}, {
    4, 1}, {
    2, 3}, {
    1, 4}};
    auto n = a.maxPoints(p);
    std::cout << n << "\n";

    return 0;
}

题目解析

• 思路：
  • 斜率相同的点在同一条直线上
  • 两个点可以确定一条直线，有这么几种情况：
    • 正常的斜率
    • 共点，在同一个位置，要算两份
    • 水平线，斜率为0
    • 共竖线
• 问题是double会精度损失，怎么表示斜率呢？
  • 可以用分数来表示斜率，比如"1_3"，相同的斜率那么求公约数
  • 也可以map套map。
    • key = 3
    • value = {7, 10}：斜率为3/7的点，一共有10个
    • value = {5, 14}：斜率为3/5的点，一共有14个

class Solution {
    
    int gcd(int a, int b){
    
        return b == 0 ? a : gcd(b, a % b);
    }
public:
    int maxPoints(vector<vector<int>>& points) {
    
        int N = points.size();
        if(N <= 1){
    
            return N;
        }

        std::map<std::string, int> map;
        int res = 0;
        for (int i = 0; i < N; ++i) {
    
            map.clear();
            int samePos = 1;
            int sameX = 0;
            int sameY = 0;
            int line = 0;
            for (int j = i + 1; j < N; ++j) {
       //i号点和j号点的斜率关系
                int x = points[j][0] - points[i][0];
                int y = points[j][1] - points[i][1];
                if(x == 0 && y == 0){
    
                    samePos++;
                }else if(x == 0){
    
                    sameX++;
                }else if(y == 0){
    
                    sameY++;
                }else{
    
                    int g = gcd(x, y);
                    x /= g;
                    y /= g;
                    std::string key = std::to_string(x) + "/" + std::to_string(y);
                    ++map[key];
                    line = std::max(line, map[key]);
                }
            }
            res = std::max(res, std::max(std::max(sameX, sameY), line) + samePos);
        }
        return res;
    }
};