Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
947. Most Stones Removed with Same Row or Column.go
947. Most Stones Removed with Same Row or Column_test.go
README.md

README.md

947. 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 为上一次遍历过的点的序号。经过这样的优化以后,时间复杂度会提高不少。
You can’t perform that action at this time.