You need to enable JavaScript to run this app. LeetCode「判断是否为直线」算法如何优化运行时与内存性能?
优惠活动
大模型
产品
解决方案
定价
更多

LeetCode「判断是否为直线」算法如何优化运行时与内存性能?

「判断是否为直线」题目的性能优化思路

现有代码排名靠后的核心原因

  • 引入重量级第三方依赖:代码在函数内部导入numpy的操作本身会带来极高的导入开销,不仅拖慢运行时速度,也会拉高内存占用——为了实现一个简单的去重功能引入整个数值计算库,属于严重的性能浪费。
  • 存在不必要的IO操作:代码分支判断中的print(slope)会触发标准输出写入,这类IO操作的耗时远高于纯算术运算,是拉低Runtime排名的核心原因之一。
  • 冗余的内存与计算开销:需要把所有相邻点计算出的斜率存入列表,既会占用额外的列表内存,浮点除法的运算效率也远低于整数运算,还可能因为浮点精度问题出现判断误差。
  • 原逻辑存在边界漏洞:遇到x坐标差为0的垂直直线场景,直接把x值存入斜率列表,碰到多段垂直但x坐标不统一的折线时,会出现逻辑误判。

高效解题的核心逻辑

核心思路是用向量叉积替代斜率计算,全程规避除法、浮点运算与额外存储:
三个点共线的充要条件是,以第一个点为公共起点,连接第二个点的向量、连接当前待判断点的向量,二者的叉积为0。对应的判断公式为:
(x1 - x0) * (yi - y0) == (xi - x0) * (y1 - y0)
这种思路的优势非常明显:

  • 全程仅使用整数运算,没有除法、没有浮点精度问题,计算速度远快于传统的斜率计算逻辑
  • 不需要申请额外列表存储所有斜率,遍历过程中一旦发现叉积不为0,直接返回结果,无需走完所有坐标点
  • 天然兼容垂直直线、水平直线的特殊场景,不需要单独做除零判断
  • 完全不需要第三方库支撑,纯原生Python即可实现

优化后的参考代码

def checkStraightLine(self, coordinates):
    # 取前两个点作为共线判断的基准
    (x0, y0), (x1, y1) = coordinates[0], coordinates[1]
    # 遍历剩余点做叉积判断
    for x, y in coordinates[2:]:
        if (x1 - x0) * (y - y0) != (x - x0) * (y1 - y0):
            return False
    return True

该实现没有冗余操作,运行时和内存占用通常可以超过90%以上的同题目提交。


内容的提问来源于stack exchange,提问作者Avia Y

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.23 02:54:04