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

发布日期： 2024-08-30 阅读量： 作者： 网络

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

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

难度：中等

主题：哈希表、深度优先搜索、并集查找、图

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

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

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

示例1：

输入： 石头 = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出： 5
说明：移除 5 颗石头的一种方法如下：
1. 移除石头 [2,2]，因为它与 [2,1] 共享同一行。
2. 移除石头 [2,1]，因为它与 [0,1] 共享同一列。
3. 移除石头 [1,2]，因为它与 [1,0] 共享同一行。
4. 移除石头 [1,0]，因为它与 [0,0] 共享同一列。
5. 移除石头 [0,1]，因为它与 [0,0] 共享同一行。
6. 石头 [0,0] 无法移除，因为它不与平面上的另一块石头共享行/列。

示例2：

输入： 石头 = [[0,0],[0,2],[1,1],[2,0],[2,2]]
输出： 3
说明：进行 3 步的一种方法如下：
1. 移除石头 [2,2]，因为它与 [2,0] 共享同一行。
2. 移除石头 [2,0]，因为它与 [0,0] 共享同一列。
3. 移除石头 [0,2]，因为它与 [0,0] 共享同一行。
4. 棋子 [0,0] 和 [1,1] 无法移除，因为它们不与平面上的另一个棋子共享行/列。

示例 3：

输入： 石头 = [[0,0]]
输出： 0
解释： [0,0] 是平面上唯一的石头，所以你无法移除它。

约束：

1
0 i, y_i4
没有两块石头位于同一坐标点。

解决方案：

我们可以使用深度优先搜索（dfs）方法来实现该解决方案。这个想法是将通过行或列连接的石头视为同一连接组件的一部分。一旦找到所有连通分量，可以移除的最大石子数量就是石子总数减去连通分量的数量。

让我们用 php 实现这个解决方案：947。同一行或同一列移除的大部分石头

<?php
function removeStones($stones) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

function dfs($stoneIndex, &$stones, &$visited) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$stones1 = array(
    array(0, 0),
    array(0, 1),
    array(1, 0),
    array(1, 2),
    array(2, 1),
    array(2, 2)
);
echo removeStones($stones1); // Output: 5

$stones2 = array(
    array(0, 0),
    array(0, 2),
    array(1, 1),
    array(2, 0),
    array(2, 2)
);
echo removeStones($stones2); // Output: 3

$stones3 = array(
    array(0, 0)
);
echo removeStones($stones3); // Output: 0
?>

# git # 社交网络

上一篇: phpcms静态url设置

下一篇: phpcms栏目如何绑定域名

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

随便看看