947。同一行或同一列移除的大部分石头
难度：中等
主题：哈希表、深度优先搜索、并集查找、图
在 2d 平面上，我们将 n 个石头放置在一些整数坐标点处。每个坐标点最多可以有一颗石头。
如果一块石头与另一块尚未移除的石头同一行或同一列，则可以将其移除。
给定一个长度为 n 的石头数组，其中stones[i] = [xi, yi] 表示第 i第 个石头的位置，返回可以移除的最大可能数量的石头.
示例1：
输入： 石头 = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]输出： 5说明：移除 5 颗石头的一种方法如下：移除石头 [2,2]，因为它与 [2,1] 共享同一行。移除石头 [2,1]，因为它与 [0,1] 共享同一列。移除石头 [1,2]，因为它与 [1,0] 共享同一行。移除石头 [1,0]，因为它与 [0,0] 共享同一列。移除石头 [0,1]，因为它与 [0,0] 共享同一行。石头 [0,0] 无法移除，因为它不与平面上的另一块石头共享行/列。
示例2：
输入： 石头 = [[0,0],[0,2],[1,1],[2,0],[2,2]]输出： 3说明：进行 3 步的一种方法如下：移除石头 [2,2]，因为它与 [2,0] 共享同一行。移除石头 [2,0]，因为它与 [0,0] 共享同一列。移除石头 [0,2]，因为它与 [0,0] 共享同一行。棋子 [0,0] 和 [1,1] 无法移除，因为它们不与平面上的另一个棋子共享行/列。
示例 3：
输入： 石头 = [[0,0]]输出： 0解释： [0,0] 是平面上唯一的石头，所以你无法移除它。
约束：
1 0 i, yi4没有两块石头位于同一坐标点。
解决方案：
我们可以使用深度优先搜索（dfs）方法来实现该解决方案。这个想法是将通过行或列连接的石头视为同一连接组件的一部分。一旦找到所有连通分量，可以移除的最大石子数量就是石子总数减去连通分量的数量。
让我们用 php 实现这个解决方案：947。同一行或同一列移除的大部分石头
解释：
dfs 函数:
dfs 函数用于探索同一连通分量中的所有石子。如果一块石头与当前石头相连（在同一行或同一列），我们会递归地对该石头执行 dfs。
主要功能：
我们迭代所有的石头，对于每一个没有被访问过的石头，我们执行 dfs 来标记同一个连接组件中的所有石头。我们计算连通分量的数量，结果是石子总数减去连通分量的数量（$n – $numcomponents）。
执行示例:
对于第一个示例，它正确地发现 5 个石头可以被移除，剩下 1 个石头无法移除。
复杂：
时间复杂度：由于嵌套循环和 dfs 遍历，o(n^2)。空间复杂度：存储访问过的石头的时间复杂度为 o(n)。
该解决方案应该在给定的限制内有效地工作。
联系链接
如果您发现本系列有帮助，请考虑在 github 上给存储库 一个星星，或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大！
如果您想要更多类似的有用内容，请随时关注我：
领英github
以上就是同一行或同一列移除的大部分石头的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1245682.html
微信扫一扫 
支付宝扫一扫 
