Hard

题目描述

你有 n 个盒子，标记为从 0 到 n - 1。给定四个数组：status、candies、keys 和 containedBoxes，其中：

  • status[i] 如果第 i 个盒子是打开的则为 1，如果是关闭的则为 0
  • candies[i] 是第 i 个盒子中的糖果数量
  • keys[i] 是打开第 i 个盒子后你可以打开的盒子标签列表
  • containedBoxes[i] 是你在第 i 个盒子内找到的盒子列表

给定一个整数数组 initialBoxes，包含你最初拥有的盒子标签。你可以取出任何打开的盒子中的所有糖果，可以使用其中的钥匙打开新盒子，也可以使用在其中找到的盒子。

按照上述规则返回你能获得的最大糖果数量。

示例 1：

输入：status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
输出：16
解释：你最初会得到盒子 0。你会在其中找到 7 个糖果和盒子 1、2。
盒子 1 是关闭的，你没有钥匙，所以你会打开盒子 2。你会在盒子 2 中找到 4 个糖果和盒子 1 的钥匙。
在盒子 1 中，你会找到 5 个糖果和盒子 3，但你找不到盒子 3 的钥匙，所以盒子 3 将保持关闭状态。
收集的糖果总数 = 7 + 4 + 5 = 16 个糖果。

示例 2：

输入：status = [1,0,0,0,0,0], candies = [1,1,1,1,1,1], keys = [[1,2,3,4,5],[],[],[],[],[]], containedBoxes = [[1,2,3,4,5],[],[],[],[],[]], initialBoxes = [0]
输出：6
解释：你最初有盒子 0。打开它你可以找到盒子 1,2,3,4,5 和它们的钥匙。
糖果总数将是 6。

约束条件：

  • n == status.length == candies.length == keys.length == containedBoxes.length
  • 1 <= n <= 1000
  • status[i] 是 0 或 1
  • 1 <= candies[i] <= 1000
  • 0 <= keys[i].length <= n
  • 0 <= keys[i][j] < n
  • keys[i] 的所有值都是唯一的
  • 0 <= containedBoxes[i].length <= n
  • 0 <= containedBoxes[i][j] < n
  • containedBoxes[i] 的所有值都是唯一的
  • 每个盒子最多包含在一个盒子中
  • 0 <= initialBoxes.length <= n
  • 0 <= initialBoxes[i] < n

解题思路

这道题是一个图遍历问题，可以用BFS（广度优先搜索）来解决。

核心思路：

  1. 我们需要模拟打开盒子的过程，每次打开一个盒子时，会获得糖果、钥匙和新的盒子
  2. 关键在于理解什么时候可以打开一个盒子：必须同时满足两个条件
    • 拥有这个盒子（从初始盒子或其他盒子中获得）
    • 这个盒子是开启状态，或者拥有这个盒子的钥匙

算法步骤：

  1. 维护三个集合：hasBox（拥有的盒子）、hasKey（拥有的钥匙）、opened（已打开的盒子）
  2. 使用队列进行BFS，初始时将所有可以立即打开的盒子加入队列
  3. 对于队列中的每个盒子：
    • 收集糖果
    • 获得新的钥匙，检查是否能打开之前无法打开的盒子
    • 获得新的盒子，检查是否能立即打开
  4. 重复直到队列为空

优化要点：

  • 避免重复处理同一个盒子
  • 当获得新钥匙时，需要检查是否能打开之前获得但无法打开的盒子

代码实现

class Solution {
public:
    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
        int n = status.size();
        unordered_set<int> hasBox, hasKey, opened;
        queue<int> q;
        
        // 初始化拥有的盒子
        for (int box : initialBoxes) {
            hasBox.insert(box);
        }
        
        // 将初始可以打开的盒子加入队列
        for (int box : initialBoxes) {
            if (status[box] == 1) {
                q.push(box);
                opened.insert(box);
            }
        }
        
        int totalCandies = 0;
        
        while (!q.empty()) {
            int box = q.front();
            q.pop();
            
            // 收集糖果
            totalCandies += candies[box];
            
            // 获得新钥匙
            for (int key : keys[box]) {
                hasKey.insert(key);
                // 如果有这个盒子且还没打开，现在可以打开了
                if (hasBox.count(key) && !opened.count(key)) {
                    q.push(key);
                    opened.insert(key);
                }
            }
            
            // 获得新盒子
            for (int newBox : containedBoxes[box]) {
                hasBox.insert(newBox);
                // 如果这个盒子可以打开且还没打开
                if (!opened.count(newBox) && (status[newBox] == 1 || hasKey.count(newBox))) {
                    q.push(newBox);
                    opened.insert(newBox);
                }
            }
        }
        
        return totalCandies;
    }
};

class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        n = len(status)
        has_box = set(initialBoxes)
        has_key = set()
        opened = set()
        queue = []
        
        # 将初始可以打开的盒子加入队列
        for box in initialBoxes:
            if status[box] == 1:
                queue.append(box)
                opened.add(box)
        
        total_candies = 0
        
        while queue:
            box = queue.pop(0)
            
            # 收集糖果
            total_candies += candies[box]
            
            # 获得新钥匙
            for key in keys[box]:
                has_key.add(key)
                # 如果有这个盒子且还没打开，现在可以打开了
                if key in has_box and key not in opened:
                    queue.append(key)
                    opened.add(key)
            
            # 获得新盒子
            for new_box in containedBoxes[box]:
                has_box.add(new_box)
                # 如果这个盒子可以打开且还没打开
                if new_box not in opened and (status[new_box] == 1 or new_box in has_key):
                    queue.append(new_box)
                    opened.add(new_box)
        
        return total_candies

public class Solution {
    public int MaxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        int n = status.Length;
        var hasBox = new HashSet<int>(initialBoxes);
        var hasKey = new HashSet<int>();
        var opened = new HashSet<int>();
        var queue = new Queue<int>();
        
        // 将初始可以打开的盒子加入队列
        foreach (int box in initialBoxes) {
            if (status[box] == 1) {
                queue.Enqueue(box);
                opened.Add(box);
            }
        }
        
        int totalCandies = 0;
        
        while (queue.Count > 0) {
            int box = queue.Dequeue();
            
            // 收集糖果
            totalCandies += candies[box];
            
            // 获得新钥匙
            foreach (int key in keys[box]) {
                hasKey.Add(key);
                // 如果有这个盒子且还没打开，现在可以打开了
                if (hasBox.Contains(key) && !opened.Contains(key)) {
                    queue.Enqueue(key);
                    opened.Add(key);
                }
            }
            
            // 获得新盒子
            foreach (int newBox in containedBoxes[box]) {
                hasBox.Add(newBox);
                // 如果这个盒子可以打开且还没打开
                if (!opened.Contains(newBox) && (status[newBox] == 1 || hasKey.Contains(newBox))) {
                    queue.Enqueue(newBox);
                    opened.Add(newBox);
                }
            }
        }
        
        return totalCandies;
    }
}

var maxCandies = function(status, candies, keys, containedBoxes, initialBoxes) {
    const n = status.length;
    const hasBox = new Set(initialBoxes);
    const hasKey = new Set();
    const opened = new Set();
    const queue = [];
    
    // 将初始可以打开的盒子加入队列
    for (const box of initialBoxes) {
        if (status[box]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n + E)，其中 n 是盒子数量，E 是所有 keys 和 containedBoxes 中元素的总数。每个盒子最多被访问一次。
空间复杂度O(n)，用于存储集合和队列，最坏情况下需要存储所有盒子的信息。