題意

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

意思就是說在給定的節點中計算出在同一條直線上的最大節點個數。

思路

這道題，題意很容易理解，但是需要注意的東西包括，如果你用斜率計算，那么就需要注意到精確度的問題，否則就會變成相等的斜率，無奈之下，只能提高精確度，比如說用long double，但這不是持久的辦法，目前的辦法是使用最大公約數。

其實我大概的思路已經想到了，就是第五種方法的思路，這道題沒做出來的原因是，沒有考慮到相同點以及相同的x的情況。

代碼

#include <stdio.h> #include <stdio.h> #include <string> #include <vector> #include <iostream> #include <unordered_map> #include <map> #include <set> using namespace std;/*** Definition for a point.*/ struct Point {int x;int y;Point() : x(0), y(0) {}Point(int a, int b) : x(a), y(b) {} };/*** 第一種方法：將每一個頂點和其他的頂點進行計算得出斜率，* 用hash保存下來，key為斜率，value為總個數* 因為相同斜率的則在同一條線上** @param points <#points description#>** @return <#return value description#>*/ int maxPoints(vector<Point>& points) {unordered_map<int, int> hash;int maxCnt = 0;auto caculateK = [&](Point p1, Point p2) {int k = (p2.y - p1.y)/(p2.x - p1.x);return k;};for (int i = 0; i < points.size(); i++) {Point pointA = points[i];for (int j = 0; j < points.size() && i != j; j++) {Point pointB = points[j];int k = caculateK(pointA, pointB);if (hash.find(k) != hash.end()) {hash[k]++;}else {hash.insert(make_pair(k, 1));}}// hash.clear();}for (auto itr = hash.begin(); itr != hash.end(); itr++) {maxCnt = std::max((*itr).second, maxCnt);}return maxCnt + 2; }/*** 計算最大公約數*/ int GCD(int a, int b) {if(b==0) return a;else return GCD(b, a%b); }/*** 這個方法不再是使用斜率作為map的key，而是使用的是gcd(最大公約數)* 總之結果就是overlap＋localmax＋vertical＋1，* 其中overlap代表的是完全相同的頂點，vertical代表的是只有x是相等的，因為相減會導致0** @param points <#points description#>** @return <#return value description#>*/ int maxPoints2(vector<Point>& points) {if (points.size() < 2) {return (int)points.size();}int result = 0;for (int i = 0; i < points.size(); i++) {map<pair<int, int>, int> lines;int localmax = 0, overlap = 0, vertical = 0;for (int j = i+1; j < points.size(); j++) {// 相同的點的個數if (points[j].x == points[i].x && points[j].y == points[i].y) {overlap++;continue;}else if (points[j].x == points[i].x) {vertical++;}else {int a=points[j].x-points[i].x, b=points[j].y-points[i].y;int gcd=GCD(a, b);a/=gcd;b/=gcd;lines[make_pair(a, b)]++;localmax=std::max(lines[make_pair(a, b)], localmax);}localmax=std::max(vertical, localmax);}// 結果為result = std::max(result, localmax+overlap+1); //這里加一是因為之前vertical只計算了一次}return result; }// 由于精確度問題，更改double inline bool double_equal(double a, double b) { return abs(a-b) < 1e-10; } inline bool double_less (double a, double b) { return a-b < -1e-10; }struct Line {double r; // ratio ; slopedouble t; // translationLine(Point p, Point q) { // mathif (q.x == p.x) r = 1e20, t = p.x;else{r = (double) (q.y-p.y) / (double) (q.x-p.x);t = p.y - p.x * r;}} };// 用作排序 bool operator < (const Line& a, const Line& b) {return a.r == b.r ? a.t < b.t : a.r < b.r; }// 依此來判斷map中是否相等 bool operator == (const Line& a, const Line& b) {return a.r == b.r && a.t == b.t; }/*** 這個思路最大的特點就是利用了一個結構體和set的原理* 因為set可以自動去除掉重復的元素** @param points <#points description#>** @return <#return value description#>*/ int maxPoints4(vector<Point> &points) {if (points.empty()) return 0;map<Line, set<Point*> > line_map;for (auto & a : points)for (auto & b : points){Line line(a,b);line_map[line].insert(&a);line_map[line].insert(&b);}int ret = 1;for (auto & pr : line_map) ret = max(ret,(int)pr.second.size());return ret; }/*** 最直接最簡單的做法** @param points <#points description#>** @return <#return value description#>*/ int maxPoints5(vector<Point>& points) {if(points.empty())return 0;else if(points.size() == 1)return 1;int ret = 0;for(int i = 0; i < points.size(); i ++){//start pointint curmax = 1; //points[i] itselfunordered_map<long double, int> kcnt; // slope_k countint vcnt = 0; // vertical countint dup = 0; // duplicate added to curmaxfor(int j = 0; j < points.size(); j ++){if(j != i){long double deltax = points[i].x - points[j].x;long double deltay = points[i].y - points[j].y;if(deltax == 0 && deltay == 0) {dup ++;}else if(deltax == 0){if(vcnt == 0)vcnt = 2;elsevcnt ++;curmax = max(curmax, vcnt);}else{long double k = deltay / deltax;if(kcnt[k] == 0)kcnt[k] = 2;elsekcnt[k] ++;curmax = max(curmax, kcnt[k]);}}}ret = max(ret, curmax + dup);}return ret; }int main(int argc, const char * argv[]) {vector<Point> points;Point point1(0, 0), point2(94911151, 94911150), point3(94911152, 94911151), point4(5, 6);points.push_back(point1);points.push_back(point2);points.push_back(point3);int result = maxPoints5(points);cout << "result..." << result << endl;return 0; }

轉載于:https://www.cnblogs.com/George1994/p/6376531.html

總結

以上是生活随笔為你收集整理的[LeetCode] Max Points on a Line 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。