Re: [閒聊] 每日LeetCode

看板Marginalman作者pandix (麵包屌)時間2年前 (2023/01/08 23:22)推噓3(3推 0噓 2→)

留言5則, 5人參與討論串185/719 (看更多)

149. Max Points on a Line 平面上有很多點，問你最多能讓幾點共線 Example 1: https://assets.leetcode.com/uploads/2021/02/25/plane1.jpg

Input: points = [[1,1],[2,2],[3,3]] Output: 3 Example 2: https://assets.leetcode.com/uploads/2021/02/25/plane2.jpg

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 思路: 1.對每個點都去算其他點和他的斜率一樣的話就是在同一條線上斜率可以拿來當成 dict 的 key 最後檢查哪個 key 的 value 最高就好自己和自己的斜率最後再扣掉樸實的O(n^2) class Solution: def maxPoints(self, points: List[List[int]]) -> int: res = 0 for p1 in points: slope = defaultdict(int) for p2 in points: if p1[0] - p2[0] != 0: slope[(p1[1] - p2[1]) / (p1[0] - p2[0])] += 1 else: slope[inf] += 1 slope[inf] -= 1 res = max(res, max(slope.values())) return res+1 -- 蛤? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.200.200 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1673191323.A.8B3.html

推

SecondRun

01/08 23:32, 2年前 , 1^F

01/08 23:32, 1^F

→

pandix

01/08 23:33, 2年前 , 2^F

01/08 23:33, 2^F

推

AyuniD

01/09 02:26, 2年前 , 3^F

01/09 02:26, 3^F