leetcode-149-直线上最多的点数

这是我参与更文挑战的第2天，活动详情查看：更文挑战

[博客链接]

[题目描述]

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。 



 示例 1： 


输入：points = [[1,1],[2,2],[3,3]]
输出：3


 示例 2： 


输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4




 提示： 


 1 <= points.length <= 300 
 points[i].length == 2 
 -10^4 <= xi, yi <= 10^4
 points 中的所有点 互不相同 

 Related Topics 几何 哈希表 数学 
 ? 275 ? 0

复制代码

[题目链接]

leetcode题目链接

[github地址]

代码链接

[思路介绍]

思路一：hash + 枚举

枚举每条线路的斜率k和截距b，通过double进行记录(考虑斜率不为整型的情况)
考虑水平线和竖直线，水平线斜率为0，不影响运算，竖直线因为斜率为最大值，我们用Integet.MAXVALUE进行替代
然后通过斜率+截距作为map的key，然后value为节点索引，最后索引+1即为在这条直线上的节点数
因为有可能有**斜率为负数0（-0.0）**的情况所以需要对这种特殊情况做个判断
当节点数小于2的时候，根据公理，两点能确定一条直线可以直接返回节点数

        public int maxPoints(int[][] points) {
            //corner case
            if (points.length <=2){
                return points.length;
            }
            int max = 2;
            for (int i = 0; i < points.length; i++) {
                Map<String, List<Integer>> map = new HashMap<>();
                for (int j = i + 1; j < points.length; j++) {
                    //水平和垂直线（）
                    double k = (points[i][0] - points[j][0]) == 0 ? Integer.MAX_VALUE : (double)(points[i][1] - points[j][1]) / (points[i][0] - points[j][0]);
                    double b = k == Integer.MAX_VALUE ? Integer.MAX_VALUE : (points[i][1] - k * points[i][0]);

                    String key = k == (-0.0)? "0.0":k + "," + b;
                    List<Integer> list = map.getOrDefault(key, new ArrayList<>());
                    list.add(j);
                    map.put(key, list);
                }
                for (Map.Entry<String, List<Integer>> entry : map.entrySet()
                ) {
                    max = Math.max(max, entry.getValue().size() + 1);
                }
            }

            return max;
        }
复制代码