题目来源
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
一开始学渣我连题目都没看懂…看了好一会才知道是给你一堆点坐标，求出在同一条直线上的点数目最多是多少。
直线有四种情况，一种是横的用0表示，一种竖的用1表示，两种斜的对角线分别用2和3表示。然后我的想法是搞一个哈希表，对于每一个点，都把这四种情况在坐标轴上的交点的map加1。最后遍历一下map，看看哪个map的值最大。
比如有个(3, 3)点的话，那就map[(3,0)]，map[(3,1)]++，map[(6,2)]++，map[(0,3)]++。写了如下代码…然后发现自己TM就没看懂题目…
/**
* Definition for a point.
* 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() == 0)
return 0;
map<string, int> m;
int n = points.size();
for (int i=0; i<n; i++) {
int x = points[i].x;
int y = points[i].y;
stringstream n1;
stringstream n2;
stringstream n3;
stringstream n4;
n1 << x;
n2 << y;
n3 << x-y;
n4 << x+y;
m[n1.str()+",0"]++;
m[n2.str()+",1"]++;
m[n3.str()+",2"]++;
m[n4.str()+",3"]++;
}
int res = 0;
map<string, int>::iterator iter;
for (iter=m.begin(); iter!=m.end(); iter++) {
res = max(res, iter->second);
}
return res;
}
};
gg了，不知道怎么做，看看大神们的做法吧。
/**
* Definition for a point.
* 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) {
int n = points.size();
int res = 0;
for (int i=0; i<n; i++) {
unordered_map<long double, int> map;
int duplicate = 0, vertical = 1;
int x1 = points[i].x, y1 = points[i].y;
int local = 1;
for (int j=i+1; j<n; j++) {
int x2 = points[j].x, y2 = points[j].y;
if (x1 == x2) {
if (y1 == y2)
duplicate++;
else
vertical++;
}
else {
long double slope = (long double)(y2 - y1) / (x2 - x1);
map[slope] = (map[slope] == 0) ? 2 : map[slope] + 1;
local = max(local, map[slope]);
}
}
local = max(local+duplicate, vertical+duplicate);
res = max(res, local);
}
return res;
}
};
其实想法很直接，就是对于每一个点，计算另外的点和该点组成的线上有多少个点。然后处理下重复点和与x轴垂直的线的点。另外还得考虑到精度问题，假如用double表示斜率的话有可能会出问题…
比如
94911149/94911150 == 94911150/94911151 # false
94911150/94911151 == 94911151/94911152 # true
94911151/94911152 == 94911152/94911153 # false
这种情况，double尾数52位，精度是15位，有可能会导致出错。用long double的话可以AC，不过这样感觉也不太好，要是数值更大了，那还是会发生问题。
所以呢，得用更安全的办法来表示斜率，那就是pair<int, int>。当然得除下最大公约数，比如(8, 4) and (2, 1)都用(2, 1)表示。
原封不动把代码搬过来了…
class Solution {
public:
int maxPoints(vector<Point>& points) {
map<pair<int, int>, int> slopes;
int maxp = 0, n = points.size();
for (int i = 0; i < n; i++) {
slopes.clear();
int duplicate = 1;
for (int j = i + 1; j < n; j++) {
if (points[j].x == points[i].x && points[j].y == points[i].y) {
duplicate++;
continue;
}
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
int dvs = gcd(dx, dy);
slopes[make_pair(dx / dvs, dy / dvs)]++;
}
maxp = max(maxp, duplicate);
for (auto slope : slopes)
if (slope.second + duplicate > maxp)
maxp = slope.second + duplicate;
}
return maxp;
}
private:
int gcd(int num1, int num2) {
while (num2) {
int temp = num2;
num2 = num1 % num2;
num1 = temp;
}
return num1;
}
};
刷题备受打击，但是还是得继续刷刷刷，不然找不到实习了…
