• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594
            給出一堆二維點,問最多多少個點共線
            O(n2)枚舉兩個點,看一樣斜率的最多多少個點,2014年曾經(jīng)用C++寫過??http://www.shnenglu.com/Uriel/articles/205287.html
            今日在Discussion看到個不錯的思路(??https://leetcode.com/problems/max-points-on-a-line/solutions/3016632/python-3-11-lines-w-explanation-and-example-t-m-95-97/),不需要折騰double型求斜率,因為點的坐標都是int型,可以求兩個點dx,dy,除以GCD之后用dict統(tǒng)計這樣的約簡后的數(shù)對有多少個,因為存的是除以GCD之后的數(shù)對,所以一開始要給所有點按x值從小到大排序,保證單調(diào)增

             1 #149
             2 #Runtime: 77 ms (Beats 92.29%)
             3 #Memory: 13.8 MB (Beats 94.26%)
             4 
             5 class Solution:
             6     def maxPoints(self, points: List[List[int]]) -> int:
             7         points.sort()
             8         ans = 0
             9         for i, (x1, y1) in enumerate(points):
            10             k = defaultdict(int)
            11             for x2, y2 in points[i + 1 :]:
            12                 dx = x2 - x1
            13                 dy = y2 - y1
            14                 g = gcd(dx, dy)
            15                 kk = (dx // g, dy // g)
            16                 k[kk] += 1
            17                 ans = max(ans, k[kk])
            18         return ans + 1
            亚洲欧美精品一区久久中文字幕 | 精品人妻伦九区久久AAA片69| 久久久久人妻一区二区三区vr| 亚洲精品国产美女久久久| 青草国产精品久久久久久| 丁香久久婷婷国产午夜视频| 久久亚洲sm情趣捆绑调教| 久久国产免费直播| 1000部精品久久久久久久久| 久久人与动人物a级毛片| 久久精品无码专区免费青青| 国产精品九九久久精品女同亚洲欧美日韩综合区 | 久久久精品波多野结衣| 看久久久久久a级毛片| 99久久国产综合精品五月天喷水 | 国产精品一区二区久久精品涩爱 | 久久综合九色综合精品| 中文字幕精品久久| 精品久久一区二区三区| 亚洲人成网站999久久久综合| 久久香蕉超碰97国产精品| 精品一久久香蕉国产线看播放| 激情伊人五月天久久综合| 中文国产成人精品久久亚洲精品AⅤ无码精品| 国产亚洲精品久久久久秋霞| 2020久久精品亚洲热综合一本| 久久精品国产免费| 婷婷久久香蕉五月综合加勒比| 日批日出水久久亚洲精品tv| 国产三级观看久久| 久久久久久国产精品无码超碰| 免费精品国产日韩热久久| 亚洲精品国产综合久久一线| 99久久国产综合精品五月天喷水 | 欧美激情精品久久久久久久九九九| 久久99精品九九九久久婷婷| 99久久er这里只有精品18| 亚洲av伊人久久综合密臀性色| 久久国产精品无| AV无码久久久久不卡蜜桃| 久久精品无码一区二区WWW|