。同一行或同一列移除的大部分石头
Aug 30, 2024 am 06:37 AM947。同一行或同一列移除的大部分石头
难度:中等
主题:哈希表、深度优先搜索、并集查找、图
在 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, yi 4
- 没有两块石头位于同一坐标点。
解决方案:
我们可以使用深度优先搜索(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 ?>
登录后复制
解释:
-
DFS 函数:
- dfs 函数用于探索同一连通分量中的所有石子。如果一块石头与当前石头相连(在同一行或同一列),我们会递归地对该石头执行 DFS。
-
主要功能:
- 我们迭代所有的石头,对于每一个没有被访问过的石头,我们执行 DFS 来标记同一个连接组件中的所有石头。
- 我们计算连通分量的数量,结果是石子总数减去连通分量的数量($n - $numComponents)。
-
执行示例:
- 对于第一个示例,它正确地发现 5 个石头可以被移除,剩下 1 个石头无法移除。
复杂:
- 时间复杂度:由于嵌套循环和 DFS 遍历,O(n^2)。
- 空间复杂度:存储访问过的石头的时间复杂度为 O(n)。
该解决方案应该在给定的限制内有效地工作。
联系链接
如果您发现本系列有帮助,请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大!
如果您想要更多类似的有用内容,请随时关注我:
- 领英
- GitHub
以上是。同一行或同一列移除的大部分石头的详细内容。更多信息请关注PHP中文网其他相关文章!
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门文章
击败分裂小说需要多长时间?
3 周前
By DDD
仓库:如何复兴队友
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
公众号网页更新缓存难题:如何避免版本更新后旧缓存影响用户体验?
3 周前
By 王林
R.E.P.O.能量晶体解释及其做什么(黄色晶体)
1 周前
By 尊渡假赌尊渡假赌尊渡假赌

热门文章
击败分裂小说需要多长时间?
3 周前
By DDD
仓库:如何复兴队友
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
公众号网页更新缓存难题:如何避免版本更新后旧缓存影响用户体验?
3 周前
By 王林
R.E.P.O.能量晶体解释及其做什么(黄色晶体)
1 周前
By 尊渡假赌尊渡假赌尊渡假赌

热门文章标签

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)