0947. Most Stones Removed With Same Row or Column

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 为上一次遍历过的点的序号。经过这样的优化以后,时间复杂度会提高不少。

代码 #


package leetcode

import (
	"github.com/halfrost/LeetCode-Go/template"
)

func removeStones(stones [][]int) int {
	if len(stones) <= 1 {
		return 0
	}
	uf, rowMap, colMap := template.UnionFind{}, map[int]int{}, map[int]int{}
	uf.Init(len(stones))
	for i := 0; i < len(stones); i++ {
		if _, ok := rowMap[stones[i][0]]; ok {
			uf.Union(rowMap[stones[i][0]], i)
		} else {
			rowMap[stones[i][0]] = i
		}
		if _, ok := colMap[stones[i][1]]; ok {
			uf.Union(colMap[stones[i][1]], i)
		} else {
			colMap[stones[i][1]] = i
		}
	}
	return len(stones) - uf.TotalCount()
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者