leetcode
leetcode 1201 ~ 1250
你能从盒子里获得的最大糖果数

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

难度:

标签:

题目描述

代码结果

运行时间: 59 ms, 内存: 26.1 MB


/**
 * Solution using Java Streams to find the maximum number of candies.
 * This solution processes the initial set of boxes and dynamically expands
 * the set of accessible boxes using Streams. This approach is less optimal
 * than the queue-based solution for real-world use but demonstrates the use
 * of functional programming style.
 */
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class MaximumCandiesStream {
    public int maxCandies(int[] status, int[] candies, int[][] keys, int[][] containedBoxes, int[] initialBoxes) {
        Set<Integer> accessibleBoxes = new HashSet<>();
        Set<Integer> foundBoxes = new HashSet<>();
        Set<Integer> collectedKeys = new HashSet<>();
        int totalCandies = 0;

        Collections.addAll(foundBoxes, Arrays.stream(initialBoxes).boxed().toArray(Integer[]::new));

        boolean progress = true;
        while (progress) {
            progress = false;
            for (int box : foundBoxes) {
                if ((status[box] == 1 || collectedKeys.contains(box)) && accessibleBoxes.add(box)) {
                    totalCandies += candies[box];
                    collectedKeys.addAll(Arrays.stream(keys[box]).boxed().collect(Collectors.toSet()));
                    foundBoxes.addAll(Arrays.stream(containedBoxes[box]).boxed().collect(Collectors.toSet()));
                    progress = true;
                }
            }
        }
        return totalCandies;
    }
}

解释

方法:

此题解采用广度优先搜索(BFS)策略来解决问题。首先,我们初始化一些基本数据结构:can_open数组用于标记每个盒子是否可以打开,has_box数组用于标记我们是否拥有某个盒子,used数组用于标记盒子是否已被处理过。将初始盒子加入队列q,并更新对应的状态。随后,从队列中逐个取出盒子,收集糖果,使用钥匙尝试打开新盒子,并将新发现的盒子加入队列。此过程持续进行直到队列为空,此时,所有可以通过当前条件打开的盒子都已处理完毕。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在算法实现中,为什么选择广度优先搜索(BFS)而不是深度优先搜索(DFS)来处理这个问题?
在此问题中,广度优先搜索(BFS)被选择是因为它按层次处理每个盒子和相关的钥匙,这样可以更快地解锁新盒子并访问更多的糖果。相比之下,深度优先搜索(DFS)可能会导致算法深入到一个分支,延迟发现其他可立即打开的盒子。BFS确保一旦获得新的钥匙或盒子,就能尽快处理,从而更有效率地最大化糖果的收集。
🦆
此算法中,used数组的作用是什么?为什么需要标记盒子是否已被使用?
used数组在算法中用于标记一个盒子是否已经被处理过。这是必须的,因为一个盒子可能多次成为处理的候选(例如,通过不同的钥匙或者直接拥有),而我们需要确保每个盒子只被处理一次以避免重复操作和潜在的无限循环。此外,这也帮助算法保持高效,减少不必要的重复处理,从而优化性能。
🦆
在处理队列时,为什么要检查钥匙对应的盒子是否已经拥有并且未使用过?这样的检查是如何影响算法效率的?
检查钥匙对应的盒子是否已经拥有并且未使用过是为了确保我们不遗漏任何可以立即打开的盒子。这种检查可以防止算法浪费资源去尝试打开一个已经在处理中或已处理的盒子,同时也确保所有获取的钥匙都被有效利用。这种策略提高了算法的效率,因为它减少了不必要的队列操作和重复检查,使算法能够集中处理那些确实可以带来新糖果和新机会的盒子。
🦆
如果有多个盒子可以通过当前钥匙打开,算法是如何决定处理哪一个盒子的顺序的?这会影响最终获取的糖果总数吗?
在此BFS算法实现中,并没有特定的规则来决定多个可打开盒子的处理顺序;它们是按照它们被发现和加入队列的顺序处理的。由于问题的性质,处理不同盒子的顺序并不影响最终可以获得的糖果总数,只要所有可通过当前钥匙打开的盒子最终都被处理。这意味着无论处理顺序如何,只要遍历完所有的可能性,收集到的糖果总数都是相同的。

相关问题