摘要：分子分母同時(shí)除以他們的最大公約數(shù)即可得到最簡(jiǎn)分?jǐn)?shù)，一般求的是兩個(gè)正整數(shù)的。這道題和有可能是，分別表示與軸或軸平行的斜率注意不能同時(shí)為表示同一個(gè)點(diǎn)沒有意義，所以這道題我們規(guī)定取值范圍。

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

O(N^2) 時(shí)間 O(N) 空間， N為點(diǎn)數(shù)

應(yīng)知應(yīng)會(huì)：

平面里確定一條直線要兩個(gè)數(shù)據(jù)，可以是兩個(gè)不同的點(diǎn)(高中數(shù)學(xué)做法)，也可以是一個(gè)點(diǎn)加一個(gè)斜率(這道題做法)

斜率k = (y2 - y1)/(x2 - x1)，當(dāng) x1 == x2 時(shí)，分母為0，斜率為無(wú)窮，表示和y軸平行的直線們

在計(jì)算機(jī)里使用double表示斜率，是不嚴(yán)謹(jǐn)?shù)囊彩遣徽_的，double有精度誤差，double是有限的，斜率是無(wú)限的，無(wú)法使用有限的double表示無(wú)限的斜率，不過(guò)此題的test case沒有涉及這個(gè)問(wèn)題

表示斜率最靠譜的方式是用最簡(jiǎn)分?jǐn)?shù)，即分子分母都無(wú)法再約分了。分子分母同時(shí)除以他們的最大公約數(shù)gcd即可得到最簡(jiǎn)分?jǐn)?shù)

gcd(a,b)，一般求的是兩個(gè)正整數(shù)的gcd。這道題a和b有可能是0，分別表示與x軸或y軸平行的斜率(注意ab不能同時(shí)為0,表示同一個(gè)點(diǎn)沒有意義)，所以這道題我們規(guī)定ab取值范圍：a>=0,b>=0。至于負(fù)數(shù)，先變成正數(shù)取gcd，再確定最終斜率的正負(fù)

gcd ( a , b ) = (b == 0) ? a : gcd ( b , a % b ), a,b是任意非負(fù)整數(shù)且a,b至少有一個(gè)不為0

觀察gcd(a,b)，假設(shè)a,b為非負(fù)整數(shù)：

a和b中有一個(gè)為零，那么gcd為另一個(gè)不為0的數(shù)；

a和b都為0，gcd為0；

算法：

沒什么算法就是窮舉：
對(duì)每個(gè)點(diǎn)，都計(jì)算一下該點(diǎn)和其他點(diǎn)連線的斜率，這樣對(duì)于這個(gè)點(diǎn)來(lái)說(shuō)，相同斜率的直線有多少條，就意味著有多少個(gè)點(diǎn)在同一條直線上，因?yàn)檫@些直線是相同的。另外，如果計(jì)算過(guò)點(diǎn)A和點(diǎn)B的直線，當(dāng)算到點(diǎn)B時(shí)，就不用再和A連線了，因?yàn)锳B這條直線上的點(diǎn)數(shù)已經(jīng)都計(jì)算過(guò)了。這里，我們用哈希表，以斜率為key，記錄有多少重復(fù)直線。

求gcd的utility:

public int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

兩層循環(huán)外層 i 從 0 到 n, 內(nèi)層 j 從 i+1 到 n

如果想要自定義Slope(斜率)類作為HashMap的Key的話要重寫hashCode()和equals()函數(shù)， 偷懶的話可以把斜率的分?jǐn)?shù)表示成String作為Key，這樣就省了一些事

hashmap的value的含義應(yīng)定義為：過(guò)cur點(diǎn)以key為斜率的直線有幾個(gè)除了cur以外的點(diǎn)。在算完 過(guò)cur的所有直線后，統(tǒng)計(jì)cur點(diǎn)的總個(gè)數(shù)howManyCur，加到當(dāng)前點(diǎn)最多的直線上，即可得到含cur點(diǎn)的最大直線上的點(diǎn)數(shù)

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */

public class Solution {
    public int maxPoints(Point[] points) {
        if (points.length <= 1)
            return points.length;
        int maxUniv = Integer.MIN_VALUE;
        for (int i = 0; i < points.length; i++) {
            Point cur = points[i];
            HashMap map = new HashMap();
            int howManyCur = 1, maxLocal = 0;
            for (int j = i + 1; j < points.length; j++) {   //這里可以從i+1開始，之前的都算過(guò)了
                    Point iter = points[j];
                    if (iter.x == cur.x && iter.y == cur.y) {//同一頂點(diǎn)
                        howManyCur += 1;
                    } 
                    else {          //不同頂點(diǎn)
                        String key = getSlopeInString(cur, iter);
                        //map里存(過(guò)cur點(diǎn),斜率key)代表的直線有多少除了cur的點(diǎn)
                        map.put(key, map.containsKey(key) ? map.get(key) + 1 : 1);
                        maxLocal = Math.max(maxLocal, map.get(key));
                    }
            }
            maxLocal = howManyCur + maxLocal;
            maxUniv = Math.max(maxLocal, maxUniv);
        }
        return maxUniv;
    }
    public String getSlopeInString(Point cur, Point iter) {
        int numerator = iter.y - cur.y;
        int denominator = iter.x - cur.x;
        String sign = getSign(numerator, denominator);
        int gcd = gcd(Math.abs(numerator), Math.abs(denominator));//0和任意一個(gè)非零數(shù)"a"的gcd為"a",0和0的gcd為0,所以斜率為無(wú)窮的情況分母為0
        return sign + Math.abs(numerator)/gcd + "/" + Math.abs(denominator)/gcd;
    }
    //a和b為非負(fù)整數(shù) 且 a和b不同時(shí)為0
    public int gcd(int a, int b) {
        if (b == 0)
            return a;
        else
            return gcd(b, a % b);
    }
    public String getSign(int a, int b) {
        if (a <= 0 && b <= 0 || a >= 0 && b >= 0)
            return "+";
        else 
            return "-";
    }
}