Сложность: medium
У вас есть n садов, помеченных от 1 до n, и массив paths, где paths[i] = [xi, yi] описывает двунаправленный путь между садом xi и садом yi. В каждом саду вы хотите посадить один из 4 типов цветов. Все сады имеют не более 3 путей, входящих и выходящих из него. Ваша задача - выбрать тип цветка для каждого сада так, чтобы для любых двух садов, соединенных путем, они имели разные типы цветов. Верните любой такой выбор в виде массива answer, где answer[i] - тип цветка, посаженного в (i+1)-м саду. Типы цветов обозначаются 1, 2, 3 или 4. Ответ гарантированно существует.
Пример:
Input: n = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]
👨💻 Алгоритм:
1⃣Построение графа:
Создайте граф из садов и путей между ними.
2⃣Присваивание цветов:
Для каждого сада выберите тип цветка, который не используется соседними садами.
3⃣Мы будем проходить по каждому саду и выбирать тип цветка, который не совпадает с типами цветов в соседних садах. Поскольку у каждого сада не более трех соседей, всегда будет возможность выбрать тип цветка из 4 возможных типов.
😎 Решение:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public int[] gardenNoAdj(int n, int[][] paths) {
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] path : paths) {
graph[path[0] - 1].add(path[1] - 1);
graph[path[1] - 1].add(path[0] - 1);
}
int[] answer = new int[n];
for (int garden = 0; garden < n; garden++) {
boolean[] used = new boolean[5];
for (int neighbor : graph[garden]) {
used[answer[neighbor]] = true;
}
for (int flower = 1; flower <= 4; flower++) {
if (!used[flower]) {
answer[garden] = flower;
break;
}
}
}
return answer;
}
}
Ставь 👍 и забирай 📚 Базу знаний