【Day58】149. 直线上最多的点数

149. 直线上最多的点数

给你一个数组 points ,其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1:

输入:points = [[1,1],[2,2],[3,3]]
输出:3

示例 2:

输入:points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出:4

提示:

  • 1 <= points.length <= 300
  • points[i].length == 2
  • -104 <= xi, yi <= 104
  • points 中的所有点 互不相同

题解:

直接枚举,比较斜率

class Solution {
public:
    int maxPoints(vector>& points) {
        int len = points.size();
        // 点的数量不够
        if(len < 3) {
            return len;
        }
        int maxNum = 2;
        // 遍历每两个点
        for(int i = 0; i < len - 1; i ++) {
            for(int j = i + 1; j < len; j ++) {
                // 统计斜率相等个数
                int count = 2;
                long long dx = points[i][0] - points[j][0];
                long long dy = points[i][1] - points[j][1];
                // 与其他点比较
                for(int k = j + 1; k < len; k ++) {
                    // 如果斜率相等
                    if(dx * (points[i][1] - points[k][1]) == dy * (points[i][0] - points[k][0])) {
                        count ++;
                    }
                }
                maxNum = max(maxNum, count);
                if(maxNum > len / 2) return maxNum;
            }  
        }
        return maxNum;
    }
};

   转载规则


《【Day58】149. 直线上最多的点数》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day59】752.打开转盘锁 【Day59】752.打开转盘锁
752. 打开转盘锁你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转:例如把 ‘9’ 变为 ‘0’,’0’
2021-06-25
下一篇 
【Day57】剑指 Offer 15.二进制中1的个数 【Day57】剑指 Offer 15.二进制中1的个数
剑指 Offer 15. 二进制中1的个数请实现一个函数,输入一个整数(以二进制串形式),输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。 示例 1: 输入:
2021-06-23
  目录