1519. Number of Nodes in the Sub-Tree With the Same Label

LeetCode medium оригинал: C# #array #csharp #graph #hash-table #leetcode #linked-list #medium #string #tree

LeetCode Static

Вам дано дерево (т.е. связный неориентированный граф без циклов), состоящее из n узлов, пронумерованных от 0 до n - 1, и ровно n - 1 ребра. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая является строчной буквой, указанной в строке labels (т.е. узел с номером i имеет метку labels[i]).

Массив edges дан в форме edges[i] = [ai, bi], что означает, что существует ребро между узлами ai и bi в дереве.

Верните массив размера n, где ans[i] — это количество узлов в поддереве узла i, которые имеют ту же метку, что и узел i.

Поддерево дерева T — это дерево, состоящее из узла в T и всех его дочерних узлов.

Пример:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"

Output: [2,1,1,1,1,1,1]

Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.

Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

C# решение

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

public class Solution {
    private int[] Dfs(int node, int parent, Dictionary<int, List<int>> adj, char[] labels, int[] ans) {
        int[] nodeCounts = new int[26];
        nodeCounts[labels[node] - 'a'] = 1;
        if (!adj.ContainsKey(node))
            return nodeCounts;
        foreach (int child in adj[node]) {
            if (child == parent) {
                continue;
            }
            int[] childCounts = Dfs(child, node, adj, labels, ans);
            for (int i = 0; i < 26; i++) {
                nodeCounts[i] += childCounts[i];
            }
        }
        ans[node] = nodeCounts[labels[node] - 'a'];
        return nodeCounts;
    }
    public int[] CountSubTrees(int n, int[][] edges, string labels) {
        var adj = new Dictionary<int, List<int>>();
        foreach (var edge in edges) {
            if (!adj.ContainsKey(edge[0])) {
                adj[edge[0]] = new List<int>();
            }
            if (!adj.ContainsKey(edge[1])) {
                adj[edge[1]] = new List<int>();
            }
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }
        var ans = new int[n];
        Dfs(0, -1, adj, labels.ToCharArray(), ans);
        return ans;
    }
}

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:
    private vector<int>& Dfs(int node, int parent, unordered_map<int, List<int>> adj, char[] labels, vector<int>& ans) {
        vector<int>& nodeCounts = new int[26];
        nodeCounts[labels[node] - 'a'] = 1;
        if (!adj.count(node))
            return nodeCounts;
        foreach (int child in adj[node]) {
            if (child == parent) {
                continue;
            }
            vector<int>& childCounts = Dfs(child, node, adj, labels, ans);
            for (int i = 0; i < 26; i++) {
                nodeCounts[i] += childCounts[i];
            }
        }
        ans[node] = nodeCounts[labels[node] - 'a'];
        return nodeCounts;
    }
    public vector<int>& CountSubTrees(int n, int[][] edges, string labels) {
        var adj = new unordered_map<int, List<int>>();
        foreach (var edge in edges) {
            if (!adj.count(edge[0])) {
                adj[edge[0]] = new List<int>();
            }
            if (!adj.count(edge[1])) {
                adj[edge[1]] = new List<int>();
            }
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        var ans = new int[n];
        Dfs(0, -1, adj, labels.ToCharArray(), ans);
        return ans;
    }
}

Java решение

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

class Solution {
    public int[] dfs(int node, int parent, Map<Integer, List<Integer>> adj, char[] labels, int[] ans) {
        int[] nodeCounts = new int[26];
        nodeCounts[labels[node] - 'a'] = 1;

        if (!adj.containsKey(node))
            return nodeCounts;

        for (int child : adj.get(node)) {
            if (child == parent) {
                continue;
            }
            int[] childCounts = dfs(child, node, adj, labels, ans);
            for (int i = 0; i < 26; i++) {
                nodeCounts[i] += childCounts[i];
            }
        }

        ans[node] = nodeCounts[labels[node] - 'a'];
        return nodeCounts;
    }

    public int[] countSubTrees(int n, int[][] edges, String labels) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1];
            adj.computeIfAbsent(a, value -> new ArrayList<>()).add(b);
            adj.computeIfAbsent(b, value -> new ArrayList<>()).add(a);
        }

        int[] ans = new int[n];
        char[] label = labels.toCharArray();
        dfs(0, -1, adj, label, ans);
        return ans;
    }
}

JavaScript решение

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

var dfs = function(node, parent, adj, labels, ans) {
    const nodeCounts = new Array(26).fill(0);
    nodeCounts[labels.charCodeAt(node) - 97] = 1;

    if (!adj.has(node)) return nodeCounts;

    for (const child of adj.get(node)) {
        if (child === parent) continue;
        const childCounts = dfs(child, node, adj, labels, ans);
        for (let i = 0; i < 26; i++) {
            nodeCounts[i] += childCounts[i];
        }
    }

    ans[node] = nodeCounts[labels.charCodeAt(node) - 97];
    return nodeCounts;
};

var countSubTrees = function(n, edges, labels) {
    const adj = new Map();
    for (const [a, b] of edges) {
        if (!adj.has(a)) adj.set(a, []);
        if (!adj.has(b)) adj.set(b, []);
        adj.get(a).push(b);
        adj.get(b).push(a);
    }

    const ans = new Array(n).fill(0);
    dfs(0, -1, adj, labels, ans);
    return ans;
};

Python решение

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

class Solution:
    def dfs(self, node, parent, adj, labels, ans):
        nodeCounts = [0] * 26
        nodeCounts[ord(labels[node]) - ord('a')] = 1

        for child in adj[node]:
            if child == parent:
                continue
            childCounts = self.dfs(child, node, adj, labels, ans)
            for i in range(26):
                nodeCounts[i] += childCounts[i]

        ans[node] = nodeCounts[ord(labels[node]) - ord('a')]
        return nodeCounts

    def countSubTrees(self, n, edges, labels):
        from collections import defaultdict

        adj = defaultdict(list)
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)

        ans = [0] * n
        self.dfs(0, -1, adj, labels, ans)
        return ans

Go решение

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

func dfs(node, parent int, adj map[int][]int, labels string, ans []int) []int {
    nodeCounts := make([]int, 26)
    nodeCounts[labels[node]-'a'] = 1

    for _, child := range adj[node] {
        if child == parent {
            continue
        }
        childCounts := dfs(child, node, adj, labels, ans)
        for i := 0; i < 26; i++ {
            nodeCounts[i] += childCounts[i]
        }
    }

    ans[node] = nodeCounts[labels[node]-'a']
    return nodeCounts
}

func countSubTrees(n int, edges [][]int, labels string) []int {
    adj := make(map[int][]int)
    for _, edge := range edges {
        adj[edge[0]] = append(adj[edge[0]], edge[1])
        adj[edge[1]] = append(adj[edge[1]], edge[0])
    }

    ans := make([]int, n)
    dfs(0, -1, adj, labels, ans)
    return ans
}

Algorithm

1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X.

2⃣Инициализируйте массив ans, хранящий ответ для каждого узла, и заполните его нулями.

3⃣Начните обход в глубину (DFS).

😎

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

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

Все вакансии

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