leetcode 149. Max Points on a Line 计算斜率的问题 + 直接暴力求解即可

﹏ヽ暗。殇╰゛Y 2022-06-08 06:24 119阅读 0赞

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

本题就是统计在一条线上的最多的点的数量。

解决方法就是遍历求解，但是主语Java的浮点数的计算精度的问题。

这道题就必须要考虑精度的问题，否者部分case是过不去的，

代码如下：

import java.math.BigDecimal;
    import java.util.HashMap;
    
    /*class Point 
    {
          int x;
          int y;
          Point() { x = 0; y = 0; }
          Point(int a, int b) { x = a; y = b; }
    }*/
    
    /*
     * 注意Java的浮点数精度
     * */
    public class Solution
    {
        public int maxPoints(Point[] points)
        {
            if (points.length <= 2)
                return points.length;
    
            int max = 2;
            for (int i = 0; i < points.length; i++) 
            {
                int pointMax = 1, samePointCount = 0;
                HashMap<Double, Integer> slopeCount = new HashMap<Double, Integer>();
                for (int j = i + 1; j < points.length; j++) 
                {
                    if (points[i].x == points[j].x && points[i].y == points[j].y)
                    {
                         samePointCount++;
                         continue;
                    }          
                    double k;
                    if (points[i].x == points[j].x)
                        k = Float.POSITIVE_INFINITY;
                    //这里是为了避免出现-0.0和0.0的问题
                    else if (points[i].y == points[j].y)
                        k = 0.0;
                    else
                    {
                        //这里是为了避免出现（k,k+1）,(k+1,k+2)和（0,0）的斜率精度问题
                        //这里是考虑到了Java的Double的精度问题，所以才是用BigDecimal的问题
                        BigDecimal fenziBigDecimal=new BigDecimal(points[i].x-points[j].x);   
                        BigDecimal fenmuBigDecimal=new BigDecimal(points[i].y-points[j].y);             
                        k = fenziBigDecimal.divide(fenmuBigDecimal,20,BigDecimal.ROUND_HALF_DOWN).doubleValue();
                    }
                    slopeCount.put(k, slopeCount.getOrDefault(k, 1)+1);
                    pointMax = Math.max(pointMax, slopeCount.get(k));
                }
                max = Math.max(max, pointMax+samePointCount);
            }
            return max; 
        }
    }

下面是C++的做法，就是遍历所有的可能性，**注意可能出现极端情况，所以这里使用了long double 来计算极端情况的斜率值**

**pointMax设置为1是为了处理所有的点全部相同的情况，别的都好处理**

代码如下：

#include <iostream>
    #include <climits>
    #include <map>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    /*
    struct Point 
    {
         int x;
         int y;
         Point() : x(0), y(0) {}
         Point(int a, int b) : x(a), y(b) {}
    };
    */
    
    class Solution
    {
    public:
        int maxPoints(vector<Point>& points) 
        {
            if (points.size() <= 2)
                return points.size();
            int maxRes = 2;
            for (int i = 0; i < points.size(); i++)
            {
                int pointMax = 1, samePoint = 0;
                map<long double, int> count;
                for (int j = i + 1; j < points.size(); j++)
                {
                    if (points[i].x == points[j].x && points[i].y == points[j].y)
                    {
                        samePoint++;
                        continue;
                    }
    
                    long double k = 0;
                    if (points[i].x == points[j].x)
                        k = numeric_limits<double>::max();
                    else
                        k = ((long double)points[i].y - (long double)points[j].y) / ((long double)points[i].x - (long double)points[j].x);
    
                    if (count.find(k) == count.end())
                        count[k] = 2;
                    else
                        count[k] += 1;
                    pointMax = max(pointMax,count[k]);
                }
                maxRes = max(maxRes, pointMax+samePoint);
            }
            return maxRes;
        }
    };