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

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

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;
    }
};