[Swift]LeetCode1042.不邻接植花|FlowerPlantingWithNoAdjacent

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

You have N gardens, labelled 1 to N. In each garden, you want to plant one of 4 types of flowers.

paths[i] = [x, y] describes the existence of a bidirectional path from garden x to garden y.

Also, there is no garden that has more than 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)-th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.

Example 1:

Input: N = [[1,2],[2,3],[3,1]]
Output: [1,2,3]

Example 2:

Input: N = [[1,2],[3,4]]
Output: [1,2,1,2]

Example 3:

Input: N = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
Output: [1,2,3,4]

Note:

1 <= N <= 10000
0 <= paths.size <= 20000
No garden has 4 or more paths coming into or leaving it.
It is guaranteed an answer exists.

有 N 个花园，按从 1 到 N 标记。在每个花园中，你打算种下四种花之一。

paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。

另外，没有花园有 3 条以上的路径可以进入或者离开。

你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。

以数组形式返回选择的方案作为答案 answer，其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1, 2, 3, 4 表示。保证存在答案。

示例 1：

输入：N = 3, paths = [[1,2],[2,3],[3,1]]
输出：[1,2,3]

示例 2：

输入：N = 4, paths = [[1,2],[3,4]]
输出：[1,2,1,2]

示例 3：

输入：N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出：[1,2,3,4]

提示：

1 <= N <= 10000
0 <= paths.size <= 20000
不存在花园有 4 条或者更多路径可以进入或离开。
保证存在答案。

Runtime: 528 ms

Memory Usage: 22.3 MB

 1 class Solution {
 2     func gardenNoAdj(_ N: Int, _ paths: [[Int]]) -> [Int] {
 3         var G:[[Int]] = [[Int]](repeating: [Int](), count: N)
 4         for v in paths
 5         {
 6             let x:Int = v[0] - 1
 7             let y:Int = v[1] - 1
 8             G[x].append(y)
 9             G[y].append(x)
10         }
11         var res:[Int] = [Int](repeating: 0, count: N)
12         for v in 0..<N
13         {
14             var ss:Set<Int> = Set<Int>()
15             for u in G[v]
16             {
17                 ss.insert(res[u])
18             }
19             res[v] = 1
20             while(ss.contains(res[v]))
21             {
22                 res[v] += 1
23             }
24         }
25         return res
26     }
27 }

624ms

 1 class Solution {
 2     func gardenNoAdj(_ N: Int, _ paths: [[Int]]) -> [Int] {
 3         var g = [Int: Set<Int>]()
 4         for p in paths {
 5             g[p[0]-1, default: Set<Int>()].insert(p[1]-1)
 6             g[p[1]-1, default: Set<Int>()].insert(p[0]-1)
 7         }
 8         guard g.count > 1 else { return [Int](repeating: 1, count: N) }
 9         var ans = [Int](repeating: -1, count: N)
10         for c in 0..<N {
11             if ans[c] == -1 {
12                 ans[c] = 1
13                 recursive(g, c, &ans)
14             }
15         }
16         
17         for i in 0..<ans.endIndex {
18             if ans[i] == -1 {
19                 ans[i] = 1
20             }
21         }
22         
23         return ans
24     }
25     
26     private func recursive(_ paths: [Int: Set<Int>], _ cur: Int, _ ans: inout [Int]) {
27         guard paths[cur] != nil else { return }
28         for dest in paths[cur]!.sorted(by: {paths[$0]?.count ?? 0 > paths[$1]?.count ?? 0}) {
29             // print("cur: \(cur), dest: \(dest), color: \(ans)")
30             if ans[dest] == -1 {
31                 ans[dest] = selectColor(paths, dest, ans)
32             }
33         }
34     }
35     
36     private func selectColor(_ paths: [Int: Set<Int>], _ g: Int, _ ans: [Int]) -> Int {
37         var colors = Set<Int>([1, 2, 3, 4])
38         for s in paths[g]! {
39             if ans[s] != -1 {
40                 colors.remove(ans[s])
41             }
42         }
43         return colors.first!
44     }
45 }

708ms

 1 class Solution {
 2     func gardenNoAdj(_ N: Int, _ paths: [[Int]]) -> [Int] {
 3         var edges = [Int: [Int]]()
 4         
 5         for path in paths {
 6             let a = path[0]
 7             let b = path[1]
 8             
 9             if edges[a] == nil {
10                 edges[a] = [b]
11             } else {
12                 edges[a]?.append(b)
13             }
14             
15             if edges[b] == nil {
16                 edges[b] = [a]
17             } else {
18                 edges[b]?.append(a)
19             }
20         }
21         
22         var result = [Int](repeating: 0, count: N + 1)
23         var availableColors = Array(repeating: Set([1, 2, 3, 4]), count: N + 1)
24         var unvisited = Set(Array(1...N))
25         
26         while let first = unvisited.first {
27             var queue = Set([first])
28             while !queue.isEmpty {
29                 var nextQueue = Set<Int>()
30                 for node in queue {
31                     let color = availableColors[node].first!
32                     result[node] = color
33                     unvisited.remove(node)
34                     nextQueue.remove(node)
35                     for neighbor in edges[node, default: []] {
36                         availableColors[neighbor].remove(color)
37                         guard unvisited.contains(neighbor) else { continue }
38                         nextQueue.insert(neighbor)
39                     }
40                 }
41                 queue = nextQueue
42             }
43         }
44         
45         result.removeFirst()
46         
47         return result
48     }
49 }