https://leetcode-cn.com/problems/max-points-on-a-line/submissions/

    • 搞一张map， key放的是斜率，value放的是共享这个斜率的点有多少个
    • key用什么类型？ double吗？ 不行，有精度损耗，分子分母约一个最大公约数，然后用字符串 “分子_分母” 的形式表示
      • 为什么要约成最简形式？
        • 因为6/10和3/5虽然是一样的，但是表示成字符串就不一样了6_10, 3_5
    • 或者用两张map
      • image.png
      • 第一Integer是所有的分子， 第二个map中的第一个Integer是分母， 第二个Integer是点数
    • 有单独两类需要单独处理
      • 和我共y的
      • 和我共x的

    image.png

    • 所以最后map里的最优者需要和这两个去pk

    注意，如果数组中有重复点的话，最后pk出来的这个最优者还要加上重复点的个数

    1.  public int maxPoints(int[][] points) {
    2.         if (points == null) {
    3.             return 0;
    4.         }
    5.         if (points.length <= 2) {
    6.             return points.length;
    7.         }
    10.         Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
    11.         int result = 0;
    12.         for (int i = 0; i < points.length; i++) {
    13.             map.clear();
    14.             int samePosition = 1;
    15.             int sameX = 0;
    16.             int sameY = 0;
    17.             int line = 0;
    18.             for (int j = i + 1; j < points.length; j++) {
    19.                 int x = points[j][0] - points[i][0];
    20.                 int y = points[j][1] - points[i][1];
    21.                 if (x == 0 && y == 0) {
    22.                     samePosition++;
    23.                 } else if (x == 0) {
    24.                     sameX++;
    25.                 } else if (y == 0) {
    26.                     sameY++;
    27.                 } else {
    28.                     int gcd = gcd(x, y);
    29.                     x /= gcd;
    30.                     y /= gcd;
    31.                     if (!map.containsKey(x)) {
    32.                         map.put(x, new HashMap<>());
    33.                     }
    34.                     if (!map.get(x).containsKey(y)) {
    35.                         map.get(x).put(y, 0);
    36.                     }
    37.                     map.get(x).put(y, map.get(x).get(y) + 1);
    38.                     line = Math.max(line, map.get(x).get(y));
    39.                 }
    40.             }
    41.             result = Math.max(result, Math.max(Math.max(sameX, sameY), line) + samePosition);
    42.         }
    43.         return result;
    44.     }
    46.     public int gcd(int a, int b) {
    47.         return b == 0 ? a : gcd(b, a % b);
    48.     }