上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
int minimumLines(vector<vector<int>>& stockPrices) {
}
};
java 解法, 执行用时: 31 ms, 内存消耗: 79.8 MB, 提交时间: 2023-07-01 13:42:35
/**
* 枚举斜率
* 相邻的点如果斜率不一致,需要新加一段
* 通过相邻点的横纵坐标差,判断斜率,方式有二:
* y1/x1 != y2/x2, 由于除法涉及 double 精度 比较麻烦
* 移项后判断 y1 * x2 != y2 * x1 , 方便很多
* 一个点, 线段数为0
**/
class Solution {
public int minimumLines(int[][] stockPrices) {
Arrays.sort(stockPrices, (o1, o2) -> o1[0] - o2[0]);
int n = stockPrices.length, res = 1;
if (n == 1) return 0;
for (int i = 2; i < n; i++) {
int x1 = stockPrices[i][0] - stockPrices[i - 1][0], y1 = stockPrices[i][1] - stockPrices[i - 1][1];
int x2 = stockPrices[i - 1][0] - stockPrices[i - 2][0], y2 = stockPrices[i - 1][1] - stockPrices[i - 2][1];
if (y1 * x2 != y2 * x1) res++;
}
return res;
}
}
cpp 解法, 执行用时: 356 ms, 内存消耗: 98.3 MB, 提交时间: 2023-07-01 13:41:39
class Solution {
public:
int minimumLines(vector<vector<int>> &a) {
sort(a.begin(), a.end(), [](auto &a, auto &b) { return a[0] < b[0]; });
int ans = 0;
long double pre_k = 2e9;
for (int i = 1; i < a.size(); ++i) {
long double k = (long double) (a[i][1] - a[i - 1][1]) / (a[i][0] - a[i - 1][0]);
if (k != pre_k) {
ans++;
pre_k = k;
}
}
return ans;
}
};
golang 解法, 执行用时: 232 ms, 内存消耗: 18.9 MB, 提交时间: 2023-07-01 13:41:25
func minimumLines(a [][]int) (ans int) {
sort.Slice(a, func(i, j int) bool { return a[i][0] < a[j][0] }) // 按照 day 排序
for i, preDY, preDX := 1, 1, 0; i < len(a); i++ {
dy, dx := a[i][1]-a[i-1][1], a[i][0]-a[i-1][0]
if dy*preDX != preDY*dx { // 与上一条线段的斜率不同
ans++
preDY, preDX = dy, dx
}
}
return
}
python3 解法, 执行用时: 212 ms, 内存消耗: 49.8 MB, 提交时间: 2023-07-01 13:41:03
class Solution:
def minimumLines(self, stockPrices: List[List[int]]) -> int:
stockPrices.sort(key=lambda x: x[0]) # 按照 day 排序
ans, pre_dy, pre_dx = 0, 1, 0
for (x1, y1), (x2, y2) in pairwise(stockPrices):
dy, dx = y2 - y1, x2 - x1
if dy * pre_dx != pre_dy * dx: # 与上一条线段的斜率不同
ans += 1
pre_dy, pre_dx = dy, dx
return ans
