1、題目

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

2、解法

2.1、自己的解法：

/**
 * 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;
class PointAndK{
    int x;
    int y;
    double k;
    PointAndK(int a,int b,double c){
        x = a;y = b;k = c;
    }
}
public class Solution {
    public int maxPoints(Point[] points) {
        HashMap<Integer,Integer> horizontal = new HashMap<>();
        HashMap<Integer,Integer> vertical = new HashMap<>();
        HashMap<PointAndK,Integer> other = new HashMap<>();
        for(Point point:points){
            horizontal.put(point.y,0);
            vertical.put(point.x,0);
        }
        for(int i = 0;i<points.length;i++){
            for(int j = 0;j<points.length&&i!=j;j++){
                int x = points[i].x-points[j].x;
                int y = points[i].y-points[j].y;
                if(x!=0 && y!= 0){
                    double k = y*1.0/x;
                    other.put(new PointAndK(points[i].x,points[i].y,k),0);
                }
            }
        }
        for(PointAndK p:other.keySet()){
            for(Point point:points){
                int x = p.x-point.x;
                int y = p.y-point.y;
                if(x!=0&&y!=0){
                    double k = y*1.0/x;
                    if(Double.doubleToLongBits(k) == Double.doubleToLongBits(p.k)){
                        int val = other.get(p);
                        other.put(p,val+1);
                    }
                }else if(x == 0 && y == 0){
                    int val = other.get(p);
                    other.put(p,val+1);
                }
            }
        }
        for(Point point:points){
            int v1 = horizontal.get(point.y);
            horizontal.put(point.y,v1+1);
            int v2 = vertical.get(point.x);
            vertical.put(point.x,v2+1);
        }
        int result1 = getMaxCount(horizontal);
        int result2 = getMaxCount(vertical);
        int result3 = 0;
        for(PointAndK p:other.keySet()){
            if(other.get(p)>result3){
                result3 = other.get(p);
            }
        }
        return Math.max(result1,Math.max(result2,result3));
    }
 
    public int getMaxCount(HashMap<Integer,Integer> map) {
        int result = 0;
        for (Integer key : map.keySet()) {
            if (map.get(key) > result) {
                result = map.get(key);
            }
        }
        return result;
    }
     
     
}

2.2、別人的解法

public class Solution {
    public int maxPoints(Point[] points) {
        //關(guān)鍵在于判斷三點共線，兩平行直線有且只有一個交點，所以有一個中間點，這個中間點與另外兩個端點的連線的斜率相等
        //由比率的性質(zhì)
        int ABx;
        int ABy;
        int BCx;
        int BCy;

        if(points.length<=2) return points.length;
        int max=2;//用來記錄最大個數(shù)

        for(int i=0;i<points.length;i++){
            int num=0;
            int temp=1;

            for(int j=i+1;j<points.length;j++){
                ABx=points[i].x-points[j].x;
                ABy=points[i].y-points[j].y;
                if(ABx==0 && ABy==0)//表示出現(xiàn)重復(fù)點
                {
                    num++;
                }else{
                    temp++;
                    for(int k=j+1;k<points.length;k++){
                        BCx=points[j].x-points[k].x;
                        BCy=points[j].y-points[k].y;
                        if(ABx*BCy==BCx*ABy){//表示兩個斜率相等，轉(zhuǎn)化為乘積的形式可以避免分母為0的情況
                            temp++;
                        }
                    }
                }
                if(max<(num+temp)){
                  max=num+temp;
                }
                temp=1;
            }

        }
        return max;
    }
}

筆記上是別人的代碼，這段代碼通過三層for循環(huán)來求解，并且沒有使用hashmap。比自己的答案要精煉很多