1042. Flower Planting With No Adjacent

LeetCode medium оригинал: C# #array #csharp #graph #leetcode #medium

LeetCode Static

У вас есть 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]

C# решение

сопоставлено/оригинал

public class Solution {
    public int[] GardenNoAdj(int n, int[][] paths) {
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        foreach (var path in 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++) {
            bool[] used = new bool[5];
            foreach (int neighbor in graph[garden]) {
                used[answer[neighbor]] = true;
            }
            for (int flower = 1; flower <= 4; flower++) {
                if (!used[flower]) {
                    answer[garden] = flower;
                    break;
                }
            }
        }
        
        return answer;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& GardenNoAdj(int n, int[][] paths) {
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        foreach (var path in paths) {
            graph[path[0] - 1].push_back(path[1] - 1);
            graph[path[1] - 1].push_back(path[0] - 1);
        }
        
        vector<int>& answer = new int[n];
        for (int garden = 0; garden < n; garden++) {
            bool[] used = new bool[5];
            foreach (int neighbor in graph[garden]) {
                used[answer[neighbor]] = true;
            }
            for (int flower = 1; flower <= 4; flower++) {
                if (!used[flower]) {
                    answer[garden] = flower;
                    break;
                }
            }
        }
        
        return answer;
    }
}

Java решение

сопоставлено/оригинал

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;
    }
}

JavaScript решение

сопоставлено/оригинал

var gardenNoAdj = function(n, paths) {
    const graph = Array.from({ length: n }, () => []);
    for (const [x, y] of paths) {
        graph[x - 1].push(y - 1);
        graph[y - 1].push(x - 1);
    }
    
    const answer = Array(n).fill(0);
    for (let garden = 0; garden < n; garden++) {
        const used = new Set(graph[garden].map(neighbor => answer[neighbor]));
        for (let flower = 1; flower <= 4; flower++) {
            if (!used.has(flower)) {
                answer[garden] = flower;
                break;
            }
        }
    }
    
    return answer;
};

Python решение

сопоставлено/оригинал

def gardenNoAdj(n, paths):
    graph = [[] for _ in range(n)]
    for x, y in paths:
        graph[x - 1].append(y - 1)
        graph[y - 1].append(x - 1)
    
    answer = [0] * n
    for garden in range(n):
        used = {answer[neighbor] for neighbor in graph[garden]}
        for flower in range(1, 5):
            if flower not in used:
                answer[garden] = flower
                break
    
    return answer

Algorithm

Построение графа:

Создайте граф из садов и путей между ними.

Присваивание цветов:

Для каждого сада выберите тип цветка, который не используется соседними садами.

Мы будем проходить по каждому саду и выбирать тип цветка, который не совпадает с типами цветов в соседних садах. Поскольку у каждого сада не более трех соседей, всегда будет возможность выбрать тип цветка из 4 возможных типов.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.