leetcode 149. Max Points on a Line |149. 直线上最多的点数（Java）

今天药忘吃喽~ 2022-09-01 15:43 151阅读 0赞

## 题目 ##

[https://leetcode.com/problems/max-points-on-a-line/][https_leetcode.com_problems_max-points-on-a-line]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

hard 题，普通解法不难，有几个小坑：

*  key : key : value 的存储选型
 *  double 作为 key 时的精度问题（改为用 String 存储 7位精度）
 *  double 的正负 0 问题
 *  double 的正负 Infinite 问题
 *  统计个数 sum 与排列组合 C 的转换  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

class Solution { 
        public int maxPoints(int[][] points) { 
            Map<String, Map<String, Integer>> kMap = new HashMap<>(); // y=kx+b，map存k:b:count
            int max = 0;
            for (int i = 0; i < points.length - 1; i++) { 
                for (int j = i + 1; j < points.length; j++) { 
                    Double deltaY = (double) points[j][1] - points[i][1];
                    Double deltaX = (double) points[j][0] - points[i][0];
                    Double k = deltaY / deltaX;
                    Double b = points[i][1] - k * points[i][0];
                    
                    if (k == 0) k = 0.0; // +0.0 -0.0 统一
                    if (points[i][0] == points[j][0]) {  // +Infinity -Infinity 统一
                        k = null;
                        b = (double) points[i][0];
                    }
                    
                    String sk = String.format("%.7f", k); // string k
                    if (!kMap.containsKey(sk)) { 
                        kMap.put(sk, new HashMap<>());
                    }
                    
                    String sb = String.format("%.7f", b); // string b
                    Map<String, Integer> bMap = kMap.get(sk);
                    if (!bMap.containsKey(sb)) { 
                        bMap.put(sb, 0);
                    }
                    
                    int nb = bMap.get(sb) + 1; // new b
                    bMap.put(sb, nb);
                    max = Math.max(max, nb);
                }
            }
            return (int) ((1 + Math.sqrt(1 + 8 * max)) / 2);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_max-points-on-a-line]: https://leetcode.com/problems/max-points-on-a-line/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/01d5c03252ef4fb5a74558fe72cc7045.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/fb95b85c1df9402a83030f089e50fb36.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/3edef1b81346426a8fe85e1bde651d9a.png