收集树中金币

2603. 收集树中金币

给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [a_i, b_i] 表示树中节点 a_i 和 b_i 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。

一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：

收集距离当前节点距离为 2 以内的所有金币，或者
移动到树中一个相邻节点。

你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。

如果你多次经过一条边，每一次经过都会给答案加一。

示例 1：

输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：从节点 2 出发，收集节点 0 处的金币，移动到节点 3 ，收集节点 5 处的金币，然后移动回节点 2 。

示例 2：

输入：coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
输出：2
解释：从节点 0 出发，收集节点 4 和 3 处的金币，移动到节点 2 处，收集节点 7 处的金币，移动回节点 0 。

提示：

n == coins.length
1 <= n <= 3 * 10⁴
0 <= coins[i] <= 1
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
edges 表示一棵合法的树。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) { } };

cpp 解法, 执行用时: 600 ms, 内存消耗: 218.5 MB, 提交时间: 2023-09-21 09:51:38

class Solution {
public:
    int collectTheCoins(vector<int> &coins, vector<vector<int>> &edges) {
        int n = coins.size();
        vector<vector<int>> g(n);
        vector<int> deg(n);
        for (auto &e: edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x); // 建图
            deg[x]++;
            deg[y]++; // 统计每个节点的度数（邻居个数）
        }

        int left_edges = n - 1; // 剩余边数
        // 拓扑排序，去掉没有金币的子树
        vector<int> q;
        for (int i = 0; i < n; i++)
            if (deg[i] == 1 && coins[i] == 0) // 没有金币的叶子
                q.push_back(i);
        while (!q.empty()) {
            left_edges--; // 删除节点 x（到其父节点的边）
            int x = q.back(); q.pop_back();
            for (int y: g[x])
                if (--deg[y] == 1 && coins[y] == 0) // 没有金币的叶子
                    q.push_back(y);
        }

        // 再次拓扑排序
        for (int i = 0; i < n; i++)
            if (deg[i] == 1 && coins[i]) // 有金币的叶子（判断 coins[i] 是避免把没有金币的叶子也算进来）
                q.push_back(i);
        left_edges -= q.size(); // 删除所有叶子（到其父节点的边）
        for (int x: q) // 遍历所有叶子
            for (int y: g[x])
                if (--deg[y] == 1) // y 现在是叶子了
                    left_edges--; // 删除 y（到其父节点的边）
        return max(left_edges * 2, 0);
    }
};

javascript 解法, 执行用时: 416 ms, 内存消耗: 76.3 MB, 提交时间: 2023-09-21 09:51:21

/**
 * @param {number[]} coins
 * @param {number[][]} edges
 * @return {number}
 */
var collectTheCoins = function (coins, edges) {
    const n = coins.length;
    const g = Array(n).fill(null).map(() => []);
    for (const [x, y] of edges) {
        g[x].push(y);
        g[y].push(x); // 建图
    }
    const deg = g.map((neighbors) => neighbors.length); // 每个节点的度数（邻居个数）

    let leftEdges = n - 1; // 剩余边数
    // 拓扑排序，去掉没有金币的子树
    const q = [];
    for (let i = 0; i < n; i++) {
        if (deg[i] === 1 && coins[i] === 0) { // 没有金币的叶子
            q.push(i);
        }
    }
    while (q.length) {
        leftEdges--; // 删除节点到其父节点的边
        for (const x of g[q.pop()]) {
            if (--deg[x] === 1 && coins[x] === 0) { // 没有金币的叶子
                q.push(x);
            }
        }
    }

    // 再次拓扑排序
    for (let i = 0; i < n; i++) {
        if (deg[i] === 1 && coins[i]) { // 有金币的叶子（判断 coins[i] 是避免把没有金币的叶子也算进来）
            q.push(i);
        }
    }
    leftEdges -= q.length; // 删除所有叶子（到其父节点的边）
    for (const x of q) { // 遍历所有叶子
        for (const y of g[x]) {
            if (--deg[y] === 1) { // y 现在是叶子了
                leftEdges--; // 删除 y（到其父节点的边）
            }
        }
    }
    return Math.max(leftEdges * 2, 0);
};

rust 解法, 执行用时: 60 ms, 内存消耗: 6.5 MB, 提交时间: 2023-09-21 09:51:07

impl Solution {
    pub fn collect_the_coins(coins: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
        let n = coins.len();
        let mut g = vec![vec![]; n];
        let mut deg = vec![0; n];
        for e in &edges {
            let x = e[0] as usize;
            let y = e[1] as usize;
            g[x].push(y);
            g[y].push(x); // 建图
            deg[x] += 1;
            deg[y] += 1; // 统计每个节点的度数（邻居个数）
        }

        let mut left_edges = n as i32 - 1; // 剩余边数
        // 拓扑排序，去掉没有金币的子树
        let mut q = Vec::new();
        for i in 0..n {
            if deg[i] == 1 && coins[i] == 0 { // 没有金币的叶子
                q.push(i);
            }
        }
        while !q.is_empty() {
            left_edges -= 1; // 删除节点到其父节点的边
            for &y in &g[q.pop().unwrap()] {
                deg[y] -= 1;
                if deg[y] == 1 && coins[y] == 0 { // 没有金币的叶子
                    q.push(y);
                }
            }
        }

        // 再次拓扑排序
        for i in 0..n {
            if deg[i] == 1 && coins[i] == 1 { // 有金币的叶子（判断 coins[i] 是避免把没有金币的叶子也算进来）
                q.push(i);
            }
        }
        left_edges -= q.len() as i32; // 删除所有叶子（到其父节点的边）
        for &x in &q { // 遍历所有叶子
            for &y in &g[x] {
                deg[y] -= 1;
                if deg[y] == 1 { // y 现在是叶子了
                    left_edges -= 1; // 删除 y（到其父节点的边）
                }
            }
        }
        0.max(left_edges * 2)
    }
}

php 解法, 执行用时: 2484 ms, 内存消耗: 60.1 MB, 提交时间: 2023-09-21 09:50:31

class Solution {

    /**
     * @param Integer[] $coins
     * @param Integer[][] $edges
     * @return Integer
     */
    function collectTheCoins($coins, $edges) {
        $n = count($coins);
        $g = array_fill(0, $n, []);
        $deg = array_fill(0, $n, 0);
        $ans = 0;
        foreach ( $edges as $e ) {
            $x = $e[0];
            $y = $e[1];
            $g[$x][] = $y;
            $g[$y][] = $x; // 建图
            $deg[$x]++;
            $deg[$y]++;
        }
    
        // 用拓扑排序「剪枝」：去掉没有金币的子树
        $q = [];
        foreach ( $deg as $i => $d ) {
            if ( $d == 1 && $coins[$i] == 0 ) { // 无金币叶子
                $q[] = $i;
            }
        }
        while ( !empty($q) ) {
            $x = array_shift($q);
            foreach ( $g[$x] as $y ) {
                $deg[$y]--;
                if ( $deg[$y] == 1 && $coins[$y] == 0 ) {
                    $q[] = $y;
                }
            }
        }
    
        // 再次拓扑排序
        foreach ( $deg as $i => $d ) {
            if ( $d == 1 && $coins[$i] == 1 ) { // 有金币叶子
                $q[] = $i;
            }
        }
        if ( count($q) <= 1 ) { // 至多一个有金币的叶子，直接收集
            return $ans;
        }
        $time = array_fill(0, $n, 0);
        while ( !empty($q) ) {
            $x = array_shift($q);
            foreach ( $g[$x] as $y ) {
                $deg[$y]--;
                if ( $deg[$y] == 1 ) {
                    $time[$y] = $time[$x] + 1; // 记录入队时间
                    $q[] = $y;
                }
            }
        }
    
        // 统计答案
        foreach ( $edges as $e ) {
            if ( $time[$e[0]] >= 2 && $time[$e[1]] >= 2 ) {
                $ans += 2;
            }
        }
        return $ans;
    }
}

golang 解法, 执行用时: 280 ms, 内存消耗: 12.3 MB, 提交时间: 2023-03-29 15:03:19

func collectTheCoins(coins []int, edges [][]int) (ans int) {
	n := len(coins)
	g := make([][]int, n)
	deg := make([]int, n)
	for _, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], y)
		g[y] = append(g[y], x) // 建图
		deg[x]++
		deg[y]++
	}

	// 用拓扑排序「剪枝」：去掉没有金币的子树
	q := make([]int, 0, n)
	for i, d := range deg {
		if d == 1 && coins[i] == 0 { // 无金币叶子
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		x := q[0]
		q = q[1:]
		for _, y := range g[x] {
			deg[y]--
			if deg[y] == 1 && coins[y] == 0 {
				q = append(q, y)
			}
		}
	}

	// 再次拓扑排序
	for i, d := range deg {
		if d == 1 && coins[i] == 1 { // 有金币叶子
			q = append(q, i)
		}
	}
	if len(q) <= 1 { // 至多一个有金币的叶子，直接收集
		return
	}
	time := make([]int, n)
	for len(q) > 0 {
		x := q[0]
		q = q[1:]
		for _, y := range g[x] {
			deg[y]--
			if deg[y] == 1 {
				time[y] = time[x] + 1 // 记录入队时间
				q = append(q, y)
			}
		}
	}

	// 统计答案
	for _, e := range edges {
		if time[e[0]] >= 2 && time[e[1]] >= 2 {
			ans += 2
		}
	}
	return
}

java 解法, 执行用时: 38 ms, 内存消耗: 61.9 MB, 提交时间: 2023-03-29 15:03:02

class Solution {
    public int collectTheCoins(int[] coins, int[][] edges) {
        int n = coins.length;
        List<Integer> g[] = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        var deg = new int[n];
        for (var e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x); // 建图
            ++deg[x];
            ++deg[y];
        }

        // 用拓扑排序「剪枝」：去掉没有金币的子树
        var q = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i)
            if (deg[i] == 1 && coins[i] == 0) // 无金币叶子
                q.add(i);
        while (!q.isEmpty()) {
            int x = q.peek();
            q.pop();
            for (int y : g[x])
                if (--deg[y] == 1 && coins[y] == 0)
                    q.add(y);
        }

        // 再次拓扑排序
        for (int i = 0; i < n; ++i)
            if (deg[i] == 1 && coins[i] == 1) // 有金币叶子
                q.add(i);
        if (q.size() <= 1) return 0; // 至多一个有金币的叶子，直接收集
        var time = new int[n];
        while (!q.isEmpty()) {
            int x = q.peek();
            q.pop();
            for (int y : g[x])
                if (--deg[y] == 1) {
                    time[y] = time[x] + 1; // 记录入队时间
                    q.add(y);
                }
        }

        // 统计答案
        int ans = 0;
        for (var e : edges)
            if (time[e[0]] >= 2 && time[e[1]] >= 2)
                ans += 2;
        return ans;
    }
}

python3 解法, 执行用时: 360 ms, 内存消耗: 28.1 MB, 提交时间: 2023-03-29 15:02:50

# 拓扑排序 + 记录入队时间
class Solution:
    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
        n = len(coins)
        g = [[] for _ in range(n)]
        deg = [0] * n
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)  # 建图
            deg[x] += 1
            deg[y] += 1

        # 用拓扑排序「剪枝」：去掉没有金币的子树
        q = deque()
        for i, (d, c) in enumerate(zip(deg, coins)):
            if d == 1 and c == 0:  # 无金币叶子
                q.append(i)
        while q:
            for y in g[q.popleft()]:
                deg[y] -= 1
                if deg[y] == 1 and coins[y] == 0:
                    q.append(y)

        # 再次拓扑排序
        for i, (d, c) in enumerate(zip(deg, coins)):
            if d == 1 and c:  # 有金币叶子
                q.append(i)
        if len(q) <= 1:  # 至多一个有金币的叶子，直接收集
            return 0
        time = [0] * n
        while q:
            x = q.popleft()
            for y in g[x]:
                deg[y] -= 1
                if deg[y] == 1:
                    time[y] = time[x] + 1  # 记录入队时间
                    q.append(y)

        # 统计答案
        return sum(time[x] >= 2 and time[y] >= 2 for x, y in edges) * 2

上一题

下一题

详情