JavaScript算法29- 表示一个折线图的最少线段数（leetCode:6076）周赛

本文主要是介绍JavaScript算法29- 表示一个折线图的最少线段数（leetCode:6076）周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

6076. 表示一个折线图的最少线段数

一、题目

给你一个二维整数数组 stockPrices ，其中 stockPrices[i] = [dayi, pricei] 表示股票在 dayi 的价格为 pricei 。折线图 是一个二维平面上的若干个点组成的图，横坐标表示日期，纵坐标表示价格，折线图由相邻的点连接而成。比方说下图是一个例子：

在这里插入图片描述

请你返回要表示一个折线图所需要的 最少线段数 。

示例 1：
在这里插入图片描述

输入：stockPrices = [[1,7],[2,6],[3,5],[4,4],[5,4],[6,3],[7,2],[8,1]]
输出：3
解释：
上图为输入对应的图，横坐标表示日期，纵坐标表示价格。
以下 3 个线段可以表示折线图：
- 线段 1 （红色）从 (1,7) 到 (4,4) ，经过 (1,7) ，(2,6) ，(3,5) 和 (4,4) 。
- 线段 2 （蓝色）从 (4,4) 到 (5,4) 。
- 线段 3 （绿色）从 (5,4) 到 (8,1) ，经过 (5,4) ，(6,3) ，(7,2) 和 (8,1) 。
可以证明，无法用少于 3 条线段表示这个折线图。

示例 2：
在这里插入图片描述

输入：stockPrices = [[3,4],[1,2],[7,8],[2,3]]
输出：1
解释：
如上图所示，折线图可以用一条线段表示。

提示：

1 <= stockPrices.length <= 10⁵
stockPrices[i].length == 2
1 <= dayi, pricei <= 10⁹
所有 dayi 互不相同。

二、题解

初看这题很简单，一顿操作猛如虎
（提示：这是错误示范，可略过）

/*** @param {number[][]} stockPrices* @return {number}*/
var minimumLines = function(stockPrices) {if(stockPrices.length === 1) return 0// 按照日期升序排序stockPrices.sort((a, b) => a[0] - b[0]);let linesNumber = 0// 初始化斜率let ratiofor (let i = 1; i < stockPrices.length; i++){// 当前两点间的直线斜率let currRatio = (stockPrices[i][1] - stockPrices[i - 1][1]) / (stockPrices[i][0] - stockPrices[i - 1][0])// 若当前两点间的斜率和之前的斜率不相等，则认为产生新线段if (ratio !== currRatio) {linesNumber++ratio = currRatio}}return linesNumber
};

阻塞在最后3个示例（精度丢失问题）
在这里插入图片描述

解题思路我们已经有了（判断当前两点的直线斜率和之前的直线斜率是否相等），现在的难点在于怎样防止精度丢失
解决方法：

除法变乘法（a / b === c / d 变为 a * d === b * c）
套个 BigInt，处理乘积超出 Number最大范围的问题。

/*** @param {number[][]} stockPrices* @return {number}*/
var minimumLines = function (stockPrices) {  if(stockPrices.length === 1) return 0if(stockPrices.length === 2) return 1// 按照日期升序排序stockPrices.sort((a, b) => a[0] - b[0]);let linesNumber = 1let SUB1 = stockPrices[1][1] - stockPrices[0][1]let SUB2 = stockPrices[1][0] - stockPrices[0][0]for (let i = 2; i < stockPrices.length; i++){let sub1 = (stockPrices[i][1] - stockPrices[i - 1][1])let sub2 =  (stockPrices[i][0] - stockPrices[i - 1][0])if (BigInt(SUB2)*BigInt(sub1) !== BigInt(SUB1)*BigInt(sub2)) {linesNumber++}SUB1 = sub1SUB2 = sub2}return linesNumber
};

在这里插入图片描述

三、拓展：BigInt

MDN-BigInt详解
1、介绍
BigInt 是一种内置对象，它提供了一种方法来表示大于 2⁵³ - 1 的整数。这原本是 Javascript中可以用 Number 表示的最大数字。BigInt 可以表示任意大的整数。

2、用法
可以用在一个整数字面量后面加 n 的方式定义一个 BigInt ，如：10n，或者调用函数 BigInt()（但不包含 new 运算符）并传递一个整数值或字符串值。

const theBiggestInt = 9007199254740991n;const alsoHuge = BigInt(9007199254740991);
// ↪ 9007199254740991nconst hugeString = BigInt("9007199254740991");
// ↪ 9007199254740991nconst hugeHex = BigInt("0x1fffffffffffff");
// ↪ 9007199254740991nconst hugeBin = BigInt("0b11111111111111111111111111111111111111111111111111111");
// ↪ 9007199254740991n