LeetCode 947题暴力解法逻辑漏洞排查求助

问题回顾 #

LeetCode 947 要求计算二维平面上最多可移除的石头数量，移除规则是：某石头与未移除的另一石头同行或同列时即可移除。你的暴力递归代码在测试用例stones = [[0,1],[1,2],[1,3],[3,3],[2,3],[0,2]]中输出4，与预期的5不符，核心问题出在递归逻辑的设计上。

原代码的逻辑漏洞 #

原代码的递归是按数组索引顺序逐个处理石头，每个石头仅在第一次遍历到的时候决定是否移除，这种设计存在两个致命问题：

• 强制固定移除顺序，无法尝试“先移除后面的石头，再移除前面的石头”这类更优路径；
• 一旦跳过某个石头（选择不移除），递归流程不会回头处理它，即便后续移除其他石头后该石头满足移除条件。

比如在测试用例中，原代码按顺序处理时，会提前跳过某些石头，导致最终无法达到最大移除数量。

修复后的回溯递归代码 #

正确的暴力解法应该采用回溯法，遍历所有剩余石头，尝试移除每个可移除的石头，再回溯恢复状态，以此枚举所有可能的移除顺序，找到最大值：

/**
 * @param {number[][]} stones
 * @return {number}
 */
var removeStones = function(stones) {
    const n = stones.length;
    // 记录石头是否被移除
    const removed = new Array(n).fill(false);
    return backtrack(stones, removed);
};

const backtrack = (stones, removed) => {
    let maxCount = 0;
    let hasMovable = false;
    
    // 遍历所有未被移除的石头
    for (let i = 0; i < stones.length; i++) {
        if (removed[i]) continue;
        
        // 检查当前石头是否可以被移除：存在其他未移除的石头同行或同列
        const [row, col] = stones[i];
        let canRemove = false;
        for (let j = 0; j < stones.length; j++) {
            if (i === j || removed[j]) continue;
            if (stones[j][0] === row || stones[j][1] === col) {
                canRemove = true;
                break;
            }
        }
        
        if (canRemove) {
            hasMovable = true;
            // 标记为已移除
            removed[i] = true;
            // 递归计算后续最大移除数量，加1（当前移除的这一个）
            const currentCount = 1 + backtrack(stones, removed);
            // 更新最大值
            if (currentCount > maxCount) {
                maxCount = currentCount;
            }
            // 回溯，取消标记
            removed[i] = false;
        }
    }
    
    // 如果没有可移除的石头，返回0
    return hasMovable ? maxCount : 0;
};

代码说明 #

• 用removed数组跟踪每个石头的移除状态，避免重复处理；
• 每次递归遍历所有未移除的石头，判断是否满足移除条件（存在其他未移除的同行列石头）；
• 对每个可移除的石头，执行移除→递归→回溯的流程，枚举所有可能的移除路径；
• 递归终止条件是没有可移除的石头，返回当前累计的移除数量。

验证测试用例 #

对于测试用例stones = [[0,1],[1,2],[1,3],[3,3],[2,3],[0,2]]，修复后的代码会尝试所有可能的移除顺序，最终找到可以移除5个石头的路径，返回预期结果5。

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