客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ 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： 输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] 输出：5 示例 2： 输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]] 输出：3 示例 3： 输入：stones = [[0,0]] 输出：0 提示：
272ms 1 class Solution { 2 class Coordinate:Hashable{ 3 static func == (lhs: Coordinate, rhs: Coordinate) -> Bool { 4 return lhs.x == rhs.x && lhs.y == rhs.y; 5 } 6 7 let x:Int; 8 let y:Int; 9 init(x:Int,y:Int) { 10 self.x = x; 11 self.y = y; 12 } 13 var hashValue:Int{ 14 return x.hashValue ^ y.hashValue; 15 } 16 } 17 class Vertex:Hashable,Comparable{ 18 var hashValue:Int{ 19 get{ 20 return co.hashValue; 21 } 22 } 23 static func < (lhs: Vertex, rhs: Vertex) -> Bool { 24 return lhs.degree < rhs.degree; 25 } 26 27 static func == (lhs: Vertex, rhs: Vertex) -> Bool { 28 return lhs.co == rhs.co; 29 } 30 let co:Coordinate; 31 var neighbors:Set<Vertex>; 32 var degree:Int{ 33 get { 34 return neighbors.count; 35 } 36 } 37 var traversed:Bool; 38 init(x:Int,y:Int) { 39 self.co = Coordinate(x: x, y: y); 40 neighbors = Set<Vertex>(); 41 traversed = false; 42 } 43 } 44 var max = 0; 45 func removeStones(_ stones: [[Int]]) -> Int { 46 max = 0; 47 if stones.count < 2{ 48 return 0; 49 } 50 var allStones = Dictionary<Coordinate,Vertex>(); 51 var xDict = Dictionary<Int,Array<Coordinate>>(); 52 var yDict = Dictionary<Int,Array<Coordinate>>(); 53 for stone in stones{ 54 let x = stone[0]; 55 let y = stone[1]; 56 let co = Coordinate(x: x, y: y); 57 let vertex = Vertex(x: x, y: y); 58 allStones[co] = vertex; 59 if xDict[x] == nil{ 60 xDict[x] = Array<Coordinate>() 61 } 62 if yDict[y] == nil{ 63 yDict[y] = Array<Coordinate>() 64 } 65 xDict[x]!.append(co); 66 yDict[y]!.append(co); 67 } 68 69 for coco in allStones.keys{ 70 let v = allStones[coco]!; 71 let x = coco.x; 72 let y = coco.y; 73 // let keys = allStones.keys; 74 var leftClosest:Coordinate? 75 var rightClosest:Coordinate? 76 var topClosest:Coordinate? 77 var bottomClosest:Coordinate? 78 for c in xDict[x]!{ 79 if c.y != y{ 80 if c.y < y{ 81 if topClosest == nil || topClosest!.y < c.y{ 82 topClosest = c; 83 } 84 }else{ 85 if bottomClosest == nil || bottomClosest!.y > c.y{ 86 bottomClosest = c; 87 } 88 } 89 } 90 } 91 for c in yDict[y]!{ 92 if c.x != x{ 93 if c.x < x{ 94 if leftClosest == nil || leftClosest!.x < c.x{ 95 leftClosest = c; 96 } 97 }else{ 98 if rightClosest == nil || rightClosest!.y > c.y{ 99 rightClosest = c; 100 } 101 } 102 } 103 } 104 if leftClosest != nil{ 105 v.neighbors.insert(allStones[leftClosest!]!) 106 } 107 if rightClosest != nil{ 108 v.neighbors.insert(allStones[rightClosest!]!) 109 } 110 if topClosest != nil{ 111 v.neighbors.insert(allStones[topClosest!]!) 112 } 113 if bottomClosest != nil{ 114 v.neighbors.insert(allStones[bottomClosest!]!) 115 } 116 } 117 for v in allStones.values{ 118 let n = dfs(vertex: v) - 1; 119 if n > 0{ 120 max += n; 121 } 122 } 123 return max; 124 } 125 func dfs(vertex:Vertex) -> Int { 126 if vertex.traversed{ 127 return 0; 128 }else{ 129 var sum = 1; 130 vertex.traversed = true; 131 for v in vertex.neighbors{ 132 sum += dfs(vertex: v); 133 } 134 return sum; 135 } 136 } 137 } 316ms 1 class Solution { 2 func removeStones(_ stones: [[Int]]) -> Int { 3 guard stones.count > 0 else { 4 return 0 5 } 6 var v = [Int](repeating: 0, count: stones.count) 7 var dr = [Int: [Int]]() 8 var dc = [Int: [Int]]() 9 for i in 0 ..< stones.count { 10 let s = stones[i] 11 dr[s[1], default: [Int]()].append(i) 12 dc[s[0], default: [Int]()].append(i) 13 } 14 func bfs(_ i: Int) { 15 var qs = [stones[i]] 16 while !qs.isEmpty { 17 //print(v) 18 let u = qs.remove(at: 0) 19 let rs = dr[u[1], default: [Int]()] 20 let cs = dc[u[0], default: [Int]()] 21 var d = [Int: Bool]() 22 let ns = rs + cs 23 for n in ns { 24 d[n] = true 25 } 26 let ks = Array(d.keys) 27 for k in ks { 28 if v[k] != 2 { 29 v[k] += 1 30 } 31 } 32 qs += ks.filter {v[$0] == 1}.map {stones[$0]} 33 } 34 } 35 var res = 0 36 for i in 0 ..< stones.count { 37 guard v[i] != 2 else { 38 continue 39 } 40 res += 1 41 bfs(i) 42 } 43 return stones.count - res 44 45 } 46 } 1284ms 1 class Solution { 2 func removeStones(_ stones: [[Int]]) -> Int { 3 4 let unionFind = UnionFind(stones.count) 5 for i in 0..<stones.count-1 { 6 for j in i+1..<stones.count { 7 if stones[i][0] == stones[j][0] || 8 stones[i][1] == stones[j][1] { 9 unionFind.union(i, j) 10 } 11 } 12 } 13 14 var counter = 0 15 for i in 0..<unionFind.root.count { 16 if unionFind.root[i] != i { 17 counter += 1 18 } 19 } 20 return counter 21 } 22 } 23 24 class UnionFind { 25 var root = [Int]() 26 var rank = [Int]() 27 28 public init(_ n: Int) { 29 // if root is not initialized, 'self' captured by a closure before all members were initialized 30 (0...n-1).forEach { root.append($0) } 31 rank = [Int](repeating: 1, count: n) 32 } 33 34 fileprivate func find(_ current: Int) -> Int { 35 var path = [Int]() 36 var current = current 37 while root[current] != current { 38 path.append(current) 39 current = root[current] 40 } 41 42 for p in path { 43 root[p] = current 44 } 45 return current 46 } 47 48 public func union(_ x: Int, _ y: Int) { 49 let xRoot = find(x) 50 let yRoot = find(y) 51 52 if xRoot == yRoot { 53 return 54 } 55 if rank[xRoot] > rank[yRoot] { 56 root[yRoot] = xRoot 57 } else if rank[xRoot] < rank[yRoot] { 58 root[xRoot] = yRoot 59 } else { 60 rank[xRoot] = root[xRoot] + 1 61 root[xRoot] = yRoot 62 } 63 } 64 } 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 } 1476ms
1 class Solution { 2 func removeStones(_ stones: [[Int]]) -> Int { 3 4 var xPointsMap:[Int:[[Int]]] = [:] 5 var yPointsMap:[Int:[[Int]]] = [:] 6 var xTag:[Int:Int] = [:] 7 var yTag:[Int:Int] = [:] 8 9 // merge by x and y 10 for stone in stones { 11 12 let x = stone[0] 13 let y = stone[1] 14 if let _ = xPointsMap[x] { 15 xPointsMap[x]!.append(stone) 16 } else { 17 xPointsMap[x] = [stone] 18 } 19 20 if let _ = yPointsMap[y] { 21 yPointsMap[y]!.append(stone) 22 } else { 23 yPointsMap[y] = [stone] 24 } 25 } 26 27 // init x tags and y tags 28 for (x,_) in xPointsMap { 29 xTag[x] = 0 30 } 31 for (y,_) in yPointsMap { 32 yTag[y] = 0 33 } 34 35 var totalMove = 0 36 37 var currentTag = 1 38 while true { 39 var startX:Int? 40 for (x,tag) in xTag { 41 if tag == 0 { 42 startX = x 43 } 44 } 45 if let sx = startX { 46 var xSet:Set<Int> = [sx] 47 func yforxSet(_ xSet:Set<Int>) -> Set<Int> { 48 var ySet:Set<Int> = [] 49 for x in xSet { 50 for point in xPointsMap[x] ?? [] { 51 let y = point[1] 52 if yTag[y] == 0 { 53 ySet.insert(y) 54 } 55 } 56 } 57 return ySet 58 } 59 60 func xforySet(_ ySet:Set<Int>) -> Set<Int> { 61 var xSet:Set<Int> = [] 62 for y in ySet { 63 for point in yPointsMap[y] ?? [] { 64 let x = point[0] 65 if xTag[x] == 0 { 66 xSet.insert(x) 67 } 68 } 69 } 70 return xSet 71 } 72 var ySet = yforxSet(xSet) 73 var deltaY:Set<Int> = ySet 74 75 while true { 76 var thisX = xforySet(deltaY) 77 var deltaX = thisX.subtracting(xSet) 78 if (deltaX.count == 0) { 79 break; 80 } 81 xSet = xSet.union(deltaX) 82 var thisY = yforxSet(deltaX) 全部评论
专题导读
热门推荐
热门话题
阅读排行榜
|
请发表评论