LeetCode 2152 最少直线覆盖点 JS实现同x坐标用例失败排查

你的JS代码存在核心逻辑错误，导致竖直线场景判断失效：

1. 斜率计算函数判断逻辑完全错误 #

Python原版判断竖直线的规则是两点x坐标相等时，直接返回无穷大作为竖直线斜率，但你的代码错误使用p2 !== p1作为判断条件：

• 这个判断是对比两个数组的引用地址是否相同，只要是两个独立创建的点数组，哪怕坐标完全一致，p2 !== p1都会返回true，永远不会走到返回Number.MAX_SAFE_INTEGER的分支
• 当两点x坐标相同时，代码直接执行除法，分母为0时JS会根据分子正负返回Infinity或-Infinity，二者用===对比返回false，会导致同一条竖直线上的点被误判为不在同一条线
• 你预设的竖直线代表值Number.MAX_SAFE_INTEGER是有限整数，和除法得到的Infinity也不相等，进一步加剧判断错误

2. 初始值设置不匹配逻辑 #

你用Number.MAX_SAFE_INTEGER初始化最优解变量，和Python中用无穷大初始化的逻辑不一致，虽然不影响当前测试用例，但存在边界风险。

核心修改 #

1. 重写斜率计算函数：把判断条件改为对比两点x坐标，x相等时统一返回固定值Infinity，不做除法避免出现-Infinity
2. 把最优解初始值改为Infinity，和原版逻辑对齐

修复后完整可运行代码 #

var cal_slope = function(p1, p2) {
    // 竖直线统一返回Infinity，不做除法避免正负无穷不一致问题
    if (p1[0] === p2[0]) {
        return Infinity;
    }
    return (p2[1] - p1[1]) / (p2[0] - p1[0]);
}

var dfs = function(lines, pts) {
    if (pts.length === 0) {
        return lines.length;
    }
    
    const curr_pt = pts[0];
    
    // 检查当前点是否可被已有直线覆盖
    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) {
            return dfs(lines, pts.slice(1));
        }
    }
    
    if (pts.length === 1) {
        return lines.length + 1;
    }
    
    let best = Infinity;
    
    // 枚举当前点和剩余点组成新直线的所有可能性
    for (let i = 1; i < pts.length; ++i) {
        const pt = pts[i];
        const new_slope = cal_slope(curr_pt, pt);
        const newLines = lines.slice();
        newLines.push([curr_pt, new_slope]);
        const newPts = [...pts.slice(1, i), ...pts.slice(i+1)];
        best = Math.min(best, dfs(newLines, newPts));
    }
    
    return best;
}

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

上述代码可以通过你给出的测试用例，如果要100%规避浮点数精度误差（比如理论相等的斜率因为双精度浮点数计算偏差导致判断失败），可以把斜率存储为约简后的分数形式，统一符号规则（比如分母恒为正），用分子分母组成的字符串作为斜率标识，彻底避免浮点数对比问题。

内容的提问来源于stack exchange，提问作者kenpeter