1042 Flower Planting With No Adjacent 不鄰接植花
Description:
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:
Example 1:
Input: N = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]
Example 2:
Input: N = 4, paths = [[1,2],[3,4]]
Output: [1,2,1,2]
Example 3:
Input: N = 4, paths = [[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 個(gè)花園煌寇，按從 1 到 N 標(biāo)記。在每個(gè)花園中固逗，你打算種下四種花之一虐骑。
paths[i] = [x, y] 描述了花園 x 到花園 y 的雙向路徑坏挠。
另外师骗，沒(méi)有花園有 3 條以上的路徑可以進(jìn)入或者離開(kāi)屁擅。
你需要為每個(gè)花園選擇一種花仲义，使得通過(guò)路徑相連的任何兩個(gè)花園中的花的種類互不相同。
以數(shù)組形式返回選擇的方案作為答案 answer杠巡，其中 answer[i] 為在第 (i+1) 個(gè)花園中種植的花的種類量窘。花的種類用 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 條或者更多路徑可以進(jìn)入或離開(kāi)。
保證存在答案嫩海。
思路:
貪心法涂色, 題目保證了每個(gè)結(jié)點(diǎn)最多只有 3個(gè)出度(入度)
遍歷 paths數(shù)組, 將比自己小的結(jié)點(diǎn)存入表格中, 然后遍歷 N個(gè)結(jié)點(diǎn), 找到最小的未使用過(guò)的顏色加入結(jié)果
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(n)
代碼:
C++:
class Solution
{
public:
vector<int> gardenNoAdj(int N, vector<vector<int>>& paths)
{
vector<int> result(N, 1);
vector<vector<int>> record(N);
for (auto path : paths) record[max(path[0], path[1]) - 1].push_back(min(path[0], path[1]) - 1);
for (int i = 1; i < N; ++i)
{
int used[5]{0};
for (auto j : record[i]) used[result[j]] = 1;
for (int j = 4; j > 0; --j) if (!used[j]) result[i] = j;
}
return result;
}
};
Java:
class Solution {
public int[] gardenNoAdj(int N, int[][] paths) {
int result[] = new int[N];
Map<Integer, Set<Integer>> record = new HashMap<>(N);
for (int i = 0; i < N; i++) record.put(i, new HashSet<>());
for (int[] path : paths) record.get(Math.max(path[0], path[1]) - 1).add(Math.min(path[0], path[1]) - 1);
for (int i = 0; i < N; ++i) {
int used[] = new int[5];
for (int j : record.get(i)) used[result[j]] = 1;
for (int j = 4; j > 0; --j) if (used[j] == 0) result[i] = j;
}
return result;
}
}
Python:
class Solution:
def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
result, record = [1] * N, [set() for _ in range(N)]
for path in paths:
record[max(path[0], path[1]) - 1].add(min(path[0], path[1]) - 1)
for i in range(1, N):
result[i] = ({1, 2, 3, 4} - {result[j] for j in record[i]}).pop()
return result
