algorithm - 水合节点

问题描述

最近我在一家公司进行了编码面试测试。这是我无法解决的问题之一。我自己尝试并采用了方法，但我不确定它是否正确，如果有的话，请帮助我纠正我的方法错误。

这是问题陈述：-

水合节点有一棵树有n个节点。这棵树植根于编号为 0 的节点。通常在计算机科学中，与自然界中存在的树木相比，这棵树的生长是颠倒的。苹果长在这棵树的节点上。这些苹果中有些水分不足，有些水分过多，有些则两者都没有。您知道，对于每一个水分过多的苹果，您将获得 overhydratedPenalty 美分，对于每一个水分不足的苹果，您将获得underwaterdPenalty 美分。现在，您想将水倒在树的一个节点上。当你在节点 v 上倒水时，v 的子树中的所有苹果，即 vitself 和 v 的所有后代，都将被水合，因此，每个几乎过度水合的水合苹果都变得过度水合。而且，整棵树上几乎没有水分且没有浇水的每个苹果都会水分不足。计算将水倒在树的一个节点上所能得到的最小总惩罚。

函数说明完成函数 minimumPouringWaterPenalty(vector parent, vector waterLevel, int overhydradPenalty, int underhydradPenalty)

minimumPouringWaterPenalty 具有以下参数： 1. 大小为 n 的整数数组 parent，其中 parenti 表示第 i 个节点的父节点。2. 一个大小为 n 的整数数组 waterLevel，其中 waterLevel 表示节点 i 上苹果中的水位。它是 -1、0 或 1，其中 -1 代表几乎水合不足，O 代表既不几乎不水合也不几乎过度水合，1 代表几乎过度水合。3. 一个整数，overhydradPenalty，表示对每个过水苹果的惩罚。4. 一个整数，水分不足的罚分，表示每个水分不足的苹果的罚分。

该函数必须返回通过将水倒在树的一个节点上可以获得的最小惩罚。

文字取自：https ://codeforces.com/blog/entry/86512

我的方法：

使用 parent[i] -> i ( g )制作图表
如果给定水，则执行 dfs 遍历以检查每个节点的惩罚。在此仅检查任何值是否为 1，然后增加该节点的过度水化的计数惩罚，并将每个节点的数组（h_penalty）存储在给定水的惩罚中。
这次再次遍历检查是否没有给水，那么脱水不足会受到什么惩罚。在这只是检查任何值是否为-1，然后增加该节点的欠水化惩罚计数并将每个节点的数组（u_penalty）存储在给水时的惩罚。
现在，如果给水和不给水，我对每个节点都有惩罚。然后我将遍历 h_penalty，并且对于每个节点，我将取 h_penalty[i] + (u_penalty[0]-u_penalty[i]) 的最小值。

这是我的方法代码：

from collections import defaultdict


def hyderatedtheNode(parent, waterLevel, overHyderatd, underHyderated):
    g = defaultdict(list)

    h_penalty = [0] * len(waterLevel)
    u_penalty = [0] * len(waterLevel)

    createGraph(parent, g)
    dfs(0, waterLevel, overHyderatd, underHyderated, 1, h_penalty, g)
    dfs(0, waterLevel, underHyderated, overHyderatd, - 1, u_penalty, g)
    # print(h_penalty)
    # print(u_penalty)
    # print(g)
    # print(list(enumerate(waterLevel)))
    ans = float('inf')
    p = u_penalty[0]
    for i, h in enumerate(h_penalty):
        ans = min(ans, h + (p - u_penalty[i]))
    print(ans)


def createGraph(parent, g):
    for i in range(1, len(parent)):
        g[parent[i]].append(i)


def dfs(src, waterLeve, oH, uH, apple, val, g):
    if not g.get(src, None):
        if waterLeve[src] == apple:
            val[src] = oH
            return oH
        return 0

    if g.get(src, None):
        penalty = 0
        if waterLeve[src] == apple:
            penalty = oH
        for t in g[src]:
            penalty += dfs(t, waterLeve, oH, uH, apple, val, g)
            # print(src, t, penalty)
    val[src] = penalty
    return penalty


hyderatedtheNode([-1, 0, 1], [1, 1, 1], 3, 5)  # 0
hyderatedtheNode([-1, 0, 0], [1, -1, -1], 10, 15)   # 10
hyderatedtheNode([-1, 0, 0, 1], [0, 0, 0, 0], 10, 15)  # 0 
hyderatedtheNode([-1, 0, 1, 0, 1, 2, 2, 2, 5, 5], [-1, -1, 0, -1, 0, 0, 1, 0, 0, 1], 2, 3)  # 4

请让我知道这种方法是否可行或需要其他任何东西？

标签： algorithmdata-structuresdepth-first-searchgreedy

通过给定的关系制作树（它是一个 K 节点树，其中 K 表示任何父节点的子节点）。
通过 DFS 计算子树中每个节点（其中每个节点 = self + children 值）的缺水、过水苹果的数量。
按根 DFS 值计算不浇水的惩罚。
如果水倒在每个节点上，则通过其 DFS 值计算惩罚并检查全局最小值。

public class Main {

    public static void main(String[] args) {
        System.out.println(hyderatedtheNode(new int[]{-1, 0, 1}, new int[]{-1, -1, -1}, 3, 5) == 0);
        System.out.println(hyderatedtheNode(new int[]{-1, 0, 0}, new int[]{1, -1, -1}, 10, 15) == 10);
        System.out.println(hyderatedtheNode(new int[]{-1, 0, 0, 1}, new int[]{0, 0, 0, 0}, 10, 15) == 0);
        System.out.println(hyderatedtheNode(new int[]{-1, 0, 1, 0, 1, 2, 2, 2, 5, 5}, new int[]{-1, -1, 0, -1, 0, 0, 1, 0, 0, 1}, 2, 3) == 4);


    }

    public static int hyderatedtheNode(int[] parent, int[] water, int oh, int uh) {
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < parent.length; i++) {
            map.putIfAbsent(parent[i], new ArrayList<Integer>());
            map.get(parent[i]).add(i);
        }
        int[][] waterLevel = new int[parent.length][2];
        for (int[] arr : waterLevel) {
            Arrays.fill(arr, -1);
        }
        dfs(0, waterLevel, water, map);

        int ifNoWater = waterLevel[0][0] * oh + waterLevel[0][1] * uh;
        int globalMin = ifNoWater;
        for (int i = 0; i < parent.length; i++) {
            int currMax = 0;
            currMax -= waterLevel[i][1] * uh;
            globalMin = Math.min(globalMin, (ifNoWater + currMax));
        }
        return globalMin;
    }

    private static int[] dfs(int node, int[][] waterLevel, int[] water, Map<Integer, List<Integer>> map) {
        int[] total = new int[2];
        total[0] = 0; // oh
        total[1] = 0; // uh
        if (water[node] > 0) {
            total[0] += 1;
        } else if (water[node] < 0) {
            total[1] += 1;
        }

        if (waterLevel[node][0] != -1) {
            return waterLevel[node];
        }
        if (map.get(node) != null) {
            for (int i : map.get(node)) {
                int[] temp = dfs(i, waterLevel, water, map);
                total[0] += temp[0];
                total[1] += temp[1];
            }
        }

        waterLevel[node] = total;
        return total;
    }
}

algorithm - 水合节点

问题描述

解决方案

推荐阅读