LeetCode讲解篇之2280. 表示一个折线图的最少线段数

发布时间：2024年01月14日

文章目录

题目描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

题解思路

折线图中如果连续的线段共线，那么我们可以可以将其合并成一条线段

首先将坐标点按照横坐标升序排序

然后遍历数组

我们可以通过计算前一个线段的斜率和当前线段的斜率来判断是否共线

如果二者相等，则代表共线，则继续往后查找

如果不相等，则代表不共线，则线段数加一

最终遍历完数组，返回线段数的计数

题解代码

class Solution:
    def minimumLines(self, stockPrices: List[List[int]]) -> int:
        stockPrices.sort()
        pre_dy, pre_dx = 1, 0
        n = len(stockPrices)
        ans = 0
        for i in range(1, n):
            dy = stockPrices[i][1] - stockPrices[i-1][1]
            dx = stockPrices[i][0] - stockPrices[i-1][0]
            k = dy / dx
            if dy * pre_dx != dx * pre_dy:
                ans += 1
                pre_dy, pre_dx = dy, dx
        return ans
文章来源:https://blog.csdn.net/qq_67733273/article/details/135585578
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章