javascript - 你可以从盒子算法中获得的最大糖果 - JavaScript

Question

我正在用 JS 解决下面的问题。

给定 n 个盒子，每个盒子以 [status, candies, keys, containsBoxes] 的格式给出，其中：

status[i]：一个整数，如果 box[i] 打开则为 1，如果 box[i] 关闭则为 0。candies[i]：一个整数，表示 box[i] 中的糖果数量。keys[i]：一个数组，包含你可以用 box[i] 中的键打开的盒子的索引。containsBoxes[i]：一个数组包含在 box[i] 中找到的盒子的索引。您将从 initialBoxes 数组中给出的一些框开始。您可以在任何打开的盒子中取出所有糖果，您可以使用其中的钥匙打开新盒子，也可以使用您在其中找到的盒子。

按照上述规则返回您可以获得的最大糖果数量。

例子：

Input: status = [1,0,1,0], candies = [7,5,4,100], keys = [[],[],[1],[]], containedBoxes = [[1,2],[3],[],[]], initialBoxes = [0]
Output: 16
Explanation: You will be initially given box 0. You will find 7 candies in it and boxes 1 and 2. Box 1 is closed and you don't have a key for it so you will open box 2. You will find 4 candies and a key to box 1 in box 2.
In box 1, you will find 5 candies and box 3 but you will not find a key to box 3 so box 3 will remain closed.
Total number of candies collected = 7 + 4 + 5 = 16 candy.

我的解决方案：

var maxCandies = function(status, candies, keys, containedBoxes, initialBoxes) {
    let total = 0;
    let visited = new Set();
    let queue = [];
    let myKeys = new Set();
    
    for(let i=0; i<initialBoxes.length; i++) {
        queue.push(initialBoxes[i]);
        myKeys.add(initialBoxes[i]);
    }
    
    for(let i=0; i<queue.length; i++) {
        const key = keys[queue[i]];
        while(key.length)
            myKeys.add(key.shift());
    }
    
    while(queue.length) {
        const box = queue.shift();
        if(!visited.has(box)) {
            const boxes = containedBoxes[box];
            for(let j=0; j<boxes.length; j++) {
                if(!visited.has(boxes[j]))
                    queue.push(boxes[j]);
            }
            const getkeys = keys[box];
            for(let j=0; j<getkeys.length; j++){
                if(!visited.has(getkeys[j])) {
                    myKeys.add(getkeys[j]);
                    queue.push(getkeys[j]);   
                }
            }
            if(myKeys.has(box) || status[box] === 1) {
                total += candies[box];
                visited.add(box);   
            }
        }
    }
    
    return total;
};

它返回上述示例和其他一些测试的预期结果。但是，下面的输入失败了。

[1,1,1,1,0,0,1,1,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,1,1,1,0,0,0,1,1,1,1,0,0,1,0,1,0,0,0,1,0,1,1,0,1,0,1,0,0,1,1,1,1,1,0,0,0,0,1,1,0,0,0,1,0,1,1,1,0,0,1,1,1,1,1,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1,0,1,0,1,1,1,0,1]
[292,873,110,133,23,240,694,282,404,398,794,657,118,798,613,391,356,601,686,494,219,245,124,638,172,661,2,590,286,648,142,62,755,777,918,63,200,60,934,935,230,266,536,365,651,929,511,295,310,529,745,733,346,979,314,384,808,376,458,50,65,446,700,158,818,916,438,1,53,260,802,563,691,349,4,426,200,346,999,439,877,518,269,997,231,702,89,290,555,474,779,553,40,149,756,299,574,477,429,977,434]
[[63,84,99,73],[9,98,21,34,2,17,26,43],[84,85,100,19,92,33,40,91,66,96,30,3,60,74,72,95,36,29,90,4,98,21,48,56,87,42,97,32,13,93,27,39,81],[67,56,60,74,32,5,59,68,71,45,31,94,83,35,3,38,37,50,92],[81,54,84,63,51,33,80],[51,65,55],[6,57,54,96,90,13,74,23,83,37,64,99,21,2,98,61,19,26,11,29,17,86,28,52,48],[76,36,12,85,67,16,48,8],[],[78,6,53,77,30,41,52,82,35,18,70,32,20,55,58,7,47,88,21,72,16,67,79,90,33,68],[66,0,12,92,99,26,17,44,78,84,8,75,57,97,63,46,43,1,25,88],[54,72,19,62,34,76,28,68,18,75,98,1,87,73,40,57],[56,94,69,14,27,5,21,35],[35,13,29,84,43,97,9,0,19,76,93,48,81],[],[53,86,37,57,99,55,0,44,62,27,45,58,14,81,21,8,33,41,73,64,32,1,51,31,49],[52,62,91,51,72,13,31,34,37,3],[43,38,77,28,85,10,69,83,65,21,5,88,71,64,99,73,37,34,72,35,23,75,47,17],[25,24,61],[82],[100,89,71,16,10,17,90,73,78,22,86,82,48,3,47,0,76,31],[],[1,30,82,87,59,70,28,49,89,91,95,22,43,51,79,35,15,71,18,75,32,58,56],[16,30,95,88,39,56,20,38,27,67,98,0,46,42,92,93,99],[20,99],[33,78,98,9,84,96,20,4,83,18,56,85,70,38,71,10,100,12,14,89,49,60,32,86,17,91,46,8,21,68,44],[13,12,20,24,98,31,9,83,76,92,74,37,88,81,95,47,60,71,61,44,48,80,64,7,49],[58,77,29,63,90,44,49,43,38,23,85],[38,77,45,2,8,81,76,51,44,15,87,31,18,48,30,4,90,100,66,3,47,25,99,10,23,59,36,91,5],[30,98,26],[10,99,78,35,64,56,45,30,15,73,84,51,24,0,79,48,88,33,1,95,97,40,58,42,81],[64],[21,54,23,2,44],[84],[66,9,28,22,0,57,71,11,4,94,30,53,46,39,5,21,92,29,93,100,60,52,62,24,18,74,64],[35,14,95,70,67,30,38,46,74,60,82,28,22,89,57,48,3,29],[41,59,30,79,51,29,92,74,39,93,96,95,24,49,5,4,16,21,97,3,52,83],[32,70,50,57,19,82,49,1,86,37,71,60,77],[76,10,37,35,38,100,97,52,26,16,78,9,65,73,68,12,34,20,43,84,80,81,77,64,63,71,8,61,54],[95,24,9,0,11,74,71,87,78,56,99,61,5,10,55,34,14,80,96,65,35,42,39,67,23,60,58],[14,72,53,8,70,18,11,47,62,71,94,44,9,75,54,39,42,43,85,15,61,55,32,80,37,67,29,0,17,50],[31,22,10,40,34,45,8,63,36,78,83,54,71,87,72,23,41,25,27,60,35,49,14,11,42,92,9,46,56,29,38,77],[51,23,47,14,24,12,42,70,9,87,18,83,95,46,78,71,55,86,48,94,79,31,100,49,89,8,11,25,33],[65,100,38,97,31,77],[51,87,50,10,33,13,82,77,4,9,56,35,78,31,93,84,54,92,38,59,34,36,48,80,95,61,85,28],[34,9,1,85,41,13,52,19,46,50,22,62,69,78,79,49,54,8,83,15],[74,37,86,66,35,31,46,9,36,62,88,57,61,25,65,70,52],[67,33,14,50,49,45,60,37,19,6,54,4,46,64,97,96,52,11,78,38,93,62,51,48,92,10,29,75,16,41,55,58,74],[50,53,65,0,9,82,87,27,75,12,28,86],[64,32,18,60,45,92,33,24,10,58,40,21,9,57,61,90,70,73,28,59],[10,36,48,21,93,64,49,52,46,88,15,87,51,72,95,45,41,76,28,23,98,35],[26,38,64,25,62,56,61,76,81,8,11,88,89,98,100,35,63,34,30,91,49,83,72,96,10,97,80,24,82,13,65],[53,94,2,12,60,52,5,40,23,26,28,34,93,63,85,41],[35,66,1,56,30],[],[61,24,89,44,54,21,11,6,60,20,98,99],[18,55,45,31,36,38,60,95,30,58,48,63,20,34,86,59,8,51,14,100,17,24,3,16,35,73,80,84,94,49,40],[88,13,3,49,58],[88,52,1,40,71,46,10,36,18,4,42,45,91,50,79,58,19,14,0],[],[29,8,33,63,48,50,11,80,49,86,36,54,88,74],[92,60,90,76,80,87,56,71,57,0,48,70,37,38,83],[17,44,13,89,20,75,69,94,66,12,59,62,36,74,6,14,53,2],[55,79,21,13,89,61,74,69,70,76,75,50,66,58,34,93,37,22,88,7,28,51],[73,68,90,84,31,32,22,77,63,85,24,100,3],[50,6,45,15,66,25,79,37,82,41,33],[76,99,26],[40,73,50,84,69,11,19,6,14,12,74,67,97,8,33,7,55,70,63,44,100,25,79,36,76,94,54,53,22,38],[33,49,77,50,56,65,62,81],[47,75,88,20,50,74,23,18,61,69,49,41,58,35,60,99,53,7,77,96],[80,64,14,13,37,33,25,17,38,26,73,4,1,35],[75,16,85,97,31,83,96,82,78,54,73,62,79,55,42,51,43,36,99,26,57,67,24,84,23,47,61,50,63,0,94,66,20],[41,91,23,8,90,27,32,31,64,89,44,97,59,88,11,94,100,78,48,67,84],[46,56,32,71,40,26,83,44,76,73,59,22,24],[39,20,99,12,30,91,89,84,34,45,74,70,100,31,54,75,81,98,35,85,55,4,24,36],[25],[9,16,44,94,82,41,4,39,21,5,73,87,58,91,59,34,47,48,27,78,97,95,96,62,68,69,51,84],[27,20,40,28,77],[30],[76,31,91,36,62,7,78,23,63,68,86,26,8,39,64,85,54,42,29,18,17,47],[53,99,51],[27,80,37,92,40,9,56,52,34,67,10,33,48,73,26,59,83,65,64,4,3,68,85,69,63],[11,57,87,89,21,74,17,61,51,80,26,70,39,9,36,75,63,85,100,18,15,96,90,47,84],[66,74,84,5,13,0,57,23,8],[95,43,8,27,85,96,47,53,48,3,41,86,32,70,12,15,82,6,62,81,4,97,40,13,23,24,59,26,98,71,35],[35,29,64,85,63,50,67,43,54,39,94,65,87],[86,90,70,100,72,76,48,37,80,34],[44,1,25,14,41,9,72,32,19,92,100,55,0,30,76,26,99,96,16,21,11,70,74,49,65,59,27,94,87,62,3],[72,28,41,81,58,84,8,39,51,100,54,71,70,36,94,47,65,97,32,85,30,68,87,26,75,95],[86,52,26,100,0,11,19,20,82,21,88,84,9,65],[71,30,18,43,50,76,87,19],[18,64,20,80,91,0,45,97,78,98,31,23,38,8,17,32,9,55,86,44,40,77,85,14,11,81,22,42,89,63,7,60,13],[37,58,12,75,31,33,25,11,26,88,53,91,93,85,52,81,10,43,51,20,35,45,3],[88,26,23,64,56,5,21,16,15,39],[88,37,85,2,61,100,24,93,23,78,46,54,36,74,84,47,58,77,28],[],[15,23,54,73,21,33,76,96,89,12,48,10,9,92,61,59,65,42,29,37,86,27,20],[76,93,3,37,27,65,20,34,11,99,98,28,67,5,13,80,42,64,61,43,79,23,29],[41,54,81,17,90,23,75,4,62,46,52,57],[20,52,8,58,87,48,6,89,93],[49,9,34,28,41,69,87,50,54,83,96,44,5,12,86,76,92,2,19,48,4,55,85,10,25,1,78,15,61,74]]
[[],[],[41],[94],[],[63],[29],[46],[],[],[],[],[],[],[],[42,77],[],[],[],[],[64],[86],[],[8,15],[24],[],[100],[],[],[],[],[56],[],[84],[],[],[71],[],[23,83],[],[40],[],[],[20],[],[13,57],[51],[3,69],[],[68],[49],[],[28],[],[],[88],[],[52],[],[],[],[36],[14,55],[],[2],[95],[],[],[],[33],[],[93],[59],[],[74],[22],[47],[],[],[45],[35],[],[],[],[],[32],[],[1],[61],[],[],[],[44],[],[],[],[],[],[48],[],[85,96]]
[0,4,5,6,7,9,10,11,12,16,17,18,19,21,25,26,27,30,31,34,37,38,39,43,50,53,54,58,60,62,65,66,67,70,72,73,75,76,78,79,80,81,82,87,89,90,91,92,97,98,99]

预期的结果是45940。我的解决方案是返回46346。有谁知道为什么会这样？

谢谢

标签： javascriptarraysalgorithm

Answer 1

我不确定你的方法有什么问题，但这似乎有效。我没有使用“已访问”结构，但我实现了一个带有计数的散列，用于仍未打开的盒子，以及将任何可以打开的盒子（在初始之后）推送到堆栈，以便可以重用那里的过程。（顺便说一句，status有时似乎是一个保留变量，所以我将其重命名为_status。）

function f(_status, candies, keys, containedBoxes, initialBoxes){
  const closed = {};
  const myKeys = new Set();
  const stack = initialBoxes.map(x => [x, 1]);
  let result = 0;

  while (stack.length){
    const [box, boxCount] = stack.pop();

    // We can open the box
    if (myKeys.has(box) || _status[box]){
      // Get candies
      result += boxCount * candies[box];

      // Add boxes
      for (let newBox of containedBoxes[box]){
        if (myKeys.has(box) || _status[newBox])
          stack.push([newBox, 1])
        else
          closed[newBox] = -~closed[newBox];
      }

      // Get keys
      for (let newKey of keys[box]){
        myKeys.add(newKey);

        // Maybe use a new key
        if (closed[newKey]){
          stack.push([newKey, closed[newKey]]);
          delete closed[newKey];
        }
      }
      
    // We cannot open the box
    } else {
      closed[box] = -~closed[box];
    }
  }

  return result;
}


var _status = [1,0,1,0];
var candies = [7,5,4,100];
var keys = [[],[],[1],[]];
var containedBoxes = [[1,2],[3],[],[]];
var initialBoxes = [0]; // 16

console.log(f(_status, candies, keys, containedBoxes, initialBoxes));

var args = [
  [1,1,1,1,0,0,1,1,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,1,1,1,0,0,0,1,1,1,1,0,0,1,0,1,0,0,0,1,0,1,1,0,1,0,1,0,0,1,1,1,1,1,0,0,0,0,1,1,0,0,0,1,0,1,1,1,0,0,1,1,1,1,1,1,0,0,0,1,1,0,1,0,1,1,0,0,0,1,0,1,0,1,1,1,0,1],

  [292,873,110,133,23,240,694,282,404,398,794,657,118,798,613,391,356,601,686,494,219,245,124,638,172,661,2,590,286,648,142,62,755,777,918,63,200,60,934,935,230,266,536,365,651,929,511,295,310,529,745,733,346,979,314,384,808,376,458,50,65,446,700,158,818,916,438,1,53,260,802,563,691,349,4,426,200,346,999,439,877,518,269,997,231,702,89,290,555,474,779,553,40,149,756,299,574,477,429,977,434],

  [[63,84,99,73],[9,98,21,34,2,17,26,43],[84,85,100,19,92,33,40,91,66,96,30,3,60,74,72,95,36,29,90,4,98,21,48,56,87,42,97,32,13,93,27,39,81],[67,56,60,74,32,5,59,68,71,45,31,94,83,35,3,38,37,50,92],[81,54,84,63,51,33,80],[51,65,55],[6,57,54,96,90,13,74,23,83,37,64,99,21,2,98,61,19,26,11,29,17,86,28,52,48],[76,36,12,85,67,16,48,8],[],[78,6,53,77,30,41,52,82,35,18,70,32,20,55,58,7,47,88,21,72,16,67,79,90,33,68],[66,0,12,92,99,26,17,44,78,84,8,75,57,97,63,46,43,1,25,88],[54,72,19,62,34,76,28,68,18,75,98,1,87,73,40,57],[56,94,69,14,27,5,21,35],[35,13,29,84,43,97,9,0,19,76,93,48,81],[],[53,86,37,57,99,55,0,44,62,27,45,58,14,81,21,8,33,41,73,64,32,1,51,31,49],[52,62,91,51,72,13,31,34,37,3],[43,38,77,28,85,10,69,83,65,21,5,88,71,64,99,73,37,34,72,35,23,75,47,17],[25,24,61],[82],[100,89,71,16,10,17,90,73,78,22,86,82,48,3,47,0,76,31],[],[1,30,82,87,59,70,28,49,89,91,95,22,43,51,79,35,15,71,18,75,32,58,56],[16,30,95,88,39,56,20,38,27,67,98,0,46,42,92,93,99],[20,99],[33,78,98,9,84,96,20,4,83,18,56,85,70,38,71,10,100,12,14,89,49,60,32,86,17,91,46,8,21,68,44],[13,12,20,24,98,31,9,83,76,92,74,37,88,81,95,47,60,71,61,44,48,80,64,7,49],[58,77,29,63,90,44,49,43,38,23,85],[38,77,45,2,8,81,76,51,44,15,87,31,18,48,30,4,90,100,66,3,47,25,99,10,23,59,36,91,5],[30,98,26],[10,99,78,35,64,56,45,30,15,73,84,51,24,0,79,48,88,33,1,95,97,40,58,42,81],[64],[21,54,23,2,44],[84],[66,9,28,22,0,57,71,11,4,94,30,53,46,39,5,21,92,29,93,100,60,52,62,24,18,74,64],[35,14,95,70,67,30,38,46,74,60,82,28,22,89,57,48,3,29],[41,59,30,79,51,29,92,74,39,93,96,95,24,49,5,4,16,21,97,3,52,83],[32,70,50,57,19,82,49,1,86,37,71,60,77],[76,10,37,35,38,100,97,52,26,16,78,9,65,73,68,12,34,20,43,84,80,81,77,64,63,71,8,61,54],[95,24,9,0,11,74,71,87,78,56,99,61,5,10,55,34,14,80,96,65,35,42,39,67,23,60,58],[14,72,53,8,70,18,11,47,62,71,94,44,9,75,54,39,42,43,85,15,61,55,32,80,37,67,29,0,17,50],[31,22,10,40,34,45,8,63,36,78,83,54,71,87,72,23,41,25,27,60,35,49,14,11,42,92,9,46,56,29,38,77],[51,23,47,14,24,12,42,70,9,87,18,83,95,46,78,71,55,86,48,94,79,31,100,49,89,8,11,25,33],[65,100,38,97,31,77],[51,87,50,10,33,13,82,77,4,9,56,35,78,31,93,84,54,92,38,59,34,36,48,80,95,61,85,28],[34,9,1,85,41,13,52,19,46,50,22,62,69,78,79,49,54,8,83,15],[74,37,86,66,35,31,46,9,36,62,88,57,61,25,65,70,52],[67,33,14,50,49,45,60,37,19,6,54,4,46,64,97,96,52,11,78,38,93,62,51,48,92,10,29,75,16,41,55,58,74],[50,53,65,0,9,82,87,27,75,12,28,86],[64,32,18,60,45,92,33,24,10,58,40,21,9,57,61,90,70,73,28,59],[10,36,48,21,93,64,49,52,46,88,15,87,51,72,95,45,41,76,28,23,98,35],[26,38,64,25,62,56,61,76,81,8,11,88,89,98,100,35,63,34,30,91,49,83,72,96,10,97,80,24,82,13,65],[53,94,2,12,60,52,5,40,23,26,28,34,93,63,85,41],[35,66,1,56,30],[],[61,24,89,44,54,21,11,6,60,20,98,99],[18,55,45,31,36,38,60,95,30,58,48,63,20,34,86,59,8,51,14,100,17,24,3,16,35,73,80,84,94,49,40],[88,13,3,49,58],[88,52,1,40,71,46,10,36,18,4,42,45,91,50,79,58,19,14,0],[],[29,8,33,63,48,50,11,80,49,86,36,54,88,74],[92,60,90,76,80,87,56,71,57,0,48,70,37,38,83],[17,44,13,89,20,75,69,94,66,12,59,62,36,74,6,14,53,2],[55,79,21,13,89,61,74,69,70,76,75,50,66,58,34,93,37,22,88,7,28,51],[73,68,90,84,31,32,22,77,63,85,24,100,3],[50,6,45,15,66,25,79,37,82,41,33],[76,99,26],[40,73,50,84,69,11,19,6,14,12,74,67,97,8,33,7,55,70,63,44,100,25,79,36,76,94,54,53,22,38],[33,49,77,50,56,65,62,81],[47,75,88,20,50,74,23,18,61,69,49,41,58,35,60,99,53,7,77,96],[80,64,14,13,37,33,25,17,38,26,73,4,1,35],[75,16,85,97,31,83,96,82,78,54,73,62,79,55,42,51,43,36,99,26,57,67,24,84,23,47,61,50,63,0,94,66,20],[41,91,23,8,90,27,32,31,64,89,44,97,59,88,11,94,100,78,48,67,84],[46,56,32,71,40,26,83,44,76,73,59,22,24],[39,20,99,12,30,91,89,84,34,45,74,70,100,31,54,75,81,98,35,85,55,4,24,36],[25],[9,16,44,94,82,41,4,39,21,5,73,87,58,91,59,34,47,48,27,78,97,95,96,62,68,69,51,84],[27,20,40,28,77],[30],[76,31,91,36,62,7,78,23,63,68,86,26,8,39,64,85,54,42,29,18,17,47],[53,99,51],[27,80,37,92,40,9,56,52,34,67,10,33,48,73,26,59,83,65,64,4,3,68,85,69,63],[11,57,87,89,21,74,17,61,51,80,26,70,39,9,36,75,63,85,100,18,15,96,90,47,84],[66,74,84,5,13,0,57,23,8],[95,43,8,27,85,96,47,53,48,3,41,86,32,70,12,15,82,6,62,81,4,97,40,13,23,24,59,26,98,71,35],[35,29,64,85,63,50,67,43,54,39,94,65,87],[86,90,70,100,72,76,48,37,80,34],[44,1,25,14,41,9,72,32,19,92,100,55,0,30,76,26,99,96,16,21,11,70,74,49,65,59,27,94,87,62,3],[72,28,41,81,58,84,8,39,51,100,54,71,70,36,94,47,65,97,32,85,30,68,87,26,75,95],[86,52,26,100,0,11,19,20,82,21,88,84,9,65],[71,30,18,43,50,76,87,19],[18,64,20,80,91,0,45,97,78,98,31,23,38,8,17,32,9,55,86,44,40,77,85,14,11,81,22,42,89,63,7,60,13],[37,58,12,75,31,33,25,11,26,88,53,91,93,85,52,81,10,43,51,20,35,45,3],[88,26,23,64,56,5,21,16,15,39],[88,37,85,2,61,100,24,93,23,78,46,54,36,74,84,47,58,77,28],[],[15,23,54,73,21,33,76,96,89,12,48,10,9,92,61,59,65,42,29,37,86,27,20],[76,93,3,37,27,65,20,34,11,99,98,28,67,5,13,80,42,64,61,43,79,23,29],[41,54,81,17,90,23,75,4,62,46,52,57],[20,52,8,58,87,48,6,89,93],[49,9,34,28,41,69,87,50,54,83,96,44,5,12,86,76,92,2,19,48,4,55,85,10,25,1,78,15,61,74]],

  [[],[],[41],[94],[],[63],[29],[46],[],[],[],[],[],[],[],[42,77],[],[],[],[],[64],[86],[],[8,15],[24],[],[100],[],[],[],[],[56],[],[84],[],[],[71],[],[23,83],[],[40],[],[],[20],[],[13,57],[51],[3,69],[],[68],[49],[],[28],[],[],[88],[],[52],[],[],[],[36],[14,55],[],[2],[95],[],[],[],[33],[],[93],[59],[],[74],[22],[47],[],[],[45],[35],[],[],[],[],[32],[],[1],[61],[],[],[],[44],[],[],[],[],[],[48],[],[85,96]],

  [0,4,5,6,7,9,10,11,12,16,17,18,19,21,25,26,27,30,31,34,37,38,39,43,50,53,54,58,60,62,65,66,67,70,72,73,75,76,78,79,80,81,82,87,89,90,91,92,97,98,99]
];

console.log(f(...args));