問題描述：
給定一個二維平面存炮，平面上有 n 個點梦染，求最多有多少個點在同一條直線上吱肌。
示例 1:
輸入:
[[1,1],[2,2],[3,3]]
輸出:
3
解釋:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
示例 2:
輸入:
[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
輸出:
4
解釋:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
思路：
尋找以某一點為起始點的斜率马靠，如果斜率相同的有幾個點是共線的，所以遍歷所有點作為起始點氢橙，計算起始點之后的點的斜率（之前的不用計算因為是重復(fù)的），放進map中恬偷，map的鍵是斜率悍手，值是點的個數(shù)。主要注意兩點問題：
使用double作為斜率的表達可能會因為精度問題導(dǎo)致不同的斜率算出的結(jié)果一樣袍患，而且注意double類型有0.0和-0.0坦康，infinite和-infinite的差別，存入map可能會出錯诡延，所以采用分?jǐn)?shù)轉(zhuǎn)成字符串進行表達滞欠。分?jǐn)?shù)的計算可以采用歐幾里得算法算出最大公約數(shù)，然后分子分母分別除以最大公約數(shù)肆良，拼裝成字符串作為map的鍵仑撞。
要注意存在坐標(biāo)與起始點相同的點，這樣的點會造成所有共線的點數(shù)要增加妖滔，注意處理隧哮。
代碼：
import java.util.*;
class Point {
int x;
int y;
Point() { x = 0; y = 0; }
Point(int a, int b) { x = a; y = b; }
}
public class Solution {
// 歐幾里得算法求最大公約數(shù)
public int gcd(int a, int b){
if (b == 0) return a;
return gcd(b,a%b);
}
public int maxPoints(Point[] points) {
if (points.length == 0) return 0;
int res = 0;
for (int i=0; i<points.length; i++){
HashMap<String, Integer> kMap = new HashMap();
int same = 1;// same用于保存與初始點坐標(biāo)相同的點的個數(shù)（包括初始點）
for (int j=i+1; j<points.length; j++) {
// 坐標(biāo)相同就把same++
if (points[i].x == points[j].x &&
points[i].y == points[j].y) {
same++;
} else {
int dy = points[j].y - points[i].y;
int dx = points[j].x - points[i].x;
int maxD = gcd(dx, dy);
// 將最簡分?jǐn)?shù)作為key
String key = dy/maxD + "/" + dx/maxD;
if (kMap.containsKey (key)) {
kMap.put(key, kMap.get(key) + 1);
} else {
kMap.put(key, 1);
}
}
}
int count = 0; // count統(tǒng)計不同斜率點的個數(shù)
for (Map.Entry<String, Integer> entry : kMap.entrySet()){
if (entry.getValue() > count){
count = entry.getValue();
}
}
// res存共線點個數(shù)的最大值
res = Math.max(res, count + same);
}
return res;
}
}
