你能从盒子里获得的最大糖果数
难度:
标签:
题目描述
代码结果
运行时间: 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)来处理这个问题?
▷🦆
此算法中,used数组的作用是什么?为什么需要标记盒子是否已被使用?
▷🦆
在处理队列时,为什么要检查钥匙对应的盒子是否已经拥有并且未使用过?这样的检查是如何影响算法效率的?
▷🦆
如果有多个盒子可以通过当前钥匙打开,算法是如何决定处理哪一个盒子的顺序的?这会影响最终获取的糖果总数吗?
▷