资讯专栏INFORMATION COLUMN

LeetCode 4

zhkai / 1325人阅读

摘要:这个题的思路就是找数组里的两个点,用这两个点来做一条直线,然后看数组里的点都在直线上不,我用的是两点式,需要考虑两个点或坐标相同的特殊情况。

Max Points on a Line https://oj.leetcode.com/problems/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.

这个题的思路就是找数组里的两个点,用这两个点来做一条直线,然后看数组里的点都在直线上不,我用的是两点式,需要考虑两个点x或y坐标相同的特殊情况。

public class Solution {
    public int maxPoints(Point[] points) {
        int num = points.length;
        int maxPoints = 0;
        if(num == 1) return 1;
        for(int first = 0; first < num; first++){
            for(int second = 0;second < num / 2 +1; second++){
                if(first == second) continue;
                Point firstPoint = points[first];
                Point secondPoint = points[second];
                int count = 0;
                if(firstPoint.x == secondPoint.x){
                    for(int i = 0; i < num; i++){
                        if(points[i].x == firstPoint.x) count++;
                    }
                }else if(firstPoint.y == secondPoint.y){
                    for(int i = 0; i < num; i++){
                        if(points[i].y == firstPoint.y) count++;
                    }
                }else{
                    for(int i = 0; i < num; i++){
                        if((points[i].y - secondPoint.y) * (firstPoint.x - secondPoint.x) == 
                            (firstPoint.y - secondPoint.y) * (points[i].x - secondPoint.x)){
                            count++;
                        }
                    }
                }
                if(count > maxPoints) maxPoints = count;
            }
        }
        return maxPoints;
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/64104.html

相关文章

  • 6-9月技术文章汇总

    摘要:分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥?...

    miya 评论0 收藏0
  • LeetCode 精选TOP面试题【51 ~ 100】

    摘要:有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像,都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归,所以空间复杂度为 ...

    Clect 评论0 收藏0
  • 简单易用的leetcode开发测试工具(npm)

    摘要:工具安装使用示例问题下面两部分的顺序不能交换第一个参数是空数组故意写错答案,展示测试失败输出效果测试用例编写说明要测试的都是函数,参数个数不定,但返回值是一个。上面例子的输入参数是,第一个参数是数组,第二个参数是数值返回值是一个数组。 描述 最近在用es6解leetcode,当问题比较复杂时,有可能修正了新的错误,却影响了前面的流程。要用通用的测试工具,却又有杀鸡用牛刀的感觉,所以就写...

    shusen 评论0 收藏0
  • 优秀程序员都应该学习的 GitHub 上开源的数据结构与算法项目

    摘要:强烈推荐上值得前端学习的数据结构与算法项目,包含图的演示过程与视频讲解。该仓库包含了多种基于的算法与数据结构,提供进一步阅读的解释和链接。数据结构和算法必知必会的个代码实现。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法为王。想学好前端,先练好内功,内功不行,就算招式练的再花哨,终究成不了高手;只有内功深厚者,前端之路才会走得...

    cheukyin 评论0 收藏0
  • LeetCode天梯>Day031 验证二叉搜索树(递归+中序遍历) | 初级算法 | Pytho

    摘要:有效二叉搜索树定义如下节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值,根节点的值均小于右子树的值,因此中序遍历以后得到的序列一定是升序序列。 ...

    Genng 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<