Leetcode 2152，覆盖点的最小行数.当x轴相同时失效

Question

这是能够通过所有测试用例的解决方案。我试图将其转换为javascript，但它失败了这个测试用例。(当两个点有相同的x轴时)

[[-4,0],[0,4],[-1,-5],[2,3],[-4,1],[-4,3],[-1,5]]
output: 4
expect: 3

如果你没有权限:可以看看这个https://www.geeksforgeeks.org/minimum-lines-cover-points/

class Solution:
def minimumLines(self, points: List[List[int]]) -> int:
slope_calc = lambda p1, p2: (p2[1] - p1[1]) / (p2[0] - p1[0]) if p2[0] != p1[0] else math.inf
def helper(lines, points):
if len(points) == 0:
return len(lines)

point = points[0]


# add to existing line            
for p, slope in lines:
s = slope_calc(point, p)
if s == slope:
return helper(lines, points[1:])

# if we have a single point and it doesn't belong to an existing
# line, we must have another line to cover it.
if len(points) == 1:
return len(lines) + 1
# creating new line in the case we have two or more points
# (cover two at once). iterating through all possibilities.
best = math.inf
for i in range(1, len(points)):
p = points[i]
slope = slope_calc(point, p)
lines.append((point, slope))
best = min(best, helper(lines, points[1:i] + points[i + 1:]))
lines.pop(-1)

return best
return helper([], points) if len(points) > 1 else 1

这是我的javascript

var cal_slope = function(p2, p1) {
if(p2 !== p1) {
return (p2[1] - p1[1]) / (p2[0] - p1[0]);    
} else {
return Number.MAX_SAFE_INTEGER;
}
}
var dfs = function(lines, pts) {
// base
if(pts.length === 0) {
return lines.length;
}

const curr_pt = pts[0];

// existing can cover?
for(let i=0; i<lines.length; ++i) {
const line_pt = lines[i][0];
const line_slope = lines[i][1];

const new_slope = cal_slope(line_pt, curr_pt);
if(new_slope === line_slope) {
// can cover
return dfs(lines, pts.slice(1));
}
} // el

// cannot cover
if(pts.length === 1) {
return lines.length + 1;
}


let best = Number.MAX_SAFE_INTEGER;

// form new slope
for(let i=1; i<pts.length; ++i) {
const pt = pts[i];
const new_slope = cal_slope(pt, curr_pt);

const line1 = lines.slice(0);
line1.push([curr_pt, new_slope]);

const p1 = pts.slice(1, i);
const p2 = pts.slice(i+1);
const newPts = [...p1, ...p2];

best = Math.min(best, dfs(line1, newPts));
} // el

return best
}
var minimumLines = function(pts) {
if(pts.length === 1) {
return 1;    
} else {
return dfs([], pts);
}
};

Answer 1

问题在这一行:

if(p2 !== p1) {

在函数的使用中，p1和p2是具有x和y坐标的数组。只有当p1和p2是相同的数组引用时，这种比较才成立。这在你的用例中是绝对不会发生的。

你需要这个(Python版本也是如此):

if(p2[0] !== p1[0]) {