mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-07 01:44:56 +08:00
49 lines
2.2 KiB
Markdown
Executable File
49 lines
2.2 KiB
Markdown
Executable File
# [947. Most Stones Removed with Same Row or Column](https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/)
|
||
|
||
|
||
## 题目
|
||
|
||
On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.
|
||
|
||
Now, a *move* consists of removing a stone that shares a column or row with another stone on the grid.
|
||
|
||
What is the largest possible number of moves we can make?
|
||
|
||
**Example 1:**
|
||
|
||
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
|
||
Output: 5
|
||
|
||
**Example 2:**
|
||
|
||
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
|
||
Output: 3
|
||
|
||
**Example 3:**
|
||
|
||
Input: stones = [[0,0]]
|
||
Output: 0
|
||
|
||
**Note:**
|
||
|
||
1. `1 <= stones.length <= 1000`
|
||
2. `0 <= stones[i][j] < 10000`
|
||
|
||
|
||
## 题目大意
|
||
|
||
在二维平面上，我们将石头放置在一些整数坐标点上。每个坐标点上最多只能有一块石头。现在，move 操作将会移除与网格上的某一块石头共享一列或一行的一块石头。我们最多能执行多少次 move 操作？
|
||
|
||
提示：
|
||
|
||
- 1 <= stones.length <= 1000
|
||
- 0 <= stones[i][j] < 10000
|
||
|
||
|
||
## 解题思路
|
||
|
||
|
||
- 给出一个数组，数组中的元素是一系列的坐标点。现在可以移除一些坐标点，移除必须满足：移除的这个点，在相同的行或者列上有一个点。问最终可以移除多少个点。移除到最后必然有些点独占一行，那么这些点都不能被移除。
|
||
- 这一题的解题思路是并查集。把所有共行或者共列的点都 `union()` 起来。不同集合之间是不能相互移除的。反证法：如果能移除，代表存在共行或者共列的情况，那么肯定是同一个集合了，这样就不满足不同集合了。最终剩下的点就是集合的个数，每个集合只会留下一个点。所以移除的点就是点的总数减去集合的个数 `len(stones) - uf.totalCount()`。
|
||
- 如果暴力合并集合，时间复杂度也非常差，可以由优化的地方。再遍历所有点的过程中，可以把遍历过的行和列存起来。这里可以用 map 来记录，key 为行号，value 为上一次遍历过的点的序号。同样，列也可以用 map 存起来，key 为列号，value 为上一次遍历过的点的序号。经过这样的优化以后，时间复杂度会提高不少。
|