wordpress文件下载站,网站建设与规划结论,wordpress h5,html简单网页代码图片1298. 你能从盒子里获得的最大糖果数 文章目录 【每日力扣中医养生】力扣1298. 你能从盒子里获得的最大糖果数题目描述示例解析示例 1示例 2 算法思路算法步骤代码实现复杂度分析总结 【每日力扣中医养生】力扣1298. 你能从盒子里获得的最大糖果数
《黄帝内经》的阴… 1298. 你能从盒子里获得的最大糖果数 文章目录 【每日力扣中医养生】力扣1298. 你能从盒子里获得的最大糖果数题目描述示例解析示例 1示例 2 算法思路算法步骤代码实现复杂度分析总结 【每日力扣中医养生】力扣1298. 你能从盒子里获得的最大糖果数
《黄帝内经》的阴阳应象大论篇第五提到了“酸胜甘”所以如果你觉得吃的东西齁甜可以吃喝点酸的东西来减缓齁甜的感觉。
题目描述
在这个问题中你拥有一些盒子。每个盒子包含以下四种信息
状态 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获得 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来实现。
算法步骤 初始化 使用一个队列 queue 存放当前可以打开的盒子。使用一个集合 opened 存储已经打开的盒子避免重复打开。使用一个集合boxes_owned记录拥有的盒子使用集合 boxes_can_open 存储可以打开的盒子记录哪一些盒子拥有对应钥匙或者在status中为1。 处理初始盒子 将所有可以打开的初始盒子添加到队列中。 BFS遍历 遍历队列中的盒子依次处理 获取盒子中的钥匙查看是否拥有对应的盒子可以打开如果可以打开则打开并入队。获取盒子中包含的其他盒子查看是否可以打开如果可以打开则打开并入队。 循环结束 继续上述过程直到队列为空即所有能够打开的盒子都已处理完毕。
代码实现
以下是该算法的完整代码实现
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 ) O(n) O(n)其中 n n n 是盒子的数量。每个盒子最多处理一次所有操作都是线性复杂度的。空间复杂度 O ( n ) O(n) O(n)用于存储队列和集合的内存。
总结
在这个问题中通过使用广度优先搜索BFS算法我们能够模拟打开盒子和获取糖果的过程。整个过程的关键在于理解BFS算法中的入队操作正确管理盒子的状态、钥匙以及盒子间的相互包含关系。 如果在这些多重因素限制下依然能运用BFS算法解决问题那么你一定已经很深入地理解了BFS算法的核心逻辑。
