java:共线上的点

傷城~ 2022-06-17 04:10 169阅读 0赞

【题目描述】：Given n points on a 2D plane, find the maximum number of points that lie on the same straight line  
在一个二维平面上有n个点，求出现在同一直线上的点的最大个数

> 在此之间，我还去学了一下HashMap  
> 是Map接口的常用实类  
> 创建一个HashMap:  
> HashMap<键的数据类型（如Integer，Double，String…），值的数据类型（如Integer，Double，String…）  
> Map更新方法:clear()、put()、remove()  
> 返回Map的方法：  
> entrySet（）：返回Map中所包含映射的set视图，set中的每个每个元素都是Map.Entry对象  
> keySet():返回Map中所包含【键】的视图、删除set中的元素还将删除Map中相应映射  
> values():返回Map中包含值的【collection】的视图

//有误！测试案例不能完全通过
    package leetcode;
    import java.awt.Point;
    import java.util.*;
    public class Point_line {
        /* * 哈希集合：存放斜率和直线上点的个数 * 穷举法：找一个固定点，向后按个来求他们之间的斜率 * 斜率相同就放进哈希的key里 * 注意事项： * 1.只有一个到两个点的情况：返回点的个数 * 2.有两点重合的情况，设一个变量，存放重合点的个数 * 案例：point={ {1,1},{1,1},{2,2},{2,3}} * 3.在纵坐标相等的情况下(y1-y2)=0 * 即斜率不存在：此时斜率用Int的最大值表示 * 4.考虑数组中全是重合的点 */
    
        public int maxPoints(Point[] point){
            /*//点小于3个，那么就只有一条直线*/
            if(point.length<3){
                return point.length;
            }
            int count=0;
            /*点大于三个的情况*/
            HashMap<Double,Integer>hm = new HashMap<Double,Integer>();
            for(int i=0;i<point.length;i++){
                hm.clear();
                int same=1;
    
                Point cur=point[i];
    
                for(int j=1;j<point.length;j++){
                 double slope=0.0;
                 Point next=point[j];
                //考虑重合的点
                 if(cur.x==next.x&&cur.y==next.y){
                    same++;
                    continue;
                 }else if(cur.x==next.x){
       //在同一竖线上
    
                    slope=Integer.MAX_VALUE;//设为int的最大值
                }
                 else{
       //正常情况下求斜率
                     slope=1.0*((cur.y-next.y)/(cur.x-next.x));
                 }
                    /*把斜率和点数存进哈希表,判断哈希里是否已有这个斜率 *有，就+1； *没有就加进去，并把值设为1 */
                    hm.put(slope,hm.containsKey(slope)?hm.get(slope)+1:1);
      /* for(double key:hm.keySet()){ System.out.println(i+"\t"+j+"\t"+hm.get(key)+"\t"+same);*/
                       }
    
                    }
                   if(hm.keySet().size()==0){
       //如果max为空,考虑point数组全是重复的点
                       count=same>count?same:count;
                   }else{
                       for(double key:hm.keySet()){
                         count= Math.max(same+hm.get(slope),count);
                       }
                   }
    
                }
             return count;
    
        }
    
        public static void main(String[] args){
            //此处省略
    
        }
    }

写完之后。。。报错了

> 不通过 您的代码已保存 答案错误:您提交的程序没有通过所有的测试用例 case通过率为19.23%
> 
> 测试用例: \[(0,0),(1,1),(1,-1)\]
> 
> 对应输出应该为:
> 
> 2
> 
> 你的输出为:
> 
> 3

为什么呢？代码哪里会有错呢？  
后来发现自己写的双循环判断条件不对

而且为什么结果会是3？

//用这段代码来测试一下
       for(double key:hm.keySet()){
                         System.out.println(i+"\t"+j+"\t"+hm.get(key)+"\t"+same);
        public static void main(String[] args){
    
          Point_line p=new Point_line();
          Point[] point=null;
          point=new Point[]
          {
          new Point(0,0),new Point(1,1),new Point(1,-1)
          };
          System.out.println(p.maxPoints(point));
        }
     得出的结果：
    i   j  点数 重合点数
    0   1   1   1
    0   2   1   1
    0   2   1   1
    1   2   1   2
    2   1   1   1
    3

<table> 
 <tbody> 
  <tr> 
   <td>point[i]</td> 
   <td>point[j]</td> 
   <td>same</td> 
   <td>备注</td> 
  </tr> 
  <tr> 
   <td>(0,0)</td> 
   <td>(1,1)</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>(0,0)</td> 
   <td>(1,-1)</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>(0,0)</td> 
   <td>(1,-1)</td> 
   <td>1</td> 
   <td>为什么这里会有打印两次，因为此时的hm.keySet().size()=2,所以打印了两遍</td> 
  </tr> 
  <tr> 
   <td>(1,1)</td> 
   <td>(1,1)</td> 
   <td>1+1=2</td> 
   <td>因为j从1开始，又points[1]和points[j]重合，所以continue跳出循环，就是因为重合，所以same++,导致出了错</td> 
  </tr> 
  <tr> 
   <td>(1，1)</td> 
   <td>(1,-1)</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>(1,-1)</td> 
   <td>(1,1)</td> 
   <td>1</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

> 所以！！！之前的循环判断是错的！

for(int i=0;i<points.length;i++){
    
     for（int j=1;points.length;j++){
     //当i=1,2时，根本没有与第一个点作比较
    }
    
    }

**正确循环判断**

for(int i=0;i<points.length;i++){
    
     for（int j=0;points.length;j++){
      if(i==j)continue;//如果是自己就跳出循环
    }
    
    }

**正解**

import java.awt.Point;
    import java.util.*;
    public class Solution {
        /* * 哈希集合：存放斜率和直线上点的个数 * 穷举法：找一个固定点，向后按个来求他们之间的斜率 * 斜率相同就放进哈希的key里 * 注意事项： * 1.只有一个到两个点的情况：返回点的个数 * 2.有两点重合的情况，设一个变量，存放重合点的个数 * 案例：point={ {1,1},{1,1},{2,2},{2,3}} * 3.在纵坐标相等的情况下(y1-y2)=0 * 即斜率不存在：此时斜率用Int的最大值表示 * 4.考虑数组中全是重合的点 */
    
        public int maxPoints(Point[] point){
            /*//点小于3个，那么就只有一条直线*/
            if(point.length<3){
                return point.length;
            }
            int count=0;
            /*点大于三个的情况*/
            HashMap<Double,Integer>hm = new HashMap<Double,Integer>();
            for(int i=0;i<point.length;i++){
                hm.clear();
                int same=1;
    
                Point cur=point[i];
    
                for(int j=0;j<point.length;j++){
                if(i==j)continue;
                 double slope=0.0;
                 Point next=point[j];
                //考虑重合的点
                 if(cur.x==next.x&&cur.y==next.y){
                    same++;
                    continue;
                 }else if(cur.x==next.x){
       //在同一竖线上
    
                    slope=Integer.MAX_VALUE;//设为int的最大值
                }
                 else{
       //正常情况下求斜率
                     slope=1.0*((cur.y-next.y)/(cur.x-next.x));
                 }
                    /*把斜率和点数存进哈希表,判断哈希里是否已有这个斜率 *有，就+1； *没有就加进去，并把值设为1 */
                    hm.put(slope,hm.containsKey(slope)?hm.get(slope)+1:1);
    
    
                }
    
                   if(hm.keySet().size()==0){
       //如果max为空,考虑point数组全是重复的点
                       count=same>count?same:count;
                   }else{
                       for(double key:hm.keySet()){
                         count= Math.max(same+hm.get(key),count);
                       }
                   }
    
                }
    
             return count;
    
        }
    
        public static void main(String[] args){
    
          Point_line p=new Point_line();
          Point[] point=null;
          point=new Point[]
          {
          new Point(0,0),new Point(1,1),new Point(1,-1)
          };
          System.out.println(p.maxPoints(point));
        }
    }