2014
11-19

# LeetCode-Max Points on a Line[模拟]

### 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.

// LeetCode, Max Points on a Line
// 暴力枚举法，以边为中心，时间复杂度O(n^3)，空间复杂度O(1)
class Solution {
public:
int maxPoints(vector<Point> &points) {
if (points.size() < 3) return points.size();
int result = 0;

for (int i = 0; i < points.size() - 1; i++) {
for (int j = i + 1; j < points.size(); j++) {
int sign = 0;
int a, b, c;
if (points[i].x == points[j].x) sign = 1;
else {
a = points[j].x - points[i].x;
b = points[j].y - points[i].y;
c = a * points[i].y - b * points[i].x;
}
int count = 0;
for (int k = 0; k < points.size(); k++) {
if ((0 == sign && a * points[k].y == c +  b * points[k].x) ||
(1 == sign&&points[k].x == points[j].x))
count++;
}
if (count > result) result = count;
}
}
return result;
}
};


// LeetCode, Max Points on a Line
// 暴力枚举，以点为中心，时间复杂度O(n^2)，空间复杂度O(n)
class Solution {
public:
int maxPoints(vector<Point> &points) {
if (points.size() < 3) return points.size();
int result = 0;

unordered_map<double, int> slope_count;
for (int i = 0; i < points.size()-1; i++) {
slope_count.clear();
int samePointNum = 0; // 与i重合的点
int point_max = 1;    // 和i共线的最大点数

for (int j = i + 1; j < points.size(); j++) {
double slope; // 斜率
if (points[i].x == points[j].x) {
slope = std::numeric_limits<double>::infinity();
if (points[i].y == points[j].y) {
++ samePointNum;
continue;
}
} else {
slope = 1.0 * (points[i].y - points[j].y) /
(points[i].x - points[j].x);
}

int count = 0;
if (slope_count.find(slope) != slope_count.end())
count = ++slope_count[slope];
else {
count = 2;
slope_count[slope] = 2;
}

if (point_max < count) point_max = count;
}
result = max(result, point_max + samePointNum);
}
return result;
}
};


Java代码:

/**
* Definition for a point.
* class Point {
*     int x;
*     int y;
*     Point() { x = 0; y = 0; }
*     Point(int a, int b) { x = a; y = b; }
* }
*/
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;
public class Solution {
public static int maxPoints(Point[] points) {
if(points.length == 0) return 0;
HashMap<Double,Integer> map = new HashMap<Double,Integer>();
int ans = 1;
for (int i = 0; i < points.length; i++) {
map.clear();
int tmp = 1;
int de = 0;
for (int j = 0; j < points.length; j++) {
if(j == i) continue;
if(points[i].x == points[j].x && points[i].y == points[j].y){
de++;
continue;
}
double d = d(points[i], points[j]);
Integer cnt = map.get(d);
if(cnt == null)
map.put(d, 2);
else map.put(d, cnt+1);
}
Set<Entry<Double, Integer>> entrySet =  map.entrySet();
for(Entry<Double, Integer> e:entrySet){
if(tmp <e.getValue())
tmp = e.getValue();
}
if(ans < tmp+de) ans = tmp+de;
}

return ans;
}

static double d(Point p1,Point p2){
if((p1.y-p2.y) == (p1.x-p2.x)) return 1;
return (p1.y-p2.y)*1.0/(p1.x-p2.x);
}
}

1. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧

2. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

3. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。