【每日力扣中医养生】力扣1298. 你能从盒子里获得的最大糖果数

1298. 你能从盒子里获得的最大糖果数

文章目录

• 【每日力扣&中医养生】力扣1298. 你能从盒子里获得的最大糖果数
• • 题目描述
  • 示例解析
  • • 示例 1
    • 示例 2
  • 算法思路
  • • 算法步骤
    • 代码实现
    • 复杂度分析
    • 总结

---

【每日力扣&中医养生】力扣1298. 你能从盒子里获得的最大糖果数

《黄帝内经》的阴阳应象大论篇第五，提到了“酸胜甘”，所以，如果你觉得吃的东西齁甜，可以吃喝点酸的东西来减缓齁甜的感觉。

题目描述

在这个问题中，你拥有一些盒子。每个盒子包含以下四种信息：

1. 状态 status[i]：一个整数，表示盒子 i 是否已经打开。如果是打开的，值为 1，否则为 0。
2. 糖果数 candies[i]：一个整数，表示盒子 i 中包含的糖果数量。
3. 钥匙 keys[i]：一个数组，表示打开盒子 i 后，可以获得的一些盒子的钥匙。每个元素表示对应盒子的下标。
4. 内含盒子 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，获得 4 个糖果和盒子 1 的钥匙。
• 打开盒子 1，获得 5 个糖果和盒子 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。打开盒子 0 后，你可以获得所有其他盒子（1, 2, 3, 4, 5）及其对应的钥匙，并且打开它们，最终获取所有糖果。

总结：最终你获得的糖果总数为 6。

算法思路

解决这个问题的关键在于模拟打开盒子的过程，这个过程可以通过广度优先搜索（BFS）来实现。

算法步骤

1. 初始化：

   • 使用一个队列 queue 存放当前可以打开的盒子。
   • 使用一个集合 opened 存储已经打开的盒子，避免重复打开。
   • 使用一个集合boxes_owned记录拥有的盒子，
   • 使用集合 boxes_can_open 存储可以打开的盒子，记录哪一些盒子拥有对应钥匙或者在status中为1。

2. 处理初始盒子：

   • 将所有可以打开的初始盒子添加到队列中。

3. BFS遍历：

   • 遍历队列中的盒子，依次处理：
     1. 获取盒子中的钥匙，查看是否拥有对应的盒子可以打开，如果可以打开，则打开并入队。
     2. 获取盒子中包含的其他盒子，查看是否可以打开，如果可以打开，则打开并入队。

4. 循环结束：

   • 继续上述过程，直到队列为空，即所有能够打开的盒子都已处理完毕。

代码实现

以下是该算法的完整代码实现：

from collections import dequetrue = True
false = Falseclass Solution:def maxCandies(self, status, candies, keys, cboxes, initialBoxes):# 初始化队列与集合queue = deque()opened = set()boxes_owned = set()boxes_can_open = set(i for i, e in enumerate(status) if e == 1)total_candies = 0for box in initialBoxes:boxes_owned.add(box)if status[box] == 1:queue.append(box)opened.add(box)total_candies += candies[box]while queue:box = queue.popleft()  # 取出已经打开的盒子# 将获得的钥匙加入“可打开”集合，并检查是否有对应的未开启的盒子for key in keys[box]:boxes_can_open.add(key)if key not in opened and key in boxes_owned:queue.append(key)opened.add(key)  # 记录已打开盒子total_candies += candies[key]  # 获取糖果# 获取该盒子内部的其它盒子for cbox in cboxes[box]:boxes_owned.add(cbox)# 检查是否可以打开if  (cbox not in openedandcbox in boxes_can_open):queue.append(cbox)opened.add(cbox)  # 记录已打开盒子total_candies += candies[cbox]  # 获取糖果return total_candies

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是盒子的数量。每个盒子最多处理一次，所有操作都是线性复杂度的。
• 空间复杂度：$O(n)$，用于存储队列和集合的内存。

总结

在这个问题中，通过使用广度优先搜索（BFS）算法，我们能够模拟打开盒子和获取糖果的过程。整个过程的关键在于理解BFS算法中的入队操作，正确管理盒子的状态、钥匙以及盒子间的相互包含关系。
如果在这些多重因素限制下依然能运用BFS算法解决问题，那么你一定已经很深入地理解了BFS算法的核心逻辑。