題目

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

題解

hard 題，普通解法不難，有幾個(gè)小坑：

• key : key : value 的存儲(chǔ)選型
• double 作為 key 時(shí)的精度問(wèn)題（改為用 String 存儲(chǔ) 7位精度）
• double 的正負(fù) 0 問(wèn)題
• double 的正負(fù) Infinite 問(wèn)題
• 統(tǒng)計(jì)個(gè)數(shù) sum 與排列組合 C 的轉(zhuǎn)換
  

class Solution {public int maxPoints(int[][] points) {Map<String, Map<String, Integer>> kMap = new HashMap<>(); // y=kx+b，map存k:b:countint 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 統(tǒng)一if (points[i][0] == points[j][0]) { // +Infinity -Infinity 統(tǒng)一k = null;b = (double) points[i][0];}String sk = String.format("%.7f", k); // string kif (!kMap.containsKey(sk)) {kMap.put(sk, new HashMap<>());}String sb = String.format("%.7f", b); // string bMap<String, Integer> bMap = kMap.get(sk);if (!bMap.containsKey(sb)) {bMap.put(sb, 0);}int nb = bMap.get(sb) + 1; // new bbMap.put(sb, nb);max = Math.max(max, nb);}}return (int) ((1 + Math.sqrt(1 + 8 * max)) / 2);} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 149. Max Points on a Line |149. 直线上最多的点数（Java）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。