Leedcode3- Max Points on a Line 共线点个数-白红宇的个人博客

发布日期：2025-04-04 18:33:36 浏览次数：17 分类：精选文章

本文共 1512 字，大约阅读时间需要 5 分钟。


   
   
   
    
   
    #include 
     
      #include 
      #include 
       
        using namespace std;struct Point {    int x;    int y;    Point(int a = 0, int b = 0) : x(a), y(b) {}};class Solution {public:    int maxPoints(const vector
        
         & points) {        if (points.empty()) return 0;        if (points.size() == 1) return 1;        int max_colinear = 1; // 最大共线点数        map
         
           slope_counts; // 用于存储相同斜率的点数 for (int i = 0; i < points.size(); ++i) { // 每个点作为参考点 int x0 = points[i].x; int y0 = points[i].y; int same = 0; // 重合的点数 for (int j = 0; j < points.size(); ++j) { if (j == i) continue; int x = points[j].x; int y = points[j].y; if (x0 == x && y0 == y) { same++; } else { // 计算斜率 double dx = x0 - x; double dy = y0 - y; double slope; if (dx == 0) { // 垂直线，点在同一条垂直线上 if (same != 0) { max_colinear = max(max_colinear, same + 1); } // 已经不重合的点都在垂直线上 if (same == 0) { same = 1; // 空间内可能在同一直线，没有重合点 } // 更新斜率为无穷大 if (same > 1) { // 跑步 slit jump } } else { if (dy != 0) { slope = (double)dy / dx; } else { // 平行线，点位于水平线上 if (same != 0) { max_colinear = max(max_colinear, same + 1); } } if (same + (slope_counts.find(slope) != slope_counts.end() ? slope_counts[slope] : 0) + 1) { max_colinear = max(max_colinear, same + slope_counts[slope] + 1); } slope_counts[slope]++; } } } } return max_colinear; }};int main() { Point p1(1, 1), p2(2, 2), p3(3, 3), p4(4, 4), p5(5, 5); vector
          
            v; v.push_back(p1); v.push_back(p5); v.push_back(p2); v.push_back(p3); v.push_back(p4); Solution s; cout << s.maxPoints(v) << endl;}

上一篇：Leedcode4-sort listnode 归并排序

下一篇：Leedcode2-后缀表达式结果

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章