`
betakoli
  • 浏览: 168743 次
社区版块
存档分类
最新评论

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 straight line.

一个平面中有很多点,找出能在同一条直线上的最多的点

思路:遍历所有的点,在每次遍历中再依次遍历其他与该点没有计算过斜率的点,计算斜率,并统计数量。

 

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
		if(points.length==0) return 0;
        int max = 1;
        //第一个值存放斜率,第二个存放数量
        Map<Double,Integer> map = new HashMap<Double,Integer>();
        for(int i=0;i<points.length-1;i++)
        {
            int x=1;
            int duplicates = 0;
            boolean flag = false;
            int tempmax = 1;
            map.clear();
        	for(int j=i+1;j<points.length;j++)
        	{
                        //计算重复点
        		if(points[j].x==points[i].x&&points[i].y==points[j].y)
        		{
        			duplicates++;
        			continue;
        		}
                        //判断是否两点共x轴
        		if(points[j].x-points[i].x!=0)
        		{
	        		double k = (double)(points[j].y-points[i].y)/(points[j].x-points[i].x);
	        		if(k==-0.0)
	        			k=0.0;
	        		if(map.get(k)==null)
	        		{
	        			map.put(k, 2);
	        			if(tempmax<2) tempmax=2;
	        		}	
	        		else 
	        		{
	        			int t = (Integer)map.get(k);
	        			t=t+1;
	        			map.put(k,t);
	        			if(t>tempmax) tempmax=t;
	        		}
        		}else
        		{
        			x++;
        		}
        	}
        	
        	if(tempmax+duplicates>max)
        	 max = duplicates+tempmax;
        	if(x>max) max=x;
        }
        return max;
    }
}

 

 

分享到:
评论

相关推荐

    leetcodemaxpointsonaline-leetcode:leetcode

    max points on a line leetcode ISCAS15 - leetcode - week1 唐波 任杰 王建飞 殷康 张一鸣 ISCAS15 - leetcode - week2 曾靖 刘重瑞 沉雯婷 刘旭斌 王建飞 ISCAS15 - leetcode - week3 殷康 张一鸣 赵伟 任杰 唐波 ...

    python-leetcode题解之149-Max-Points-on-a-Line.py

    python python_leetcode题解之149_Max_Points_on_a_Line.py

    js-leetcode题解之149-max-points-on-a-line.js

    javascript js_leetcode题解之149-max-points-on-a-line.js

    LeetCode最全代码

    Up to date (2016-12-18), there are `447` Algorithms / `13` Database / `4` Shell / `4` Draft questions on [LeetCode Online Judge](https://leetcode.com/). The number of questions is increasing recently...

    dna匹配leetcode-leetcode:leetcode刷题

    dna匹配 leetcode leetcode刷题--C++ 哈希表 Longest Substring Without Repeating Characters ...Points on a Line 斜率 map, int&gt; Fraction to Recurring Decimal map long long 正负号 Repeated DNA S

    LeetCode:LeetCode解决方案

    LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...

    Selective_Leetcode_solutions

    2. 题目149 - "Max Points on a Line" 这道题目要求找到平面上最多共线的点。解决方法通常涉及线性代数,如计算两点之间的斜率,并通过哈希表记录斜率及其出现的次数。在Java中,可以使用HashMap来存储斜率和对应的...

    leetcodemaxpointsonaline-leetcode:https://oj.leetcode.com/的解决方案

    在LeetCode平台上,题目"Max Points on a Line"是一道典型的几何与图论结合的问题,旨在测试编程者对数据结构和算法的理解。本题要求找到二维平面上最多共线的点的数量。这个问题的关键在于理解如何有效地计算每一对...

    leetcode-answer-and-analysis(part).zip_图形图像处理_Java_

    2. **Max points on a line** (平面上最多的共线点): 此题考察的是线性代数和几何知识,以及如何在二维平面上找到共线点。在Java中,可以使用数据结构如HashMap来存储斜率和点的数量,从而有效地计算最大共线点数。 ...

Global site tag (gtag.js) - Google Analytics