[Swift Weekly Contest 112]LeetCode947. 移除最多的同行或同列

发布时间：2020-12-14 05:09:43 所属栏目：百科来源：网络整理

导读：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 p

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,2],[2,2]]
Output: 5

Example 2:

Input: stones = [[0,2]]
Output: 3

Example 3:

Input: stones = [[0,0]]
Output: 0

Note:

1 <= stones.length <= 1000
0 <= stones[i][j] < 10000

在二维平面上，我们将石头放置在一些整数坐标点上。每个坐标点上最多只能有一块石头。

现在，move?操作将会移除与网格上的另一块石头共享一列或一行的石头。

我们最多能执行多少次?move?操作？

示例 1：

输入：stones = [[0,2]]
输出：5

示例 2：

输入：stones = [[0,2]]
输出：3

示例 3：

输入：stones = [[0,0]]
输出：0

提示：

1 <= stones.length <= 1000
0 <= stones[i][j] < 10000

1436ms

 1 class Solution {
 2     func removeStones(_ stones: [[Int]]) -> Int {
 3         var n:Int = stones.count
 4         var ds:DJSet = DJSet(n)
 5         for i in 0..<n
 6         {
 7             for j in (i + 1)..<n
 8             {
 9                 if stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]
10                 {
11                     ds.union(i,j)
12                 }
13             }
14         }
15         return n-ds.count()
16     }
17 }
18 
19 public class DJSet 
20 {
21     var upper:[Int] = [Int]()
22     
23     public init(_ n:Int)
24     {
25         upper = [Int](repeating:-1,count: n)
26     }
27     
28     public func root(_ x:Int) -> Int
29     {
30         if upper[x] < 0
31         {
32             return x
33         }
34         else
35         {
36             upper[x] = root(upper[x])
37             return upper[x]
38         }
39     }
40     
41     public func equiv(_ x:Int,_ y:Int) -> Bool
42     {
43         return root(x) == root(y)
44     }
45     
46     public func union(_ x:Int,_ y:Int) -> Bool
47     {
48         var x:Int = root(x)
49         var y:Int = root(y)
50         if (x != y)
51         {
52             if (upper[y] < upper[x]) 
53             {
54                 var d:Int = x
55                 x = y
56                 y = d
57             }
58             upper[x] += upper[y]
59             upper[y] = x
60         }
61         return x == y
62     }
63 
64     public func count()-> Int 
65     {
66         var ct:Int = 0
67         for u in upper
68         {
69             if u < 0
70             {
71                 ct += 1
72             }
73         }
74         return ct
75     }
76 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!