编程题—给定位于二维平面上的n个点，求出位于同一条直线上的最大点数

开始拿到这个题的时候，首先就会想到两点确定一条直线，若要判断相应的点是否在同一条直线上，仅需求出它们的斜率即可。

但是此题需注意的几点是：（1）当斜率不存在的情况：即（y2-y1）/（x2-x1）中（x2-x1）为0的情况。

                                           （2）当斜率为0的情况：即（y2-y1）为0的情况。

                                           （3）最后需要注意的就是此题有一入坑点就是对斜率的存，一般我们可能会想到用double类型来存斜率，但是double类型也有精度不准的几率，导致程序出错，所以在此我选择了用最大公约数（最大公因子）gcd来使用分数来代替斜率(此时需要保证分子分母最简)。

                                              即使用一个Map<Integer, Map<Integer, Integer>> map = new HashMao<>();

其中第一个Integer代表的是（x2-x1）/gcd, 即分母；内嵌的key代表的是（y2-y1）/gcd,即分子；value代表的是出现次斜率的次数。

                                              其中需要一个在每一次外部遍历时记录一个特殊情况计数器，即overLop.

 

---

import java.util.Map;
import java.util.HashMap;
/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
/*
    给定位于二维平面上的n个点，求出位于同一条直线上的最大点数
    思路：(1)位于同一直线上即就是斜率相同，用一个hashmap记录下斜率和点数量的映射关系；
         （2）特殊情况：两个点重合
*/
public class Solution {
    public int maxPoints(Point[] points) {
       if(points == null){
           return 0;
       }
        if(points.length <=2 ){
            return points.length;
        }
        
        Map<Integer, Map<Integer,Integer>> map = new HashMap<>();
        //设置最终的结果
        int res = 0;
        //设置每一轮比较后的最大值
        int max = 0;
          
        for(int i=0;i<points.length-1;i++){
            map.clear();
            int overLop=0;//考虑特殊情况
            max = 0;
            
            for(int j=i+1;j<points.length;j++){
                int x = points[j].x - points[i].x;
                int y = points[j].y - points[i].y;
                if(x == 0 && y == 0){
                    overLop++;
                    continue;
                }
                //计算最大公约数
                //想用分数代表斜率，必须保证分子分母最简
                int gcd = generateor(x,y);
                if(gcd != 0){
                    x = x/gcd;
                    y = y/gcd;
                }
                if(map.containsKey(x)){
                    if(map.get(x).containsKey(y)){
                        map.get(x).put(y,map.get(x).get(y)+1);
                    }else{
                        map.get(x).put(y,1);
                    }
                }else{
                    Map<Integer,Integer> temp = new HashMap<>();
                    temp.put(y,1);
                    map.put(x,temp);
                }
                max = Math.max(max, map.get(x).get(y) ); 
            }
            res = Math.max(res, max+overLop+1);
        }
         return res;
    }
        
        private int generateor(int x, int y){//欧几里得算法
            if(y == 0){
                return x;
            }
            return generateor(y, x%y);
        }
}