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

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

题目

https://leetcode.com/problems/max-points-on-a-line/
在这里插入图片描述

题解

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

key : key : value 的存储选型
double 作为 key 时的精度问题（改为用 String 存储 7位精度）
double 的正负 0 问题
double 的正负 Infinite 问题

统计个数 sum 与排列组合 C 的转换
在这里插入图片描述

class Solution {

public int maxPoints(int[][] points) { 
    Map<String, Map<String, Integer>> kMap = new HashMap<>(); // y=kx+b，map存kcount
    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);
}