class Solution {
public:
int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
}
};
1298. 你能从盒子里获得的最大糖果数
给你 n 个盒子，每个盒子的格式为 [status, candies, keys, containedBoxes] ，其中：
status[i]：整数，如果 box[i] 是开的，那么是 1 ，否则是 0 。candies[i]: 整数，表示 box[i] 中糖果的数目。keys[i]：数组，表示你打开 box[i] 后，可以得到一些盒子的钥匙，每个元素分别为该钥匙对应盒子的下标。containedBoxes[i]：整数，表示放在 box[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 的钥匙所以盒子 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 个。
示例 3：
输入：status = [1,1,1], candies = [100,1,100], keys = [[],[0,2],[]], containedBoxes = [[],[],[]], initialBoxes = [1] 输出：1
示例 4：
输入：status = [1], candies = [100], keys = [[]], containedBoxes = [[]], initialBoxes = [] 输出：0
示例 5：
输入：status = [1,1,1], candies = [2,3,2], keys = [[],[],[]], containedBoxes = [[],[],[]], initialBoxes = [2,1,0] 输出：7
提示：
1 <= status.length <= 1000status.length == candies.length == keys.length == containedBoxes.length == nstatus[i] 要么是 0 要么是 1 。1 <= candies[i] <= 10000 <= keys[i].length <= status.length0 <= keys[i][j] < status.lengthkeys[i] 中的值都是互不相同的。0 <= containedBoxes[i].length <= status.length0 <= containedBoxes[i][j] < status.lengthcontainedBoxes[i] 中的值都是互不相同的。0 <= initialBoxes.length <= status.length0 <= initialBoxes[i] < status.length原站题解
java 解法, 执行用时: 5 ms, 内存消耗: 52.8 MB, 提交时间: 2023-09-21 10:57:20
class Solution {
public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
int n = status.length;
boolean[] can_open = new boolean[n], has_box = new boolean[n], used = new boolean[n];
for(int i = 0; i < n; i++){
can_open[i] = (status[i] == 1);
}
Deque<Integer> q = new ArrayDeque<>();
for(int i : initialBoxes){
has_box[i] = true;
if(can_open[i]){
used[i] = true;
q.add(i);
}
}
int ans = 0;
while(!q.isEmpty()){
int i = q.poll();
ans += candies[i];
for(int k : keys[i]){
can_open[k] = true;
if(has_box[k] && !used[k]){
used[k] = true;
q.add(k);
}
}
for(int k : containedBoxes[i]){
has_box[k] = true;
if(can_open[k] && !used[k]){
used[k] = true;
q.add(k);
}
}
}
return ans;
}
}
golang 解法, 执行用时: 100 ms, 内存消耗: 7.8 MB, 提交时间: 2023-09-21 10:57:05
// 获得糖果的条件：获得盒子 & (盒子开着 || 具有钥匙)
func maxCandies(status []int, candies []int, keys [][]int, containedBoxes [][]int, initialBoxes []int) int {
n := len(status)
hasBox := make([]bool, n) // owned box
hasKey := make([]bool, n) // owned keys
vis := make([]bool, n) // visited
que := []int{}
ans := 0 // candies taken
for _, box := range initialBoxes {
hasBox[box] = true
if status[box] == 1 {
que = append(que, box)
vis[box] = true
}
}
// BFS
for len(que) > 0 {
box := que[0]
que = que[1:]
ans += candies[box]
// 拿到新钥匙，入队
for _, key := range keys[box] {
hasKey[key] = true
if !vis[key] && hasBox[key] { // 可能存在重复的钥匙，用vis去重
que = append(que, key)
vis[key] = true
}
}
// 拿到新盒子，入队
for _, cBox := range containedBoxes[box] {
hasBox[cBox] = true
if hasKey[cBox] || status[cBox] == 1 {
que = append(que, cBox)
vis[cBox] = true
}
}
}
return ans
}
python3 解法, 执行用时: 108 ms, 内存消耗: 26.2 MB, 提交时间: 2023-09-21 10:56:45
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)
can_open = [status[i] == 1 for i in range(n)]
has_box, used = [False] * n, [False] * n
q = collections.deque()
ans = 0
for box in initialBoxes:
has_box[box] = True
if can_open[box]:
q.append(box)
used[box] = True
ans += candies[box]
while len(q) > 0:
big_box = q.popleft()
for key in keys[big_box]:
can_open[key] = True
if not used[key] and has_box[key]:
q.append(key)
used[key] = True
ans += candies[key]
for box in containedBoxes[big_box]:
has_box[box] = True
if not used[box] and can_open[box]:
q.append(box)
used[box] = True
ans += candies[box]
return ans
cpp 解法, 执行用时: 132 ms, 内存消耗: 39.2 MB, 提交时间: 2023-09-21 10:56:21
// bfs
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();
vector<bool> can_open(n), has_box(n), used(n);
for (int i = 0; i < n; ++i) {
can_open[i] = (status[i] == 1);
}
queue<int> q;
int ans = 0;
for (int box: initialBoxes) {
has_box[box] = true;
if (can_open[box]) {
q.push(box);
used[box] = true;
ans += candies[box];
}
}
while (!q.empty()) {
int big_box = q.front();
q.pop();
for (int key: keys[big_box]) {
can_open[key] = true;
if (!used[key] && has_box[key]) {
q.push(key);
used[key] = true;
ans += candies[key];
}
}
for (int box: containedBoxes[big_box]) {
has_box[box] = true;
if (!used[box] && can_open[box]) {
q.push(box);
used[box] = true;
ans += candies[box];
}
}
}
return ans;
}
};