java - Google Foobar 4 级 RunningWithTheBunnies
问题描述
我被困在 foobar 问题的一个测试用例上。
问题和我的代码如下
你和你获救的兔子囚犯需要摆脱这个空间站崩溃的死亡陷阱——而且要快！不幸的是，一些兔子因长期监禁而变得虚弱，不能跑得很快。他们的朋友正在努力帮助他们，但如果你也投入其中，这次逃跑会更快。防御舱壁门已经开始关闭，如果你不及时通过，你会被困住！您需要尽可能多地抓住兔子并在它们关闭之前穿过舱壁。
从您的起点移动到所有兔子和舱壁所需的时间将以整数方阵的形式提供给您。每一行都会告诉你到达开始所需要的时间，第一只兔子，第二只兔子，...，最后一只兔子，以及按顺序排列的隔板。行的顺序遵循相同的模式（开始，每个兔子，隔板）。兔子可以跳进你的怀抱，因此可以立即将它们捡起来，并且在密封的同时到达舱壁仍然可以成功逃脱，即使是戏剧性的逃脱。（别担心，任何你没有捡到的兔子都可以和你一起逃跑，因为它们不再需要携带你捡到的兔子。）如果你愿意，你可以重新访问不同的地方，然后移动到舱壁没有
除了花时间在兔子之间旅行之外，一些路径还与空间站的安全检查站交互，并将时间加回时钟。向时钟添加时间将延迟舱壁门的关闭，如果在门已经关闭后时间回到 0 或正数，则会触发舱壁重新打开。因此，有可能绕着一个圈走并不断获得时间：也就是说，每次经过一条路径，都会使用或增加相同的时间。
编写一个形式为 answer(times, time_limit) 的函数来计算您可以捡起的最多兔子以及它们是哪些兔子，同时在门永远关闭之前仍然通过舱壁逃生。如果有多个相同大小的兔子集，则按排序顺序返回具有最低囚犯 ID（作为索引）的兔子集。bunnies 表示为一个按囚犯 ID 排序的列表，第一个 bunny 为 0。最多有 5 个 bunnies，time_limit 是一个非负整数，最多为 999。
例如，在 [
[0, 2, 2, 2, -1] 的情况下，#0 = Start
[9, 0, 2, 2, -1], #1 = Bunny 0
[9, 3, 0, 2, -1], # 2 = Bunny 1
[9, 3, 2, 0, -1], # 3 = Bunny 2
[9, 3, 2, 2, 0], # 4 = Bulkhead ] 和时间限制在 1 中，五个内部阵列行分别指定起点、兔子 0、兔子 1、兔子 2 和舱壁门出口。你可以走这条路：开始 结束 Delta 时间状态 - 0 - 1 隔板最初打开 0 4 -1 2 4 2 2 0 2 4 -1 1 4 3 2 -1 隔板关闭 3 4 -1 0 隔板重新打开；你和兔子离开 使用这个解决方案，你会捡起兔子 1 和 2。这是这个空间站走廊的最佳组合，所以答案是 [1, 2]。
测试用例输入：
(int) 次 = [[0, 1, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 0, 1, 1], [1, 1, 1, 0 , 1], [1, 1, 1, 1, 0]] (int) time_limit = 3 输出：
(int list) [0, 1] 输入：
(int) 次 = [[0, 2, 2, 2, -1], [9, 0, 2, 2, -1], [9, 3, 0, 2, -1], [9, 3, 2, 0, -1], [9, 3, 2, 2, 0]] (int) time_limit = 1 输出：
（整数列表）[1, 2]
在下面添加我的代码。
public class RunningWithBunnies {
public static class FloydWarshall {
private final Integer[][] allPairShortestPathMatrix;
private final Integer[][] pathFinderMatrix;
public FloydWarshall(final Integer[][] matrix) {
if (matrix.length != matrix[0].length) {
throw new IllegalArgumentException("Bad Adj Matrix Passed");
}
allPairShortestPathMatrix = new Integer[matrix.length][matrix[0].length];
pathFinderMatrix = new Integer[matrix.length][matrix[0].length];
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[i].length; j++) {
allPairShortestPathMatrix[i][j] = matrix[i][j];
if(matrix[i][j] != null) {
pathFinderMatrix[i][j] = j;
}
}
}
findAllPairsShortestPath(matrix);
}
public int getShortestDistanceBetweenNodes(final int startNode, final int endNode) {
return allPairShortestPathMatrix[startNode][endNode];
}
public List<Integer> findShortestPathBetweenNodes(final int startNode, final int endNode) {
final List<Integer> path = new ArrayList<>();
Integer currentNode = startNode;
path.add(startNode);
while (currentNode != endNode) {
currentNode = pathFinderMatrix[currentNode][endNode];
if (currentNode == null || allPairShortestPathMatrix[currentNode][currentNode] < 0) {
return Collections.emptyList();
}
path.add(currentNode);
}
return new ArrayList<>(path);
}
public boolean doesMatrixContainNegativeCycles() {
for (int i = 0; i < allPairShortestPathMatrix.length; i++) {
if (allPairShortestPathMatrix[i][i] < 0) {
return true;
}
}
return false;
}
private void findAllPairsShortestPath(final Integer[][] matrix) {
for(int k = 0; k < matrix.length; k++) {
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[i].length; j++) {
final Integer directPathCost = allPairShortestPathMatrix[i][j];
final Integer indirectPathToIntermediateCost = allPairShortestPathMatrix[i][k];
final Integer indirectPathFromIntermediateCost = allPairShortestPathMatrix[k][j];
if (indirectPathToIntermediateCost != null && indirectPathFromIntermediateCost != null) {
if (directPathCost == null ||
(directPathCost > indirectPathToIntermediateCost + indirectPathFromIntermediateCost)) {
allPairShortestPathMatrix[i][j] = allPairShortestPathMatrix[i][k] + allPairShortestPathMatrix[k][j];
pathFinderMatrix[i][j] = pathFinderMatrix[i][k];
}
}
}
}
}
}
}
public static int[] solution(int[][] times, int times_limit) {
final Integer[][] matrix = new Integer[times.length][times[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
matrix[i][j] = times[i][j];
}
}
final FloydWarshall floydWarshall = new FloydWarshall(matrix);
final Set<Integer> bunniesLeft = IntStream
.range(1, matrix.length - 1)
.boxed()
.collect(Collectors.toSet());
if (floydWarshall.doesMatrixContainNegativeCycles()) {
return bunniesLeft
.stream()
.mapToInt(bunny -> bunny - 1)
.toArray();
}
final List<Integer[]> path = new ArrayList<>();
int currentPos = 0;
int pathCost = 0;
while (!bunniesLeft.isEmpty()) {
int nearestBunnyPathDuration = Integer.MAX_VALUE;
int nearestBunny = -1;
for (int bunnyPosition : bunniesLeft) {
if (bunnyPosition != currentPos
&& bunniesLeft.contains(bunnyPosition)
&& floydWarshall.getShortestDistanceBetweenNodes(currentPos, bunnyPosition) < nearestBunnyPathDuration) {
nearestBunnyPathDuration = floydWarshall.getShortestDistanceBetweenNodes(currentPos, bunnyPosition);
nearestBunny = bunnyPosition;
}
}
if (nearestBunny == -1) {
break;
}
final List<Integer> subPath =
floydWarshall
.findShortestPathBetweenNodes(currentPos, nearestBunny)
.stream()
.filter(bunniesLeft::contains)
.collect(Collectors.toList());
currentPos = nearestBunny;
for (int subPathNode : subPath) {
path.add(new Integer[]{
subPathNode,
path.isEmpty()
? floydWarshall.getShortestDistanceBetweenNodes(0, subPathNode)
: pathCost + floydWarshall.getShortestDistanceBetweenNodes(path.get(path.size() - 1)[0], subPathNode)
});
bunniesLeft.remove(subPathNode);
pathCost = path.get(path.size() - 1)[1];
}
}
path.removeIf(pathNode ->
pathNode[1] + floydWarshall.getShortestDistanceBetweenNodes(pathNode[0], matrix.length - 1) > times_limit
);
if (path.isEmpty()) {
return new int[]{};
}
return path
.stream()
.mapToInt(node->node[0] - 1)
.sorted()
.toArray();
}
}
只有测试用例 8 失败。我在堆栈溢出中看到了其他解决方案，但没有人采用这种方法。将不胜感激任何关于我在这里缺少什么的指针。
谢谢！
解决方案
推荐阅读
- python - Pyspark - 将两列中的值转换为字典
- python - TF2、Tensorflow Probability 随机种子生成器和 VAE
- node.js - 节点缓存是否使用锁
- python - 使用python读取vb文件时无法识别的符号
- php - PHP MYSQL ODBC 连接成功但未检索数据
- amazon-web-services - 如何将 AWS 应用程序负载均衡器和 NAT 网关配置为具有公共 IP
- node.js - 如何在 Apple Silicon M1 上原生安装 NodeJS？
- excel - Power Pivot 2016 中的 DAX 计算度量
- python - Python3 不正确的 AES 密钥长度（256 字节）
- reactjs - Firebase 提取时间过长