Leetcode每日一题：2872. 可以被 K 整除连通块的最大数目

思路

虽然题目描述中提到的是树，但实际上它是一个无环图。对于这类问题，通常考虑使用深度优先搜索（DFS）来解决。关键的问题在于如何进行搜索。我们可以考虑两种搜索方式：

按顺序删除边，计算剩下节点值之权和，如果能整除K就继续;
从任意一个节点进入，统计总权和，根据和的情况，如果不能整除K继续遍历，如果能整除K则尝试删除边。

然而，这两种方法在实际应用中都存在一定的难度。第一种方法每次都要计算节点值之和，容易导致超时。第二种方法在统计总权和时还需要考虑删除边的情况，比如除了已遍历的点还有两个点，删除某条边时要统计与之相连的分支，反之亦然，这并不是简单地按照遍历到的节点顺序就能完成的。

在尝试第二种方案时，我以sum作为DFS的第二个参数，但在实践过程中发现，可以将删除边与统计过程调换，这样就能在遍历的同时完成节点之权和的统计工作。

代码

private List<Integer> graph;
private int k;
private int ans;
private int values;
public int maxKDivisibleComponents(int n, int edges, int values, int k) {
    graph = new ArrayList[n];
    Arrays.setAll(graph, o -> new ArrayList<>());
    this.k = k;
    this.values = values;
    ans = 0;
    for (int edge : edges) {
        graph[edge[0]].add(edge[1]);
        graph[edge[1]].add(edge[0]);
    }
    dfs(0, -1);
    return ans;
}

private long dfs(int node, int parent) {
    List<Integer> list = graph[node];
    long sum = 0;
    if (list != null) {
        for (int v : list) {
            if (v == parent) continue;
            sum += dfs(v, node);
        }
    }
    sum += values[node];
    if (sum % k == 0) {
        ans++;
    }
    return sum;
}

优化思路

优化思路相对简单，主要是通过添加父节点参数来避免每次对列表进行增删操作，从而减少了时间复杂度。此外，直接声明长度为n的列表数组替代HashMap可以提高效率。

优化后的代码

private List<Integer> graph;
private int k;
private int ans;
private int values;
public int maxKDivisibleComponents(int n, int edges, int values, int k) {
    graph = new ArrayList[n];
    Arrays.setAll(graph, o -> new ArrayList<>());
    this.k = k;
    this.values = values;
    ans = 0;
    for (int edge : edges) {
        graph[edge[0]].add(edge[1]);
        graph[edge[1]].add(edge[0]);
    }
    dfs(0, -1);
    return ans;
}

private long dfs(int node, int parent) {
    List<Integer> list = graph[node];
    long sum = 0;
    if (list != null) {
        for (int v : list) {
            if (v == parent) continue;
            sum += dfs(v, node);
        }
    }
    sum += values[node];
    if (sum % k == 0) {
        ans++;
    }
    return sum;
}

通过这些优化，我们可以有效地提高算法的执行效率，更好地解决问题。

Leetcode每日一题：2872. 可以被 K 整除连通块的最大数目

评论已关闭