[Swift Weekly Contest 112]LeetCode947. 移除最多的同行或同列石头 | 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 s

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) -> Int29     {30         if upper[x] < 031         {32             return x33         }34         else35         {36             upper[x] = root(upper[x])37             return upper[x]38         }39     }40     41     public func equiv(_ x:Int,_ y:Int) -> Bool42     {43         return root(x) == root(y)44     }45     46     public func union(_ x:Int,_ y:Int) -> Bool47     {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 = x55                 x = y56                 y = d57             }58             upper[x] += upper[y]59             upper[y] = x60         }61         return x == y62     }63 64     public func count()-> Int 65     {66         var ct:Int = 067         for u in upper68         {69             if u < 070             {71                 ct += 172             }73         }74         return ct75     }76 }

总结

以上是内存溢出为你收集整理的[Swift Weekly Contest 112]LeetCode947. 移除最多的同行或同列石头 | Most Stones Removed with Same Row or Column全部内容，希望文章能够帮你解决[Swift Weekly Contest 112]LeetCode947. 移除最多的同行或同列石头 | Most Stones Removed with Same Row or Column所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。