LeetCode刷题笔记（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.

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4
Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

题意分析： 

在二维平面中给定n个点，找到同在一条直线上点的数目，并返回最多的共线点数值。

解答如下：

方法一（map方法）

共线一般有分两类情况，第一类斜率相等，但由于斜率△y/△x是除法，△x一旦为0则会出现错误，所以要用最大公约数来分别约减△y、△x，并用map的键按顺序存放约减后的△y、△x，其值为斜率相等共线点的数量。第二类相同的点，对应就是△y=0、△x=0的情况，此时只需通过判断并用额外一个变量记录相同点，最后把两类情况下的共线点数累积求和，并返回最大值即可。

 注：①△y与△x是有顺序之分的，所以只能用map，不能用unordered_map。②用公约数约减法替换除法，避免了出错。

class Solution{
public:
    int maxPoints( vector<Point>& points ){
        int result = 0;
        if (points.size() == 1)     
            return 1;
        for (int i = 0; i < points.size(); i++) {
            map <pair<int,int>, int> record;
            int samepoint =1;                         //每次都需要重新计数
            for (int j = i+1; j < points.size(); j++) {
                //记录相同点的个数
                if ( points[i].x == points[j].x && points[i].y == points[j].y )
                    samepoint++;      
                //记录斜率相同点的个数             
                else{int dx = points[i].x - points[j].x;
                int dy = points[i].y - points[j].y;
                int d = gcd(dx, dy);//不存在dx=dy=0
                record[{dx/d, dy/d}] ++;}
            }
            for ( map <pair<int,int>, int> :: iterator iter = record.begin(); iter != record.end(); iter++) {
                result = max(result, iter -> second + samepoint); //将相同点的个数与斜率相同点的个数进行累积求和得与该点共线的所有点数
            }
            result = max(result, samepoint);
        }

        return result;
    }
//自己定义的求最大公约数的函数
private: int gcd(int a, int b){   
        return  (b == 0) ? a : gcd(b, a%b);
    }
};

提交后的结果如下：

 

方法二（行列式为0法）

由线性代数知识可知，三点共线则必有三点构成的三阶行列式为0。

注：①samepoint用于记录points.size()不足3时，相同点的个数。

②k从0开始循环，sum可以记录下所有共线的点数，包括了相同点，所以这里的samepoint与sum不需要累加

class Solution{
public:
    int maxPoints(vector<Point>& points){
        int result = 0;

        for (int i = 0; i < points.size(); i++) {
            int samepoint = 1;
            long long x1 = points[i].x;
            long long y1 = points[i].y;
            for (int j = i + 1; j < points.size(); j++) {
                int sum = 0;
                long long x2 = points[j].x;
                long long y2 = points[j].y;
                if(points[j].x == points[i].x && points[j].y == points[i].y)
                {   samepoint++;
                    continue;
                 }
                for (int k = 0; k < points.size(); k++) {
                        long long x3 = points[k].x;
                        long long y3 = points[k].y;
                        if(x1*y2 + x3*y1 + x2*y3 - x3*y2 - x1*y3 - x2*y1 == 0)
                            sum ++;
                }
                result = max(result, sum);
            }
            result = max(result, samepoint);
        }
        return result;
    }
};

 

提交后的结果如下：

 

日积月累，与君共进，增增小结，未完待续。