关键词：
title: LeetCode No.149
categories:
- OJ
- LeetCode
tags:
- Programing
- LeetCode
- OJ
LeetCode第149题—直线上最多的点数
自己代码的开源仓库:click here 欢迎Star和Fork 😃
题目描述
给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
示例 1：
输入：points = [[1,1],[2,2],[3,3]]
输出：3
示例 2：
输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4
提示：
1 <= points.length <= 300
points[i].length == 2
-104 <= xi, yi <= 104
points 中的所有点 互不相同
代码
from fractions import Fraction
class Solution(object):
# 统计在直线上点的个数
def num_points_on_line(self, k, b, points):
num = 0
for i in range(len(points)):
if points[i][0] * k + b == points[i][1]:
num += 1
return num
def time_out(self, points):
"""
暴力搜索的方法，目前自己能想到的方法
找到两个点求出斜率，然后确定还有多少个点在上面，找到最大的, 暴力搜索不出意外的Time out了，下面尝试对代码进行优化
:type points: List[List[int]]
:rtype: int
"""
if len(points) == 1:
return 1
if len(points) == 2:
return 2
max_num = 0
for i in range(len(points)):
for j in range(len(points)):
if i == j:
continue
if points[i][0] - points[j][0] == 0: # 为纵轴的情况
cur_num = 0
for m in range(len(points)):
if points[m][0] == points[i][0]:
cur_num += 1
else:
k = Fraction((points[i][1] - points[j][1]) , (points[i][0] - points[j][0]))
b = points[i][1] - k * points[i][0]
cur_num = self.num_points_on_line(k, b, points)
if cur_num > max_num:
max_num = cur_num
return max_num
def maxPoints(self, points):
"""
不出意料的暴力搜索的代码直接裂开了，我最开始的那个暴力算法冗余度太高了，后面需要进行优化，这里使用哈希表进行记忆
可以使用如下方法：
固定一个点来统计和其他的点的斜率
最后再将斜率和b相同的点个数统计，返回最大的值
考虑用字典来记录，字典：斜率: [位于当前斜率上的点]
:type points: List[List[int]]
:rtype: int
"""
if len(points) == 1:
return 1
if len(points) == 2:
return 2
max_num = 0
k_num = dict()
for i in range(len(points)):
for j in range(len(points)):
if i == j:
continue
if points[i][0] - points[j][0] == 0: # 为纵轴的情况 斜率不存在用对应的x值的字符串表示
if str(points[i][0]) not in k_num.keys():
k_num[str(points[i][0])] = []
if points[i] not in k_num[str(points[i][0])]:
k_num[str(points[i][0])].append(points[i])
if points[j] not in k_num[str(points[i][0])]:
k_num[str(points[i][0])].append(points[j])
if len(k_num[str(points[i][0])]) > max_num:
max_num = len(k_num[str(points[i][0])])
else:
k = Fraction((points[i][1] - points[j][1]) , (points[i][0] - points[j][0]))
b = points[i][1] - k * points[i][0]
key = str(k)+','+str(b)
if key not in k_num.keys():
k_num[key] = []
if points[i] not in k_num[key]:
k_num[key].append(points[i])
if points[j] not in k_num[key]:
k_num[key].append(points[j])
if len(k_num[key]) > max_num:
max_num = len(k_num[key])
return max_num
if __name__ == '__main__':
s = Solution()
print(s.maxPoints([[0,0],[4,5],[7,8],[8,9],[5,6],[3,4],[1,1]]))
leetcode149.直线上最多的点数(代码片段)
给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一条直线上。 示例1：输入：points=[[1,1],[2,2],[3,3]]输出：3示例2：输入：points=[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]输出：4 提示：1<=points.length&... 查看详情
149maxpointsonaline直线上最多的点数
给定二维平面上有n个点，求最多有多少点在同一条直线上。详见：https://leetcode.com/problems/max-points-on-a-line/description//***Definitionforapoint.*structPoint*intx;*inty;*Point():x(0),y(0)*Point(inta,intb):x(a),y(b)*;*/clas 查看详情
题目地址(149.直线上最多的点数)(代码片段)
题目地址(149.直线上最多的点数)https://leetcode.cn/problems/max-points-on-a-line/题目描述给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一条直线上。 示例1：输入：points=[[1,1],[2,2],[... 查看详情
题目地址(149.直线上最多的点数)(代码片段)
题目地址(149.直线上最多的点数)https://leetcode.cn/problems/max-points-on-a-line/题目描述给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一条直线上。 示例1：输入：points=[[1,1],[2,2],[... 查看详情
leetcode0149.直线上最多的点数(代码片段)
...LetMeFly】149.直线上最多的点数力扣题目链接：https://leetcode.cn/problems/max-points-on-a-line/给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一条直线上。 示例1：输入：points=[[1... 查看详情
leetcodeno.149直线上最多的点数(代码片段)
...xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一条直线上。示例1：输入：points=[[1,1],[2,2],[3,3]]输出：3示例2：输入：points=[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]输出：4提示：1<=points.length<=300points[i].l 查看详情
leetcodeno.149直线上最多的点数(代码片段)
一、题目描述给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一条直线上。示例1：输入：points=[[1,1],[2,2],[3,3]]输出：3示例2：输入：points=[[1,1],[3,2],[5,3],[4,1],[2, 查看详情
2021-09-03：直线上最多的点数。给你一个数组points，其中points[i]=[xi,yi]表示x-y平面上的一个点。求最多有多少个点在同一条直线上。力扣149。(代码片(代码片段)
2021-09-03：直线上最多的点数。给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点。求最多有多少个点在同一条直线上。力扣149。福大大答案2021-09-03：具体见代码。代码用golang编写。代码如下：packagem... 查看详情
直线上最多的点数
给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。functionmaxPoints(points)if(points.length==1)return1letnumber=0for(leti=0;i<points.length-1;i++)letitem=points[i]for(letj=i+1;j<points.length;j++ 查看详情
maxpointsonaline（直线上最多的点数）(代码片段)
给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。示例1:输入:[[1,1],[2,2],[3,3]]输出:3解释:^|| o| o| o +------------->0 1 2 34示例 2:输入:[[1,1],[3,2] 查看详情
leetcode刷题模版：141-150
目录简介141.环形链表142.环形链表II143.重排链表144.二叉树的前序遍历145.二叉树的后序遍历146.LRU缓存【未实现】147.对链表进行插入排序148.排序链表149.直线上最多的点数150.逆波兰表达式求值结语简介Hello！非常感谢您阅读海轰的... 查看详情
day4直线上最多的点数循环链表四数相加2(代码片段)
四数相加2对下一个题的方式有启发，使用dict存储后两个之和classSolution(object):deffourSumCount(self,A,B,C,D):Dict=foriinrange(len(C)):forjinrange(len(D)):ifC[i]+D[j]inDict:Dict[C[i]+D[j]]+=1else:Dict[ 查看详情
leetcode刷题模版：141-150
目录简介141.环形链表142.环形链表II143.重排链表144.二叉树的前序遍历145.二叉树的后序遍历146.LRU缓存【未实现】147.对链表进行插入排序148.排序链表149.直线上最多的点数150.逆波兰表达式求值结语简介Hello！非常感谢您阅读海轰的... 查看详情
直线上最多的点数(代码片段)
classSolutionpublicintmaxPoints(int[][]points)if(points.length==1)return1;Map<Double,Integer>map=newHashMap<>();intmax=Integer.MIN_VALUE;for(int[]point1:points)for(int[]point2:points)doublek=(double)(point2[1]-point1[1])/(double)(point2[0]-point1[0]);map.put(k,map.get... 查看详情
直线上最多的点数(代码片段)
classSolutionpublicintmaxPoints(int[][]points)if(points.length==1)return1;Map<Double,Integer>map=newHashMap<>();intmax=Integer.MIN_VALUE;for(int[]point1:points)for(int[]point2:points)doublek=(double)(point2[1]-point1[1])/(double)(point2[0]-point1[0]);map.put(k,map.get... 查看详情
数据结构与算法之深入解析“直线上最多的点数”的求解思路与算法示例(代码片段)
一、题目要求给你一个数组points，其中points[i]=[xi,yi]表示X-Y平面上的一个点，求最多有多少个点在同一条直线上。示例1：输入：points=[[1,1],[2,2] 查看详情
149.maxpointsonaline
...，三层循环，以任意两点划线，判断第三个点是否在这条直线上。 比较暴力 2、使用 查看详情
leetcode刷题日记之盛最多水的容器
节后第一天，鉴于五一五天都没做过题，有点遗忘了，今天来看一道简单点的题，练下手。先看下题：给你n个非负整数a1，a2，...，an，每个数代表坐标中的一个点(i,ai)。在坐标内画n条垂直线，垂直线i的两个端点分别为(i,ai)和(i,... 查看详情