[Swift]LeetCode684. 冗余连接 | Redundant Connection

[Swift]LeetCode684. 冗余连接 | Redundant Connection,第1张

概述In this problem, a tree is an undirected graph that is connected and has no cycles. The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additio

In this problem,a tree is an undirected graph that is connected and has no cycles.

The given input is a graph that started as a tree with N nodes (with distinct values 1,2,...,N),with one additional edge added. The added edge has two different vertices chosen from 1 to N,and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u,v] with u < v,that represents an undirected edge connecting nodes u and v.

Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers,return the answer that occurs last in the given 2D-array. The answer edge [u,v] should be in the same format,with u < v.

Example 1:

input: [[1,2],[1,3],[2,3]]Output: [2,3]Explanation: The given undirected graph will be like this:  1 / 2 - 3 

Example 2:

input: [[1,[3,4],5]]Output: [1,4]Explanation: The given undirected graph will be like this:5 - 1 - 2    |   |    4 - 3 

Note:

The size of the input 2D-array will be between 3 and 1000. Every integer represented in the 2D-array will be between 1 and N,where N is the size of the input array.

Update (2017-09-26):
We have overhauled the problem description + test cases and specifIEd clearly the graph is an undirectedgraph. For the directed graph follow up please see Redundant Connection II). We apologize for any inconvenIEnce caused.

在本问题中,树指的是一个连通且无环的无向图。

输入一个图,该图由一个有着N个节点 (节点值不重复1,N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。

结果图是一个以组成的二维数组。每一个的元素是一对[u,v] ,满足 u < v,表示连接顶点u 和v的无向图的边。

返回一条可以删去的边,使得结果图是一个有着N个节点的树。如果有多个答案,则返回二维数组中最后出现的边。答案边 [u,v] 应满足相同的格式 u < v

示例 1:

输入: [[1,3]]输出: [2,3]解释: 给定的无向图为:  1 / 2 - 3

示例 2:

输入: [[1,5]]输出: [1,4]解释: 给定的无向图为:5 - 1 - 2    |   |    4 - 3

注意:

输入的二维数组大小在 3 到 1000。 二维数组中的整数在1到N之间,其中N是输入数组的大小。

更新(2017-09-26):
我们已经重新检查了问题描述及测试用例,明确图是无向 图。对于有向图详见冗余连接II。对于造成任何不便,我们深感歉意。

Runtime: 28 ms Memory Usage: 18.9 MB
 1 class Solution { 2     func findRedundantConnection(_ edges: [[Int]]) -> [Int] { 3         var root:[Int] = [Int](repeating:-1,count:2001) 4         for edge in edges 5         { 6             var x:Int = find(&root,edge[0]) 7             var y:Int = find(&root,edge[1]) 8             if x == y {return edge} 9             root[x] = y10         }11         return [Int]()12     }13     14     func find (_ root:inout [Int],_ i:Int) -> Int15     {16         var i = i17         while (root[i] != -1)18         {19             i = root[i]20         }21         return i22     }23 }

32ms

 1 class Solution { 2     func findRedundantConnection(_ edges: [[Int]]) -> [Int] { 3         guard edges.isEmpty == false else { 4             return [] 5         } 6         let n = edges.count 7         var parents: [Int] = [] 8         for i in 0...n { 9             parents.append(i)10         }11         for edge in edges {12             let first = edge[0]13             let second = edge[1]14             let p1 = find(parents,first)15             let p2 = find(parents,second)16             if p1 == p2 {17                 return edge18             }19             parents[p2] = p120         }21         return []22     }23     24     private func find(_ parents: [Int],_ val: Int) -> Int {25         if parents[val] == val {26             return val27         }28         return find(parents,parents[val])29     }30 }

48ms

 1 class Solution { 2     @H_96_403@//@H_96_403@ s1: union find 3     func findRedundantConnection(_ edges: [[Int]]) -> [Int] { 4         var uf = UnionFind(n: edges.count+1) 5         for con in edges { 6             let s = con[0] 7             let e = con[1] 8             if uf.union(s,e) == false { 9                 return con10             } 11         }12         return []13     }14 }15 16 class UnionFind {17     public var parents = [Int]()18     private var ranks = [Int]()19     public var count: Int = 020     init(n: Int) {21         for i in 0..<n {22             parents.append(i)23             ranks.append(1)24         }25     }26     27     func find(_ x: Int) -> Int {28         var x = x29         if parents[x] != x {30             parents[x] = find(parents[x])31         }32         return parents[x]33     }34     @H_96_403@/*35 @H_96_403@    1 2 336 @H_96_403@    5 637     @H_96_403@*/38     func union(_ x: Int,_ y: Int) -> Bool {39         let px = find(x)40         let py = find(y)41         if px == py {42             return false43         }44         count -= 145         if ranks[x] > ranks[y] {46             parents[py] = px47         } else if ranks[x] < ranks[y] {48             parents[px] = py49         } else {50             parents[py] = px51             ranks[px] += 152         }53         return true54     }55 }

52ms

 1 class Solution { 2     func findRedundantConnection(_ edges: [[Int]]) -> [Int] { 3         guard edges.count > 0 else { return [0,0] } 4  5         var totalNode = edges.count + 1 6          7         var group: [Int] = [] 8         var groupLevel: [Int] = [] 9         10         for i in 0..<totalNode {11             group.append(i)12             groupLevel.append(0)13         }14         15         var extraEdge:[Int] = []16         17         for edge in edges {18            var nodeX = edge[0]19            var nodeY = edge[1]20             21            var pNodeX =  findParent(nodeX,&group)22            var pNodeY =  findParent(nodeY,&group)23            if pNodeX != pNodeY {24                 if groupLevel[pNodeX] > groupLevel[pNodeY] {25                     group[pNodeY] = pNodeX26                 }else if groupLevel[pNodeX] < groupLevel[pNodeY] {27                     group[pNodeX] = pNodeY28                 }else {29                     group[pNodeY] = pNodeX30                     groupLevel[pNodeX] += 131                 }32            }else {33                extraEdge = edge34            }35         }36         return extraEdge37     }38         39     40     func findParent(_ node: Int,_ group: inout [Int]) -> Int {41         var currentNode = node42         while currentNode != group[currentNode] {43             group[currentNode] = group[group[currentNode]]44             currentNode = group[currentNode]45         }46         47         return currentNode48     }49 }

64ms

  1 class Solution {  2       3     struct Edge {  4         var w: Int  5         var a: Int  6         var b: Int  7     }  8       9     func findRedundantConnection(_ _edges: [[Int]]) -> [Int] { 10         var wEdges = [Int: [(Int,Int)]]() 11         for (i,edge) in _edges.enumerated() { 12             wEdges[edge[0],default: []].append((edge[1],i)) 13             wEdges[edge[1],default: []].append((edge[0],i)) 14         } 15         var safe: Set<Int> = [] 16         var heap = Heap<((Int,Int),Int)>(sort: { 17             $0.1 < $1.1 18         }) 19         let source = _edges[0][0] 20         var edges = Set<[Int]>() 21         safe.insert(source) 22         for n in wEdges[source]! { 23             heap.insert( ((source,n.0),n.1) ) 24         } 25         while !heap.isEmpty { 26             let ((source,node),_) = heap.remove()! 27             safe.insert(node) 28             edges.insert([source,node]) 29             edges.insert([node,source]) 30             for n in wEdges[node]! { 31                 if edges.contains( [n.0,node] ) { 32                      33                 } else if safe.contains(n.0) { 34                     return [node,n.0].sorted() 35                 } else { 36                     heap.insert( ((node,n.1) ) 37                 } 38             } 39         } 40          41         return _edges.last! 42     } 43 } 44  45  46  47  48  49 public struct Heap<T> { 50    51   @H_96_403@/*@H_96_403@* The array that stores the heap‘s nodes. @H_96_403@*/ 52   var nodes = [T]() 53    54   @H_96_403@/*@H_96_403@* 55 @H_96_403@   * Determines how to compare two nodes in the heap. 56 @H_96_403@   * Use ‘>‘ for a max-heap or ‘<‘ for a min-heap, 57 @H_96_403@   * or provIDe a comparing method if the heap is made 58 @H_96_403@   * of custom elements,for example tuples. 59    @H_96_403@*/ 60   private var orderCriteria: (T,T) -> Bool 61    62   @H_96_403@/*@H_96_403@* 63 @H_96_403@   * Creates an empty heap. 64 @H_96_403@   * The sort function determines whether this is a min-heap or max-heap. 65 @H_96_403@   * For comparable data types,> makes a max-heap,< makes a min-heap. 66    @H_96_403@*/ 67   public init(sort: @escaPing (T,T) -> Bool) { 68     self.orderCriteria = sort 69   } 70    71   @H_96_403@/*@H_96_403@* 72 @H_96_403@   * Creates a heap from an array. The order of the array does not matter; 73 @H_96_403@   * the elements are inserted into the heap in the order determined by the 74 @H_96_403@   * sort function. For comparable data types,‘>‘ makes a max-heap, 75 @H_96_403@   * ‘<‘ makes a min-heap. 76    @H_96_403@*/ 77   public init(array: [T],sort: @escaPing (T,T) -> Bool) { 78     self.orderCriteria = sort 79     configureHeap(from: array) 80   } 81    82   @H_96_403@/*@H_96_403@* 83 @H_96_403@   * Configures the max-heap or min-heap from an array,in a bottom-up manner. 84 @H_96_403@   * Performance: This runs pretty much in O(n). 85    @H_96_403@*/ 86   private mutating func configureHeap(from array: [T]) { 87     nodes = array 88     for i in strIDe(from: (nodes.count/2-1),through: 0,by: -1) { 89       shiftDown(i) 90     } 91   } 92    93   public var isEmpty: Bool { 94     return nodes.isEmpty 95   } 96    97   public var count: Int { 98     return nodes.count 99   }100   101   @H_96_403@/*@H_96_403@*102 @H_96_403@   * Returns the index of the parent of the element at index i.103 @H_96_403@   * The element at index 0 is the root of the tree and has no parent.104    @H_96_403@*/105   @inline(__always) internal func parentIndex(ofIndex i: Int) -> Int {106     return (i - 1) / 2107   }108   109   @H_96_403@/*@H_96_403@*110 @H_96_403@   * Returns the index of the left child of the element at index i.111 @H_96_403@   * Note that this index can be greater than the heap size,in which case112 @H_96_403@   * there is no left child.113    @H_96_403@*/114   @inline(__always) internal func leftChildindex(ofIndex i: Int) -> Int {115     return 2*i + 1116   }117   118   @H_96_403@/*@H_96_403@*119 @H_96_403@   * Returns the index of the right child of the element at index i.120 @H_96_403@   * Note that this index can be greater than the heap size,in which case121 @H_96_403@   * there is no right child.122    @H_96_403@*/123   @inline(__always) internal func rightChildindex(ofIndex i: Int) -> Int {124     return 2*i + 2125   }126   127   @H_96_403@/*@H_96_403@*128 @H_96_403@   * Returns the maximum value in the heap (for a max-heap) or the minimum129 @H_96_403@   * value (for a min-heap).130    @H_96_403@*/131   public func peek() -> T? {132     return nodes.first133   }134   135   @H_96_403@/*@H_96_403@*136 @H_96_403@   * Adds a new value to the heap. This reorders the heap so that the max-heap137 @H_96_403@   * or min-heap property still holds. Performance: O(log n).138    @H_96_403@*/139   public mutating func insert(_ value: T) {140     nodes.append(value)141     shiftUp(nodes.count - 1)142   }143   144   @H_96_403@/*@H_96_403@*145 @H_96_403@   * Adds a sequence of values to the heap. This reorders the heap so that146 @H_96_403@   * the max-heap or min-heap property still holds. Performance: O(log n).147    @H_96_403@*/148   public mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T {149     for value in sequence {150       insert(value)151     }152   }153   154   @H_96_403@/*@H_96_403@*155 @H_96_403@   * Allows you to change an element. This reorders the heap so that156 @H_96_403@   * the max-heap or min-heap property still holds.157    @H_96_403@*/158   public mutating func replace(index i: Int,value: T) {159     guard i < nodes.count else { return }160     161     remove(at: i)162     insert(value)163   }164   165   @H_96_403@/*@H_96_403@*166 @H_96_403@   * Removes the root node from the heap. For a max-heap,this is the maximum167 @H_96_403@   * value; for a min-heap it is the minimum value. Performance: O(log n).168    @H_96_403@*/169   @discardableResult public mutating func remove() -> T? {170     guard !nodes.isEmpty else { return nil }171     172     if nodes.count == 1 {173       return nodes.removeLast()174     } else {175       @H_96_403@//@H_96_403@ Use the last node to replace the first one,then fix the heap by176       @H_96_403@//@H_96_403@ shifting this new first node into its proper position.177       let value = nodes[0]178       nodes[0] = nodes.removeLast()179       shiftDown(0)180       return value181     }182   }183   184   @H_96_403@/*@H_96_403@*185 @H_96_403@   * Removes an arbitrary node from the heap. Performance: O(log n).186 @H_96_403@   * Note that you need to kNow the node‘s index.187    @H_96_403@*/188   @discardableResult public mutating func remove(at index: Int) -> T? {189     guard index < nodes.count else { return nil }190     191     let size = nodes.count - 1192     if index != size {193       nodes.swapAt(index,size)194       shiftDown(from: index,until: size)195       shiftUp(index)196     }197     return nodes.removeLast()198   }199   200   @H_96_403@/*@H_96_403@*201 @H_96_403@   * Takes a child node and looks at its parents; if a parent is not larger202 @H_96_403@   * (max-heap) or not smaller (min-heap) than the child,we exchange them.203    @H_96_403@*/204   internal mutating func shiftUp(_ index: Int) {205     var childindex = index206     let child = nodes[childindex]207     var parentIndex = self.parentIndex(ofIndex: childindex)208     209     while childindex > 0 && orderCriteria(child,nodes[parentIndex]) {210       nodes[childindex] = nodes[parentIndex]211       childindex = parentIndex212       parentIndex = self.parentIndex(ofIndex: childindex)213     }214     215     nodes[childindex] = child216   }217   218   @H_96_403@/*@H_96_403@*219 @H_96_403@   * Looks at a parent node and makes sure it is still larger (max-heap) or220 @H_96_403@   * smaller (min-heap) than its childeren.221    @H_96_403@*/222   internal mutating func shiftDown(from index: Int,until endindex: Int) {223     let leftChildindex = self.leftChildindex(ofIndex: index)224     let rightChildindex = leftChildindex + 1225     226     @H_96_403@//@H_96_403@ figure out which comes first if we order them by the sort function:227     @H_96_403@//@H_96_403@ the parent,the left child,or the right child. If the parent comes228     @H_96_403@//@H_96_403@ first,we‘re done. If not,that element is out-of-place and we make229     @H_96_403@//@H_96_403@ it "float down" the tree until the heap property is restored.230     var first = index231     if leftChildindex < endindex && orderCriteria(nodes[leftChildindex],nodes[first]) {232       first = leftChildindex233     }234     if rightChildindex < endindex && orderCriteria(nodes[rightChildindex],nodes[first]) {235       first = rightChildindex236     }237     if first == index { return }238     239     nodes.swapAt(index,first)240     shiftDown(from: first,until: endindex)241   }242   243   internal mutating func shiftDown(_ index: Int) {244     shiftDown(from: index,until: nodes.count)245   }246   247 }248 249 @H_96_403@//@H_96_403@ MARK: - Searching250 extension Heap where T: Equatable {251   252   @H_96_403@/*@H_96_403@* Get the index of a node in the heap. Performance: O(n). @H_96_403@*/253   public func index(of node: T) -> Int? {254     return nodes.index(where: { $0 == node })255   }256   257   @H_96_403@/*@H_96_403@* Removes the first occurrence of a node from the heap. Performance: O(n log n). @H_96_403@*/258   @discardableResult public mutating func remove(node: T) -> T? {259     if let index = index(of: node) {260       return remove(at: index)261     }262     return nil263   }  264 }

88ms

 1 class Solution { 2  3     func findRedundantConnection(_ edges: [[Int]]) -> [Int] { 4         var N = 0 5         var graph = [Int: Set<Int>]() 6         for edge in edges { 7             graph[edge[0],default: []].insert(edge[1]) 8             graph[edge[1],default: []].insert(edge[0]) 9             N = max(N,edge[0],edge[1])10         }11         let source = edges[0][0]12         for edge in edges.reversed() {13             if isConnected(graph,edge,source,N) {14                 return edge15             }16         }17         return edges.last!18     }19     20     func isConnected(_ graph: [Int: Set<Int>],_ edge: [Int],_ source: Int,_ N: Int) -> Bool {21         var graph = graph22         graph[edge[0]]!.remove(edge[1])23         graph[edge[1]]!.remove(edge[0])24         var stack = [Int]()25         var visited = Set<Int>()26         stack.append(source)27         while !stack.isEmpty {28             let node = stack.popLast()!29             visited.insert(node)30             for edge in graph[node] ?? [] {31                 if !visited.contains(edge) {32                     stack.append(edge)33                 }34             }35         }36         37         return visited.count == N38     }39 }

112ms

 1 class Solution { 2      3     let MAX_EDGE_VAL = 1000 4      5     func findRedundantConnection(_ edges: [[Int]]) -> [Int] { 6         var graph = [Int: [Int]]() 7          8         for edge in edges { 9             let u = edge[0]10             let v = edge[1]11             var visited = Set<Int>()12             if hasPath(&graph,&visited,u,v) {13                 return [u,v]14             }15             graph[u] = graph[u] ?? [Int]()16             graph[u]!.append(v)17             graph[v] = graph[v] ?? [Int]()18             graph[v]!.append(u)19         }20         return [-1,-1]21     }22     23     public func hasPath(_ graph: inout [Int: [Int]],_ visited: inout Set<Int>,_ target: Int) -> Bool {24         if source == target {25             return true26         }27         if !graph.keys.contains(source) || !graph.keys.contains(target) {28             return false29         }30         visited.insert(source)31         if let neighbers = graph[source] {32             for neighber in neighbers {33                 if visited.contains(neighber) {34                     continue35                 }36                 if hasPath(&graph,neighber,target) {37                     return true38                 }39             }   40         }41         return false42     }43 }
总结

以上是内存溢出为你收集整理的[Swift]LeetCode684. 冗余连接 | Redundant Connection全部内容,希望文章能够帮你解决[Swift]LeetCode684. 冗余连接 | Redundant Connection所遇到的程序开发问题。

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

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/web/1019516.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-23
下一篇 2022-05-23

发表评论

登录后才能评论

评论列表(0条)

保存