大部分石子在同一行或同一列被移除

Question

我无法理解我的代码中的逻辑缺陷是什么

我正在努力解决这个问题：

947。同一行或同一列移除的大部分石头

在 2D 平面上，我们将 n 个石头放置在一些整数坐标点处。每个坐标点最多可以有一颗石头。

如果一块石头与另一块尚未被移除的石头共享同一行或同一列，则可以将其移除。

给定一个长度为 n 的石头数组，其中stones[i] = [xi, yi] 表示第 i 个石头的位置，返回可以移除的最大石头数量。

/**

 * @param {number[][]} stones
 * @return {number}
 */
var removeStones = function (stones) {
    const rowMap = {}
    const colMap = {}
    for (let i = 0; i < stones.length; i++) {
        const [row, col] = stones[i]
        if (!rowMap[row]) rowMap[row] = 0
        if (!colMap[col]) colMap[col] = 0
        rowMap[row] += 1
        colMap[col] += 1
    }
    return findMaxMove(stones, 0, rowMap, colMap)
};

const findMaxMove = (stones, index, rowMap, colMap) => {
    if (index == stones.length) return 0
    const [row, col] = stones[index]
    let isInCol = colMap[col] > 1
    let isInRow = rowMap[row] > 1
    let removedMove = 0
    if (isInCol || isInRow) {
        const colMapCopy = { ...colMap, [col]: colMap[col] - 1 }
        const rowMapCopy = { ...rowMap, [row]: rowMap[row] - 1 }
        removedMove = 1 + findMaxMove(stones, index + 1, rowMapCopy, colMapCopy);
    }
    return Math.max(removedMove, findMaxMove(stones, index + 1, rowMap, colMap))
}

有些情况通过，有些情况不通过：

不工作的情况：

stones = [[0,1],[1,2],[1,3],[3,3],[2,3],[0,2]]
Expected: 5
Output: 4

我从互联网上了解到，使用不相交集来解决是常见问题，但在深入研究不相交集之前我想用蛮力来解决。

请帮忙

Answer 1

失败的测试用例代表这个平面：

. 0 5 .
. . 1 2
. . . 4
. . . 3

当您的代码按照索引顺序删除石头时，您将首先删除石头 0 和 1，留下石头 5 成为孤立的：

. . 5 .
. . . 2
. . . 4
. . . 3

这不是最佳解决方案，因为您可以先删除 0（就像您所做的那样），然后先删除 5，然后再删除 1。然后可以删除所有石头。

你的算法并不是真正的蛮力，因为它排除了其他可能性。您已经实现了一种可以称为“贪婪”的算法，但不是暴力算法。蛮力方法也会尝试以不同的顺序移除石头，因为顺序会影响可以移除的石头数量。