多少个点位于同一直线

import java.util.*;
/**
 * 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 ***(int x, int y){
        if(y==0){
            return x;
        }else{
            return ***(y, x%y);
        }
    }
    public int maxPoints(Point[] points) {
        //corner case
        if(points==null)return 0;
        if(points.length<=2)return points.length;
        
        int maxFinal = 0;
        //每个点
        for(int i=0; i<points.length;i++){
            HashMap<Integer, HashMap<Integer, Integer>> map = new HashMap<>();
            int max = 0;
            int samePoint =0;
            //i点的后面的另外一个j点
            for(int j=i+1; j<points.length;j++){
                //算他们的dx和dy
                int dx = points[j].x-points[i].x;
                int dy = points[j].y-points[i].y;  
                //如果是重合的点
                if(dx==0 &&dy==0){
                    samePoint+=1;
                    //跳出循环，走下一个j点
                    continue;
                }
                //计算最大公因数
                int GCD = ***(dx,dy);
                //简化dx和dy，不需要计算出dx/dy因为不准确，所以简化dx和dy来获得一对dx-dy
                //拥有相同的一对dx-dy，证明点在同一线上
                if(GCD!=0){
                    dx/=GCD;
                    dy/=GCD; 
                }
                
                //contains the x
                if(map.containsKey(dx)){
                   //contains x-y pair, increase by 1
                   if(map.get(dx).containsKey(dy)){
                       map.get(dx).put(dy, map.get(dx).get(dy)+1 );
                   //create new x-y pair  
                   }else{
                       map.get(dx).put(dy,1);
                   }
                    //add new x-y pair 
                }else{
                    HashMap<Integer,Integer> newPair = new HashMap<>();
                    newPair.put(dy,1);
                    map.put(dx,newPair);
                }
                
                //get the max 
                max= Math.max(max,map.get(dx).get(dy));
                
            }
            
            maxFinal = Math.max(maxFinal,max+samePoint+1);
        }
        return maxFinal;
    }
}

public class Solution {
    public int maxPoints(Point[] points) {
         
        if(points.length < 2) {
            return points.length;
        }
         
        int max = 2;
        for(int i = 0; i < points.length - 1; i++) {
            int base = 1;
            for(int j = i + 1; j < points.length; j++) {
                int count = 2;
                if(points[i].x == points[j].x && points[i].y == points[j].y) {
                    base++;
                    max = base > max ? base : max;
                } else {
                    for(int k = 0; k < points.length; k++) {
                        if(k == i || k == j) {
                            continue;
                        }
                        count += isLine(points[i], points[j], points[k]) ? 1 : 0;
                    }
                    max = count > max ? count : max;
                }
                
            }
        }
        return max;
    }
     
    boolean isLine(Point p1, Point p2, Point p3) {
        return (p1.x - p2.x) * p3.y == (p1.y - p2.y) * (p3.x - p2.x) + p2.y * (p1.x - p2.x);
    }
}

题目描述

解题思路

点共线，那么最容易想到的思路就是确定斜率，斜率相同不就共线了。但是还有两点特殊情况需要考虑，二是当两个点重合时，无法确定一条直线，但这也是共线的情况，需要特殊处理。二是斜率不存在的情况，由于两个点(x1, y1)和(x2, y2)的斜率k表示为(y2 - y1) / (x2 - x1)，那么当x1 = x2时斜率不存在，这种共线情况需要特殊处理。这里我对重合的情况，斜率不存在的情况以及斜率为0的情况进行了讨论，因为这比较好处理，所以处理一下斜率为0的没什么问题。最后就是通用情况，代码如下：

class Solution {
    public int maxPoints(Point[] points) {
        if(points == null){
            return 0;
        }
        if(points.length <= 2){
            return points.length;
        }
        Map map = new HashMap();
        int result = 0;
        for(int i=0;i<points.length;i++){
            map.clear();
            int overlap = 0;
            int vertical = 0;
            int horizon = 0;   
            int max = 0;
            double rate = 0.0;
            for(int j=i+1;j<points.length;j++){
                double gapx = new Double(points[i].x) - new Double(points[j].x);
                double gapy = new Double(points[i].y) - new Double(points[j].y);
                if(gapx == 0 && gapy == 0){
                    overlap++;
                    continue;
                }else if(gapx == 0){
                    vertical++;
                    max = Math.max(max,vertical);
                }else if(gapy == 0){
                    horizon++;
                    max = Math.max(max,horizon);
                }else{
                    rate = gapy/gapx;
                    if(map.containsKey(rate)){
                        map.put(rate,map.get(rate)+1);
                    }else{
                        map.put(rate,1);
                    }
                    max = Math.max(max,map.get(rate));
                }
            }
            result=Math.max(result, max+overlap+1);
        }
        return result;
    }
}

虽然可以在牛客上通过，但是这个思路在leetcode上已经不行了，它给的例子是：

Input      [[0,0],[94911151,94911150],[94911152,94911151]]
Output     3
Expected   2

我们注意到，由于精度丢失问题，我们算出来的斜率竟然是一样的了，所以这个程序错误地认为这三个点都共线了。因此错误。那怎么办呢？

代码提交

由于通过斜率来判断共线需要用到除法，而用double表示的双精度小数在有的系统里不一定准确，为了更加精确无误的计算共线，我们应当避免除法，从而避免无线不循环小数的出现，那么怎么办呢，我们把除数和被除数都保存下来，不做除法，但是我们要让这两数分别除以它们的最大公约数，这样例如8和4，4和2，2和1，这三组商相同的数就都会存到一个映射里面，同样也能实现我们的目标。

class Solution {
    public int maxPoints(Point[] points) {
        if(points == null){
            return 0;
        }
        if(points.length <= 2){
            return points.length;
        }
        //key为每个数组除以最大公约数后的结果，比如[8,4],[4,2],[2,1]最后都变成[2,1]存储
        Map,Integer> map = new HashMap();
        int result = 0;
        for(int i=0;i<points.length;i++){
            //每次循环完毕要清空map，否则会把上次统计结果带到下一次循环来
            map.clear();
            //重复个数，自己算重复元素，所以初始元素为1
            int dup = 1;
            int max = 0;
            for(int j=i+1;j<points.length;j++){
                //计算出两者间隔
                int x = points[i].x - points[j].x;
                int y = points[i].y - points[j].y;
                //重合的话就将dup加一
                if(x == 0 && y == 0){
                    dup++;
                    continue;
                }
                //计算最大公约数
                int d = gcd(x, y);
                Map tmpMap = new HashMap();
                tmpMap.put(x/d,y/d);
                //次数
                map.put(tmpMap, map.getOrDefault(tmpMap, 0) + 1);
                //每次都将最大的放到max中，避免最后还要遍历判断map中最大次数
                max = Math.max(max,map.get(tmpMap));
            }
            //最后的结果就是map+dup
            result = Math.max(result,max+dup);
        }
        return result;
    }
    public int gcd(int a, int b) {
        return (b == 0) ? a : gcd(b, a % b);
    }
}

 //比例法  public static int maxPoints2(Point[] points) {  //排除不足3个点的情况  if(points.length <= 2)return points.length;    int max = 2;  for(int i = 0;i < points.length - 1; i++){  for(int j = i + 1;j < points.length; j++){  int count = 2;  //斜率不为无穷  if((points[i].x != points[j].x)){  int m = 0;  double y = 10000.0 * (double)(points[i].y - points[j].y);  double x = 10000.0 * (double)(points[i].x - points[j].x);  while(m < points.length){  if(m != i && m != j){  double y2 = 10000.0 * (double)(points[i].y - points[m].y);  double x2 = 10000.0 * (double)(points[i].x - points[m].x);  if(isEqual(x2 * y, y2 * x)) count++;  }  m++;  }  if(count > max) max = count;  }  //斜率为无穷大  else{  int m = 0;  while(m < points.length){  if(m != i && m != j && points[m].x == points[i].x)  count++;  m++;  }  if(count > max) max = count;  }  }  }  return max;  }

public class maxPoints {    public static class Point {  int x;  int y;  Point() {x = 0;y = 0;}  Point(int a, int b) {x = a;y = b;}  }  public static void main(String[] args) {  // TODO Auto-generated method stub  //Point[] points = {new Point(1,2), new Point(1,3), new Point(2,4), new Point(3,6), new Point(2,6)};  Point[] points = {new Point(3,10), new Point(0,2), new Point(0,2), new Point(3,10)};  System.out.println(maxPoints(points));  }  public static int maxPoints(Point[] points) {  //排除不足3个点的情况  if(points.length <= 2)return points.length;    int max = 2;  for(int i = 0;i < points.length - 1; i++){  for(int j = i + 1;j < points.length; j++){  int count = 2;  //斜率不为无穷  if((points[i].x != points[j].x)){  double k = (double)(points[i].y - points[j].y) / (points[i].x - points[j].x);  double b = points[i].y - points[i].x * k;  int m = 0;  while(m < points.length){  if(m != i && m != j && isEqual(points[m].y, k * points[m].x + b))  count++;  m++;  }  if(count > max) max = count;  }  //斜率为无穷大  else{  int m = 0;  while(m < points.length){  if(m != i && m != j && points[m].x == points[i].x)  count++;  m++;  }  if(count > max) max = count;  }  }  }  return max;  }    //浮点数相等比较  public static boolean isEqual(double x1, double x2){  if((x1 - x2 <= 0.0000001) && (x1 - x2 >= -0.0000001)){  return true;  }else{  return false;  }  }
}

	

import java.util.*;
public class Solution {
    public int maxPoints(Point[] points) {
       if(points.length == 1 || points.length == 0 || points.length==2) {
            return points.length;
        }
        int result=1;
        for(int i=0;i<points.length;i++) {
            int curMax=1,coincide=0;
            Map<String, Integer> slopeMap=new HashMap<String, Integer>();
            String k="";
            for(int j=0;j<points.length;j++) {
                // compute slope between two points
                if(i != j) {
                    // same points
                    if (points[i].x == points[j].x && points[i].y == points[j].y) {
                        coincide++;
                        continue;
                    // vertical
                    }else if (points[i].x == points[j].x) {
                        k = "vertical";
                    }else if (points[i].y == points[j].y) {
                        k = "horizontal";
                    } else{
                        k = computeSlope(points[i], points[j]);
                    }
                    if (slopeMap.containsKey(k)) {
                        slopeMap.put(k, slopeMap.get(k)+1);
                    }else {
                        slopeMap.put(k,2);
                    }
                    curMax =  Math.max(slopeMap.get(k),curMax);
                }
            }
            result = Math.max(result, curMax+coincide);
        }
        return result;

    }
    private String computeSlope(Point p1, Point p2) {
        int x=p1.x-p2.x;
        int y=p1.y-p2.y;
        int gcd=computeGcd(x,y);
        return (y/gcd+"")+"/"+(x/gcd+"");
    }
    private int computeGcd(int m, int n) {
        if (m < n) {
            int temp = m;
            m = n;
            n = temp;
        }
        while (m % n != 0) {
            int temp = m % n;
            m = n;
            n = temp;
        }
        return n;
    }

}

主体方法没什么区别，在存储斜率方面直接用最简分数形式来表示两点之间的斜率，完全避免float引起的精度误差

            ret = Math.max(ret, max + dup);//这里最大值的处理是在循环I中完成的，用一个全局变量Ret保证最终结果的最大性，针对一个固定点选择合适它的最大值就简单多了。我觉得重合Dup初始化为1而不是0是很有必要的。避免出现输入两个相同的点却输出1的错误边界情况发生

public int maxPoints(Point[] points) {
        if (points.length == 0) {
            return 0;
        }
        if (points.length == 1) {
            return 1;
        }
        int max = 0;
        double k = 0.0;// 斜率
        for (int i = 0; i < points.length; i++) {
            Map<Double, Integer> map = new HashMap<Double, Integer>();// 保存斜率和节点数量
            int dup = 0;// 重复的节点
            int tempmax = 1;
            for (int j = i + 1; j < points.length; j++) {
                double x1 = points[j].x - points[i].x;
                double y1 = points[j].y - points[i].y;
                if (x1 == 0 && y1 == 0) {// 重复的节点
                    dup++;
                } else {
                    if (x1 == 0) {// 垂直
                        k = Double.MAX_VALUE;
                    } else if (y1 == 0) {
                        k=0.0;
                    } else {
                        k = 1.0 * (y1 / x1);// 计算斜率
                    }
                    int num;
                    if (map.get(k) != null) {
                        num = map.get(k) + 1;
                    } else {
                        num = 2;
                    }
                    map.put(k, num);
                    tempmax = num > tempmax ? num : tempmax;
                }

            }
            max = (tempmax + dup) > max ? tempmax + dup : max;
        }
        return max;
    }

/**
 * 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) {
        /*
        一、基于的原理:
        A与B在同一条直线上且B与C在同一条直线上,那么若AB与BC同斜率
        则A、B、C三点是否共线即有
        deta(ABx)*deta(BCy)=deta(ABy)*deta(BCx)
        二、算法思想:
        同直线上点的个数为与模板点重合的点数+在模板直线上的点数
        固定模板点，累计与模板点重合的点数
        固定模板直线，累计在模板直线上的点数
        更新最大值
        */
        if (points.length<=2){
            return points.length;
        }else{
            int max=2;
            for(int i=0;i<points.length;i++){
                Point Aitem = points[i];
                int point_num = 1;//累计同直线上不同点的个数，至少存在点A
                int Adup = 0;//与A重合的个数
                for(int j=i+1;j<points.length;j++){
                    Point Bitem = points[j];
                    int ABxdiffer = Bitem.x-Aitem.x;
                    int ABydiffer = Bitem.y-Aitem.y;
                    if (ABxdiffer==0 && ABydiffer==0){
                        //累计与A重合的点数
                        Adup++;
                    }else{
                        //假定A与B同直线
                        point_num++;
                        for(int k=j+1;k<points.length;k++){
                            Point Citem = points[k];
                            int BCxdiffer = Citem.x-Bitem.x;
                            int BCydiffer = Citem.y-Bitem.y;
                            if (ABxdiffer*BCydiffer==ABydiffer*BCxdiffer){
                                //若C与A重合或C与B重合或AB线与BC线重合,
                                //均满足deta(ABx)*deta(BCy)==deta(ABy)*deta(BCx)
                                //则A、B、C三点共线
                                point_num++;
                            }
                        }
                        max = max<(point_num+Adup)?(point_num+Adup):max;
                        point_num = 1;
                    }
                }
                max = max<(point_num+Adup)?(point_num+Adup):max;
            }
            return max;
        }
    }
}

/**
 * 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;
/**
 * 逻辑概述：
 * 通过穷举所有组合，判断共线的最多有几个点。
 * 通过斜率比较，相同的则为共线
 * 斜率采用GCD算法
 */
public class Solution {
    public int maxPoints(Point[] points) {
        int result = 0;
        if (points == null) return result;
        if (points.length <= 2) return points.length;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < points.length; i++) {
            Point a = points[i];
            HashMap<String,Integer> map = new HashMap<>();
            int addIndex = 0;
            //求出所有斜率，相同即为同一条线
            for (int j = 0; j < points.length; j++) {
                if (i == j) continue;
                Point b = points[j];
                if (isSame(a,b)) {
                    addIndex++;
                } else {
                    String tempSlope = slope(a,b);
                    if(map.get(tempSlope) != null) {
                        map.put(tempSlope,map.get(tempSlope) + 1);
                    } else {
                        map.put(tempSlope,1);
                    }
                }
            }
            //同一条线最多点的存入max
            if (map.size() != 0) {
                for (Map.Entry<String,Integer> entry : map.entrySet()) {
                    if ((entry.getValue() + 1 + addIndex) > max) {
                        max = entry.getValue() + 1 + addIndex;
                    }
                }
            } else {
                max = addIndex + 1;
            }
        }
        return max;
    }

    private boolean isSame(Point a,Point b) {
        if ((a.x == b.x) && (a.y == b.y)) {
            return true;
        }
        return false;
    }

    /**
     * 求两个点的斜率
     */
    private String slope(Point a, Point b){
        int ax = a.x;
        int ay = a.y;
        int bx = b.x;
        int by = b.y;
        //flag用于标记正负，true为正，false为负
        boolean flag = true;
        int num1 = ax - bx;
        int num2 = ay - by;
        if (num1 == 0) {
            return "|";
        }
        if (num2 == 0) {
            return "—";
        }
        //同正同负时为正
        if ((num1>0 && num2>0) || (num1<0 && num2<0)) {
            flag = true;
        }else {
            flag = false;
        }
        //将负转换为正
        if (num1 < 0){
            num1 = 0 - num1;
        }
        if (num2 < 0){
            num2 = 0 - num2;
        }

        int ***Num = ***(num1,num2);
        String result = num1/***Num + "/" + num2/***Num;
        if (!flag) {
            result = result + "-";
        }
        return result;
    }

    /**
     * 欧几里德算法，计算两个整数a,b的最大公约数
     */
    private int ***(int num1, int num2) {
        if (num2 == 0) {
            return num1;
        }
        return ***(num2,num1%num2);
    }
} 

public class Solution {
    public int maxPoints(Point[] points) {
        if(points.length<=2)return points.length;
        int result = 0;
        for(int i=0;i<points.length;i++){
            int flag = 0;//用于检测重合点
            for(int j=i+1;j<points.length;j++){
                int num = flag+2;
                int ABx = points[i].x - points[j].x;
                int ABy = points[i].y - points[j].y;
                if(ABx==0&&ABy==0){
                    flag++;
                    if(num>result)result=num;
                    continue;
                }
                for(int k=j+1;k<points.length;k++){
                    int BCx = points[j].x - points[k].x;
                    int BCy = points[j].y - points[k].y;
                    if(ABx*BCy==ABy*BCx)num++;
                }
                if(num>result)result=num;
            }
        }
        return result;
    }
}

/**
相同的点竟然算多个，这一点醉了。。。
利用斜率。具体说是每一个点i，与其前面所有点（0 ~ i-1）的斜率。
如果其中有两个斜率相同，因为它们都经过i，所以它们就在同一条线上。
最后，统计经过每个点有多少最多的相同斜率就找出来了。
*/
import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;
public class Solution {
    public int maxPoints(Point[] points) {
        int length = points.length;
        if(length==0||length==1||length==2)return length;
        float gradients[][] = new float[length][length];
        Map<Float,Integer> map[] = new Map[length];
        int sames[] = new int[length];
        for(int i=0;i<length;++i){
            float tmp;
            map[i]=new HashMap<Float, Integer>();
            for(int j=0;j<=i;++j){
                if(j==i)gradients[i][j]=tmp=Float.MAX_VALUE;      //代表两个点相同
                else{
                	if(points[i].x==points[j].x) {
                		if(points[i].y == points[j].y) {
                			sames[i]++;    // 代表点i前面i-1个点中有多少个相同的点
                			gradients[i][j]=tmp=Float.MAX_VALUE;
                		}
                		else gradients[i][j]=tmp=Float.MIN_VALUE;    //代表斜率为无穷
                	}
                	else gradients[i][j]=tmp=(float)(points[i].x-points[j].x)/ (float)(points[i].y-points[j].y);
                }
                if(tmp!=Float.MAX_VALUE){
                    Integer t = map[i].get(tmp);
                    if(t==null)t=0;
                    map[i].put(tmp,t+1);
                }
            }
        }
        
        int bigest=0;
        for(int i=0;i<length;++i){
        	int same=sames[i];
        	if(same>bigest){
        		bigest=same;
        	}
            for ( int m : map[i].values()){
            	if(m==Float.MAX_VALUE)continue;
            	int tmp = m+same;
                if (tmp >bigest)
                    bigest=tmp;
            }
        }
        return bigest+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; }
 * }
 */
//在一个2D平面上有N个点，然后寻找在一条直线上的最大点的个数
//解法：
//穷举，按照斜率相等去计算：斜率相等则说明2个点在一条直线上
import java.util.*;

public class Solution {
    public int maxPoints(Point[] points) {
        if(points == null||points.length == 0){
            return 0;
        }
        if(points.length <= 2){
            return points.length;
        }
        //float为斜率，int为该斜率下的node的个数
        HashMap<Float,Integer> hashMap =  new HashMap<Float,Integer>();
        //定义同一直线上的node的最大值
        int maxCount = 0;
        for(int i = 0;i < points.length;i++){
            hashMap.clear();
            //用于统计重复点的个数，初试为1（将现在正遍历的node计算进去）
            int duplicate = 1;
            for(int j = 0;j < points.length;j++){
                if(i == j){
                    continue;
                }
                if(points[i].x == points[j].x && points[i].y == points[j].y){
                    //遇到重复的node，则也计算进同一条直线中的node
                    ++ duplicate;
                    continue;
                }
                //计算斜率
                float k = (float)(points[i].y - points[j].y)/(points[i].x - points[j].x);
                //保存记录
                if(hashMap.containsKey(k)){
                    hashMap.put(k,hashMap.get(k)+1);
                }else{
                    hashMap.put(k,1);
                }
            }
            //遍历hashMap，得到node个数的最大值
            if(hashMap.size()==0){
                maxCount = duplicate;
            }else{
                Iterator iter = hashMap.entrySet().iterator();
            	while(iter.hasNext()){
                	Map.Entry entry = (Map.Entry) iter.next();
                	Integer val = (Integer)entry.getValue();
                	if(val+duplicate > maxCount){
                    	maxCount = val+duplicate;
                	}
            	}
            }
        }
        return maxCount;
    }
}