【Day 52 】2023-04-06 - 1298. 你能从盒子里获得的最大糖果数

[azl397985856]

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

入选理由

暂无

题目地址

https://leetcode.cn/problems/maximum-candies-you-can-get-from-boxes/

前置知识

• BFS

  题目描述

给你 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 <= 1000 status.length == candies.length == keys.length == containedBoxes.length == n status[i] 要么是 0 要么是 1 。 1 <= candies[i] <= 1000 0 <= keys[i].length <= status.length 0 <= keys[i][j] < status.length keys[i] 中的值都是互不相同的。 0 <= containedBoxes[i].length <= status.length 0 <= containedBoxes[i][j] < status.length containedBoxes[i] 中的值都是互不相同的。 每个盒子最多被一个盒子包含。 0 <= initialBoxes.length <= status.length 0 <= initialBoxes[i] < status.length

[JiangyanLiNEU]

class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        res = 0
        opened_box, closed_box, have_key, candy_taken  = [], set(), set(), set()

        for box in initialBoxes:
            if status[box] == 1: 
                opened_box.append(box)
                for key in keys[box]:
                    have_key.add(key)
                for b in containedBoxes[box]:
                    if status[b] == 1: 
                        opened_box.append(b)
                    elif b in have_key:
                        opened_box.append(b)
                        have_key.remove(b)
                    else:
                        closed_box.add(b)
            else: 
                closed_box.add(box)
        while opened_box:
            box = opened_box.pop()
            if box not in candy_taken:
                res += candies[box]
                candy_taken.add(box)
                for key in keys[box]:
                    if key in closed_box:
                        opened_box.append(key)
                        closed_box.remove(key)
                    else:
                        have_key.add(key)
                for b in containedBoxes[box]:
                    if status[b] == 1:
                        opened_box.append(b)
                    elif b in have_key:
                        have_key.remove(b)
                        opened_box.append(b)
                    else:
                        closed_box.add(b)
        return res

[JasonQiu]

• BFS

  class Solution:
  def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
      queue = []
      for b in initialBoxes:
          if status[b]:
              queue.append(b)
          else:
              status[b] = -1
      result = 0
      while queue:
          box_current = queue.pop(0)
          result += candies[box_current]
          for box in containedBoxes[box_current]:
              if status[box] == 1:
                  queue.append(box)
              else:
                  status[box] = -1
          for key in keys[box_current]:
              if status[key] == -1:
                  status[key] = 0
                  queue.append(key)
              else:
                  status[key] = 1
      return result

  Time: O(n) Space: O(n)

[LIMBO42]

class Solution {
public:
    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
        // BFS
        queue<int> que;
        int n = status.size();
        vector<bool> used(n, false);

        vector<bool> canopen(n, false);
        for(int i = 0; i < n; ++i) {
            if(status[i] == 1) {
                canopen[i] = true;
            }
        }

        vector<int> boxs(n, false);

        for(int initial : initialBoxes) {
            if(canopen[initial]) {
                used[initial] = true;
                que.push(initial);
            } else {
                boxs[initial] = true;
            }
            // que.push(initial);
        }

        int ans = 0;
        while(!que.empty()) {
            int index = que.front();
            que.pop();
            for(int i : keys[index]) {
                canopen[i] = true;
            }
            ans += candies[index];
            for(int i : containedBoxes[index]) {
                if(canopen[i] && !used[i]) {
                    used[i] = true;
                    que.push(i);
                }
                if(!canopen[i] && !used[i]) {
                    // boxs.push_back(i);
                    boxs[i] = true;
                }
            }
            for(int i = 0; i < n; ++i) {
                if(boxs[i] == true && canopen[i]) {
                    used[i] = true;
                    que.push(i);
                    boxs[i] = false;
                }
            }
        }
        return ans;
    }
};

[jmaStella]

思路

BFS 需要注意的是，你需要既能access到box又有钥匙，所以新加一个openable array to keep track of openable boxes

代码

    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        int maxCandies = 0;
        Queue<Integer> queue = new LinkedList<>();
        int[] openable = new int[status.length];
        for(int box : initialBoxes){
            if(status[box] == 1){
                //System.out.println(box);
                queue.offer(box);
            }else{
                openable[box] =1;
            }
        }
        int result = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size; i++){
                int box = queue.poll();
                result+= candies[box];
                status[box] = -1;

                for(int child : keys[box]){
                    if(status[child] == 0){
                        //System.out.println(box);
                        status[child] = 1;
                    }
                }
                for(int child : containedBoxes[box]){
                        openable[child] =1;
                }
                for(int j = 0; j<openable.length; j++){
                    if(openable[j] == 1 && status[j] ==1){
                        queue.offer(j);
                        openable[j] = 0;
                    }
                }

            }
        }
        return result;
    }

复杂度

O(N) N = number of boxes O(N)

[NorthSeacoder]

const maxCandies = (boxStatus, candies, keys, containedBoxes, initialBoxes) => {
  const needKeys = new Set();
  let maxCandiesCount = 0;
  let queue = [...initialBoxes];

  while (queue.length) {
    const currentBoxIndex = queue.shift();

    // 如果盒子已经打开或者有钥匙可用，就看看里面有没有糖果，并加入到总数中
    if (boxStatus[currentBoxIndex]) {
      maxCandiesCount += candies[currentBoxIndex];

      // 把盒子里的还没打开过的盒子加入队列中
      queue.push(...containedBoxes[currentBoxIndex]);

      // 把盒子里的钥匙标记为可用，并加入队列中
      for (const keyIndex of keys[currentBoxIndex]) {
        boxStatus[keyIndex] = 1;
        if (needKeys.has(keyIndex)) {
          queue.push(keyIndex);
          needKeys.delete(keyIndex);
        }
      }
    }
    // 如果盒子当前是锁着的，增加到等待打开列表中
    else {
      needKeys.add(currentBoxIndex);
    }
  }

  return maxCandiesCount;
};

• TC:O(n)
• SC:O(n)

[wangzh0114]

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;
    }
};

• TC:O(N)
• SC:O(N)

[kofzhang]

思路

广度优先搜索

复杂度

时间复杂度：O(n) 空间复杂度：O(n)

代码

class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        ownboxes = set()
        ownkeys = set()
        kaiguo = set()
        res = 0
        q = deque()
        for i in initialBoxes:
            if status[i]:
                q.append(i)
                kaiguo.add(i)
            else:
                ownboxes.add(i)        
        while q:
            curbox = q.popleft() 
            res += candies[curbox]
            ownkeys.discard(curbox)
            ownboxes.discard(curbox)

            for key in keys[curbox]:
                if key in ownboxes:
                    if key not in kaiguo:
                        q.append(key)
                        kaiguo.add(key)
                else:
                    ownkeys.add(key)
            for box in containedBoxes[curbox]:
                if status[box]==1 or (box in ownkeys):
                    if box not in kaiguo:
                        q.append(box)
                        kaiguo.add(box)
                else:
                    ownboxes.add(box)
        return res

[GuitarYs]

class Solution: def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int: ownboxes = set() ownkeys = set() kaiguo = set() res = 0 q = deque() for i in initialBoxes: if status[i]: q.append(i) kaiguo.add(i) else: ownboxes.add(i)
while q: curbox = q.popleft() res += candies[curbox] ownkeys.discard(curbox) ownboxes.discard(curbox)

        for key in keys[curbox]:
            if key in ownboxes:
                if key not in kaiguo:
                    q.append(key)
                    kaiguo.add(key)
            else:
                ownkeys.add(key)
        for box in containedBoxes[curbox]:
            if status[box]==1 or (box in ownkeys):
                if box not in kaiguo:
                    q.append(box)
                    kaiguo.add(box)
            else:
                ownboxes.add(box)
    return res

[Bochengwan]

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

[FireHaoSky]

思路：bfs，记录遍历过的信息

代码：python

class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        boxes = set(initialBoxes)
        q = [i for i in boxes if status[i]]
        for i in q:
            for j in containedBoxes[i]:
                boxes.add(j)
                if status[j]:
                    q.append(j)
            for j in keys[i]:
                if status[j] == 0 and j in boxes:
                    q.append(j)
                status[j] = 1
        return sum(candies[i] for i in q)

复杂度分析：

"""
时间复杂度：O(n)
空间复杂度：O(n)
"""

[Abby-xu]

class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        from collections import defaultdict, deque
        queue = deque()
        closedboxes = set()
        availkeys = set()
        candycount = 0
        for ib in initialBoxes:
            if status[ib] == 1:
                queue.append(ib)
            else:
                closedboxes.add(ib)
        while queue:
            currentbox = queue.popleft()
            candycount += candies[currentbox]
            for cb in containedBoxes[currentbox]:
                if status[cb] == 1:
                    queue.append(cb)
                else:
                    closedboxes.add(cb)
            for k in keys[currentbox]:
                availkeys.add(k)
            for c in closedboxes.intersection(availkeys):
                queue.append(c)
                closedboxes.remove(c)
                availkeys.remove(c)

        return candycount

[Zoeyzyzyzy]

class Solution {
    //要点：对于第i个盒子，只有拥有这个盒子（初始时拥有/从某个盒子里开出）并且能打开它（初始状态为1/得到了他的钥匙）才能获得其中糖果
    //Analysis: 1. hasBox - shows whether we have this box, canOpen - shows if the state is 1 / we have the key, used - we've already calculated it. 
    //          2. initial canOpen depends on initial state. Use a queue to record if this box can be added.
    //              a. we have these initial boxes, however, we only care box that we can open at first step.
    //              b. we need to find more boxes through previous opened boxes. Because all the boxes in the queue can be opened, so we can use cur box's key set to open more boxes.
    //              c. we also need to find if cur keys can open cur box's boxes, if can, we add it into queue for further caculate.
    //          3. When the queue is emepty, we return the answer cuz we find all we need.

    //Time Complexity: O(n+m) m is the number of keys, Space Complexity: O(n)

    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        int n = status.length;
        int[] canOpen = new int[n];
        int[] hasBox = new int[n];
        int[] used = new int[n];
        for (int i = 0; i < n; i++) {
            canOpen[i] = status[i];
        }

        LinkedList<Integer> queue = new LinkedList<>();
        int res = 0;
        for (int box : initialBoxes) {
            hasBox[box] = 1;
            if (canOpen[box] == 1) {
                queue.offer(box);
                used[box] = 1;
                res += candies[box];
            }
        }

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int key : keys[cur]) {
                canOpen[key] = 1;
                if (used[key] == 0 && hasBox[key] == 1) {
                    queue.offer(key);
                    used[key] = 1;
                    res += candies[key];
                }
            }
            for (int box : containedBoxes[cur]) {
                hasBox[box] = 1;
                if (used[box] == 0 && canOpen[box] == 1) {
                    queue.offer(box);
                    used[box] = 1;
                    res += candies[box];
                }
            }
        }
        return res;
    }
}

[xb798298436]

public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) { int res = 0; Queue q = new LinkedList<>(); for (int i : initialBoxes) if ((status[i] += 5000) > 5000) q.add(i); while (q.size() > 0) { int b = q.remove(); res += candies[b]; for (int i : keys[b]) if ((status[i] += 5) == 5005) q.add(i); for (int i : containedBoxes[b]) if ((status[i] += 5000) > 5000) q.add(i); } return res; }

[zhangyu1131]

class Solution {
public:
    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
        // bfs
        if (initialBoxes.empty())
        {
            return 0;
        }
        int n = status.size();

        vector<int> visited(n, 0);
        int max_candies = 0;
        vector<int> valid_keys(n, 0);
        vector<int> valid_boxes(n, 0); // 下标为1表示拥有

        queue<int> qu;
        for (auto num : initialBoxes)
        {
            qu.push(num);
            //visited[num] = 1;
            valid_boxes[num] = 1;// 初始就有的
        }
        while (!qu.empty())
        {
            auto idx = qu.front();
            qu.pop();
            if (visited[idx])
            {
                continue;
            }

            if (valid_boxes[idx] == 1 && (status[idx] == 1 || valid_keys[idx] == 1))
            {
                visited[idx] = 1;
                max_candies += candies[idx];

                // 多了些钥匙
                for(auto key : keys[idx])
                {
                    valid_keys[key] = 1;
                    qu.push(key);
                }
                // 多了些盒子
                for (auto box : containedBoxes[idx])
                {
                    if (!visited[box])
                    {
                        valid_boxes[box] = 1;
                        qu.push(box);
                    }
                }
            }
        }

        return max_candies;
    }
};

[harperz24]

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 = [0] * n
        visited = [0] * n

        q = collections.deque()
        res = 0

        for box in initialBoxes:
            has_box[box] = 1
            if status[box]:
                q.append(box)
                visited[box] = 1
                res += candies[box]

        while q:
            big_box = q.popleft()
            for key in keys[big_box]:
                status[key] = 1
                if not visited[key] and has_box[key]:
                    q.append(key)
                    visited[key] = 1
                    res += candies[key]
            for box in containedBoxes[big_box]:
                has_box[box] = 1
                if not visited[box] and status[box]:
                    q.append(box)
                    visited[box] = 1
                    res += candies[box]
        return res

        # bfs
        # time: O(n)
        # space: o(n)

[Hughlin07]

public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {

    int res = 0;
    Queue<Integer> q = new LinkedList<>();
    for (int i : initialBoxes)
        if ((status[i] += 5000) > 5000)
            q.add(i);
    while (q.size() > 0) {
        int b = q.remove();
        res += candies[b];
        for (int i : keys[b])
            if ((status[i] += 5) == 5005)
                q.add(i);
        for (int i : containedBoxes[b])
            if ((status[i] += 5000) > 5000)
                q.add(i);
    }
    return res;

}

[KrabbeJing]

class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        boxes_i_have = set(initialBoxes)
        boxes_i_can_open = [i for i in boxes_i_have if status[i]]
        for box_i in boxes_i_can_open:
            # 先把盒子box_i里内含的盒子放到我拥有的一堆
            for j in containedBoxes[box_i]:
                boxes_i_have.add(j)
            # 能打开的放到能打开的一队
                if status[j]:
                    boxes_i_can_open.append(j)
            # 再使用box_i里面放的钥匙
            for k in keys[box_i]:
                if status[k] == 0 and k in boxes_i_have:
                    boxes_i_can_open.append(k)
                # 一定要记得状态置为可以打开
                status[k] = 1
        return sum(candies[i] for i in boxes_i_can_open)

[Size-of]

var maxCandies = function(status, candies, keys, containedBoxes, initialBoxes) { let sum = 0 const n = status.length let has_box = new Array(n).fill(false) let has_key = new Array(n).fill(false) let open = new Array(n).fill(false) function open(box){ if(open[box]) return
if(!has_box[box]) return if(status[box]===0 && !has_key[box]) return open[box] = true sum += candies[box]
for(let next of keys[box]){
has_key[next] = true open(next) } for(let next of containedBoxes[box]){ has_box[next] = true open(next) } } for(let box of initialBoxes){ has_box[box] = true open(box) } return sum };

[RestlessBreeze]

code

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;
    }
};

[chocolate-emperor]

class Solution {
public:
// 思路：bfs去搜索，要注意的是，拿到的箱子可以是 打开 或 关闭，只入队打开的箱子；
// 关闭的箱子标记一下已持有，bfs每一层遍历结束时将原本关系但是现在能打开的箱子入队。
// 为简化操作，拿到钥匙后，立马修改箱子状态
// 箱子状态： 已持有-》持有未打开-》持能能打开-》持有并开完，队列中放入 持有能打开的箱子

    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
        int n =status.size();
        vector<int>taken(n,0);
        vector<int>keep(n,0);
        queue<int>q;
        int res = 0;

        for(auto i:initialBoxes){
            if(status[i])   q.push(i);
            else  keep[i] = 1;
        }

        while(!q.empty()){
            int l = q.size();

            for(int i = 0; i<l; i++){
                int curr = q.front();
                q.pop();

                res += candies[curr];
                taken[curr]=1;
                for(auto j:keys[curr])  status[j]=1;
                for(auto j:containedBoxes[curr]){
                    if(taken[j]) continue;
                    else if(status[j]==0)     keep[j] = 1;
                    else  q.push(j);
                }
            }
            for(int i=0; i<n; i++){
                if(taken[i]==0 && status[i]==1 && keep[i]==1){
                    q.push(i);
                    keep[i]=0;
                }
            }
        }
        return res;
    }
};

[kangliqi1]

public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) { int res = 0; Queue q = new LinkedList<>(); for (int i : initialBoxes) if ((status[i] += 5000) > 5000) q.add(i); while (q.size() > 0) { int b = q.remove(); res += candies[b]; for (int i : keys[b]) if ((status[i] += 5) == 5005) q.add(i); for (int i : containedBoxes[b]) if ((status[i] += 5000) > 5000) q.add(i); } return res; }

[bookyue]

TC: O(n)
SC: O(n)

    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        Set<Integer> keySet = new HashSet<>();
        Set<Integer> closed = new HashSet<>();
        Queue<Integer> queue = new ArrayDeque<>();
        int ans = 0;

        for (int initialBox : initialBoxes) {
            if (status[initialBox] == 1) {
                for (int key : keys[initialBox]) keySet.add(key);
                queue.offer(initialBox);
            } else {
                closed.add(initialBox);
            }
        }

        while (!queue.isEmpty()) {
            int box = queue.poll();
            ans += candies[box];

            for (int containedBox : containedBoxes[box]) {
                if (status[containedBox] == 1) {
                    for (int key : keys[containedBox]) keySet.add(key);
                    queue.offer(containedBox);
                } else {
                    closed.add(containedBox);
                }
            }

            for (int cBox : closed) {
                if (keySet.contains(cBox))
                    for (int key : keys[cBox]) keySet.add(key);
            }

            for (int cBox : closed) {
                if (keySet.contains(cBox))
                    queue.offer(cBox);
            }

            closed.removeAll(keySet);
        }

        return ans;
    }

[joemonkeylee]

public int MaxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) { int candiesCount = 0; int n = status.Length; bool[] open = new bool[n]; for (int i = 0; i < n; i++) { open[i] = status[i] == 1; } bool[] obtained = new bool[n]; bool[] visited = new bool[n]; Queue queue = new Queue(); foreach (int box in initialBoxes) { obtained[box] = true; if (open[box]) { visited[box] = true; queue.Enqueue(box); } } while (queue.Count > 0) { int box = queue.Dequeue(); candiesCount += candies[box]; int[] nextKeys = keys[box]; foreach (int next in nextKeys) { open[next] = true; if (obtained[next] && !visited[next]) { visited[next] = true; queue.Enqueue(next); } } int[] nextBoxes = containedBoxes[box]; foreach (int next in nextBoxes) { obtained[next] = true; if (open[next] && !visited[next]) { visited[next] = true; queue.Enqueue(next); } } } return candiesCount; }

[Diana21170648]

思路

BFS

代码

class Solution:
    def maximum_candies(self, status: list[int], candies: list[int], keys: list[list[int]], containedBoxes: list[list[int]], initialBoxes : list[int]) -> int :
          boxes = set(initialBoxes)
          queue = [i for i in boxes if status[i]]
         for i in queue:
              for j in containedBoxes[i]:
                   boxes.add(j)
                      if status[j]:
                      queue.append(j)
                      for j in keys[i]:
                           if status[j] == 0 and j in boxes:
                              queue.append(j)
                           status[j] = 1
                          return sum(candies[i] for i in queue)
print(sum)

**复杂度分析**
- 时间复杂度：O(N)
- 空间复杂度：O(N)

[Lydia61]

1298. 你能从盒子里拿到的最大糖果数

思路

class Solution {
public:
    int maxCandies(vector<int> &status, vector<int> &candies, vector<vector<int>> &keys,
                   vector<vector<int>> &containedBoxes, vector<int> &initialBoxes) {
        int ans = 0;
        queue<tuple<int, int, int, vector<int>, vector<int>>> queue;
        set<int> unlock;
        map<int, tuple<int, int, int, vector<int>, vector<int>>> map;

        for (int v: initialBoxes) {
            auto t = make_tuple(v, status[v], candies[v], keys[v], containedBoxes[v]);
            queue.push(t);
        }

        while (!queue.empty()) {
            int size = queue.size();
            while (size-- > 0) {
                auto [id, statue, candy, key, box] = queue.front();
                queue.pop();

                if (!statue && !unlock.count(id)) {
                    map[id] = make_tuple(id, statue, candy, key, box);
                } else {
                    ans += candy;
                    for (int k: key) {
                        unlock.insert(k);
                        if (map.count(k)) {
                            queue.push(map[k]);
                            map.erase(k);
                        }
                    }
                    for (int v: box) {
                        auto t = make_tuple(v, status[v], candies[v], keys[v], containedBoxes[v]);
                        queue.push(t);
                    }
                }
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N )

[yingchehu]

class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        ownOpenedBox = []
        ownBox = dict()
        for i in initialBoxes:
            if status[i] == 1:
                ownOpenedBox.append(i)
            else:
                ownBox[i] = None

        amt = 0
        for b in ownOpenedBox:
            amt += candies[b]
            for n in containedBoxes[b]:
                if status[n] == 1:
                    ownOpenedBox.append(n)
                else:
                    ownBox[n] = None
            for k in keys[b]:
                if k in ownBox:
                    ownOpenedBox.append(k)
                    del ownBox[k] # 要刪掉開過的
                status[k] = 1

        return amt

[X1AOX1A]

    def maxCandies(self, status, candies, keys, containedBoxes, initialBoxes):
        boxes = set(initialBoxes)
        q = [i for i in boxes if status[i]]
        for i in q:
            for j in containedBoxes[i]:
                boxes.add(j)
                if status[j]:
                    q.append(j)
            for j in keys[i]:
                if status[j] == 0 and j in boxes:
                    q.append(j)
                status[j] = 1
        return sum(candies[i] for i in q)

[aoxiangw]

class Solution:
    def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
        boxes = set(initialBoxes)
        q = [i for i in boxes if status[i]]
        for i in q:
            for j in containedBoxes[i]:
                boxes.add(j)
                if status[j]:
                    q.append(j)
            for j in keys[i]:
                if status[j] == 0 and j in boxes:
                    q.append(j)
                status[j] = 1
        return sum(candies[i] for i in q)

time, space: O(n^2), O(n)

[wwewwt]

思路

先根据盒子找钥匙，再根据钥匙+找盒子，知道最后盒子没有更新

代码

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

复杂度

O(N)

[snmyj]

class Solution {
public:
    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
        queue<int> q;
        int sum = 0, id;
        unordered_set<int> nokeybox;
        for(int box : initialBoxes)
        {
            q.push(box);
        }
        while(!q.empty())
        {
            id = q.front();
            q.pop();
            sum += candies[id];
            for(int k : keys[id])
            {
                status[k] = 1;
                if(nokeybox.count(k))
                {   
                    q.push(k);//入队
                    nokeybox.erase(k);
                }
            }
            for(int box : containedBoxes[id])
            {
                if(status[box]==1)
                    q.push(box);
                else
                    nokeybox.insert(box);
            }
        }
        return sum;
    }
};

[Jetery]

class Solution {
public:
    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
        int res = 0;
        unordered_set<int> boxes(initialBoxes.begin(), initialBoxes.end());

        while (1) {
            unordered_set<int> new_boxes;
            unordered_set<int> opened_boxes;
            for (int x : boxes)
                if (status[x]) {
                    opened_boxes.insert(x);
                    res += candies[x];
                    for (int k : keys[x])
                        status[k] = true;

                    for (int b : containedBoxes[x])
                        new_boxes.insert(b);
                }

            if (opened_boxes.empty())
                break;

            for (int b : opened_boxes)
                boxes.erase(b);

            for (int b : new_boxes)
                boxes.insert(b);
        }

        return res;
    }
};

[Fuku-L]

代码

class Solution {
    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        int len = status.length;
        boolean[] visited = new boolean[len];
        Set<Integer> haveBox = new HashSet<>();
        Set<Integer> haveKey = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i< initialBoxes.length; i++){
            int idx = initialBoxes[i];
            haveBox.add(idx);
            if(status[idx] == 1){
                q.offer(idx);
                visited[idx] = true;
            }
        }

        int ans = 0;
        while(!q.isEmpty()){
            Integer cur = q.poll();
            ans+= candies[cur];
            int[] curKey = keys[cur];
            int[] curBox = containedBoxes[cur];
            for(int key:curKey){
                haveKey.add(key);
                if(!visited[key] && haveBox.contains(key)){
                    q.offer(key);
                    visited[key] = true;
                }
            }
            for(int box: curBox){
                haveBox.add(box);
                if(!visited[box] && (haveKey.contains(box) || status[box] == 1)){
                    q.offer(box);
                    visited[box] = true;
                }
            }
        }
        return ans;
    }
}

[tzuikuo]

思路

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=initialBoxes.size(),cntcandy=0,m=status.size();
        queue<int> openque;
        vector<int> havebox(m,0);
        for(int i=0;i<n;i++){
            if(status[initialBoxes[i]]==1) openque.push(initialBoxes[i]);
            else havebox[initialBoxes[i]]=1;
        }
        while(!openque.empty()){
            int curbox=openque.front();
            cout<<curbox<<endl;
            openque.pop();
            havebox[curbox]=0;
            cntcandy+=candies[curbox];
            for(int i=0;i<keys[curbox].size();i++){
                status[keys[curbox][i]]=1;
            }
            for(int i=0;i<containedBoxes[curbox].size();i++){
                havebox[containedBoxes[curbox][i]]=1;
            }
            for(int i=0;i<m;i++){
                if(havebox[i]==1&&status[i]==1){
                    havebox[i]=0;
                    openque.push(i);
                }
            }
        }
        return cntcandy;

    }
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[lp1506947671]

 def maxCandies(self, status, candies, keys, containedBoxes, initialBoxes):
        boxes = set(initialBoxes)
        q = [i for i in boxes if status[i]]
        for i in q:
            for j in containedBoxes[i]:
                boxes.add(j)
                if status[j]:
                    q.append(j)
            for j in keys[i]:
                if status[j] == 0 and j in boxes:
                    q.append(j)
                status[j] = 1
        return sum(candies[i] for i in q)

令 n 为盒子数，k 为钥匙数，由于每个盒子最多会被访问一次，因此队列长度以及循环次数都不超过 n。

由于钥匙和盒子最多被访问一次，因此时间不超过 n + k。

复杂度分析

• 时间复杂度：O(n + k)
• 空间复杂度：O(n)