国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LintCode] Max Points on a Line

bingo / 1417人閱讀

摘要：兩次循環(huán)對中第個和第個進行比較設置重復點數，相同斜率點數。內部循環(huán)每次結束后更新和點相同斜率的點的最大數目。外部循環(huán)每次更新為之前結果和本次循環(huán)所得的較大值。重點一以一個點為參照求其他點連線的斜率，不需要計算斜率。

Problem

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example

Given 4 points: (1,2), (3,6), (0,0), (1,3).
The maximum number is 3.

Note

建立一個斜率對應point個數的HashMap。
兩次循環(huán)對points中第i個和第j個進行比較：
設置重復點數duplicate，相同斜率點數count。內部循環(huán)每次結束后更新count——和點i相同斜率的點的最大數目。（點i可能有很多相同斜率點的集合，故內層遍歷完之后取最大的集合的大小。）
外部循環(huán)每次更新res為之前結果和本次循環(huán)所得duplicate+count的較大值。
重點一：以一個點為參照求其他點連線的斜率，不需要計算斜率。
重點二：兩次循環(huán)體現重點一中的相對關系，可以讓j從i開始，節(jié)省時間。

Solution 
public class Solution {
    public int maxPoints(Point[] points) {
        // Write your code here
        int res = 0;
        if (points == null || points.length == 0) {
            return 0;
        }
        for (int i = 0; i < points.length; i++) {
            int count = 0;
            int duplicate = 1;
            Map map = new HashMap();
            Point p = points[i];
            for (int j = i; j < points.length; j++) {
                Point q = points[j];
                if (q == p) continue;
                if (q.x == p.x && q.y == p.y) duplicate++;
                else {
                    double s = p.x == q.x ? Double.MAX_VALUE: (double)(p.y-q.y)/(p.x-q.x);
                    map.put(s, map.containsKey(s) ? map.get(s)+1: 1);
                    count = Math.max(count, map.get(s));
                }
            }
            res = Math.max(res, count+duplicate);
        }
        return res;
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/65473.html

相關文章

  • leetcode-149-Max Points on a Line

    Given n points on a 2D plane,find the maximum number of points that lie on the same straight line. from decimal import Decimal # Definition for a point. class Point: def __init__(self, a=0, b=0)...

    darcrand 評論0 收藏0

  • [Leetcode] Max Points on a Line 線上最大點數

    摘要：哈希表復雜度時間空間思路一個點加一個斜率，就可以唯一的確定一條直線。這里，我們用哈希表，以斜率為，記錄有多少重復直線。注意哈希表的為，但是可以有正和負的，而且不一樣。 Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the same stra...

    ernest.wang 評論0 收藏0

  • [Leetcode] Max Points on a Line 直線上最多的點數

    摘要：分子分母同時除以他們的最大公約數即可得到最簡分數，一般求的是兩個正整數的。這道題和有可能是，分別表示與軸或軸平行的斜率注意不能同時為表示同一個點沒有意義，所以這道題我們規(guī)定取值范圍。 Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the s...

    張憲坤 評論0 收藏0

  • [LintCode] Baseball Game

    Problem Youre now a baseball game point recorder. Given a list of strings, each string can be one of the 4 following types: Integer (one rounds score): Directly represents the number of points you get...

    newtrek 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<