149. 直线上最多的点数

暴力做法就是三次遍历：

  1. class Solution {
  2.     public int maxPoints(int[][] ps) {
  3.         int n = ps.length;
  4.         int ans = 1;
  5.         for (int i = 0; i < n; i++) {
  6.             int[] x = ps[i];
  7.             for (int j = i + 1; j < n; j++) {
  8.                 int[] y = ps[j];
  9.                 int cnt = 2;
  10.                 for (int k = j + 1; k < n; k++) {
  11.                     int[] p = ps[k];
  12.                     int s1 = (y[1] - x[1]) * (p[0] - y[0]);
  13.                     int s2 = (p[1] - y[1]) * (y[0] - x[0]);
  14.                     if (s1 == s2) cnt++;
  15.                 }
  16.                 ans = Math.max(ans, cnt);
  17.             }
  18.         }
  19.         return ans;
  20.     }
  21. }

注意，不用除法，直接用乘法，判断斜率是否一样即可。
优化使用hashmap

  1. class Solution {
  2.     public int maxPoints(int[][] ps) {
  3.         int n = ps.length;
  4.         int ans = 1;
  5.         for (int i = 0; i < n; i++) {
  6.             Map<String, Integer> map = new HashMap<>();
  7.             // 由当前点 i 发出的直线所经过的最多点数量
  8.             int max = 0;
  9.             for (int j = i + 1; j < n; j++) {
  10.                 int x1 = ps[i][0], y1 = ps[i][1], x2 = ps[j][0], y2 = ps[j][1];
  11.                 int a = x1 - x2, b = y1 - y2;
  12.                 int k = gcd(a, b);
  13.                 String key = (a / k) + "_" + (b / k);
  14.                 map.put(key, map.getOrDefault(key, 0) + 1);
  15.                 max = Math.max(max, map.get(key));
  16.             }
  17.             ans = Math.max(ans, max + 1);
  18.         }
  19.         return ans;
  20.     }
  21.     int gcd(int a, int b) {
  22.         return b == 0 ? a : gcd(b, a % b);
  23.     }
  24. }