时间戳

首页 > 解决方案 > 使用辅助函数时未传递 Javascript 值

javascript - 使用辅助函数时未传递 Javascript 值

问题描述


var islandPerimeter = function(grid) {
   let perimeter = 0;

   const dfs = (grid, i, j, perimeter) => {
       grid[i][j] = 2;
       if( i === 0 || grid[i-1][j] === 0) perimeter++;
       if(i === grid.length - 1 || grid[i+1][j] === 0) perimeter++;
       if( j === 0 || grid[i][j-1] === 0) perimeter++;
       if(j === grid[0].length - 1 || grid[i][j+1] === 0) perimeter++;    
       
       if(i > 0 && grid[i-1][j] === 1) dfs(grid, i-1, j, perimeter);
       if(i < grid.length-1 && grid[i+1][j] === 1) dfs(grid, i+1, j, perimeter);
       if(j > 0 && grid[i][j-1] ===1) dfs(grid, i, j-1, perimeter);
       if(j < grid[0].length-1 && grid[i][j+1] === 1) dfs(grid, i, j+1, perimeter); 
       
   }
   
   let r = grid.length;
   let c = grid[0].length;
   
   for(let i = 0; i < r; i++) {
       for(let j = 0; j < c; j++) {
           if(grid[i][j] === 1) {
               dfs(grid, i, j, perimeter);
           }
       }
       return perimeter;
   }
};


const ans = islandPerimeter([
 [0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]
])

我使用 dfs 找到了一个 C++ 答案并转换为 javascript ......但它不会引用周长值，因此返回 0；

如何修复它并供将来参考使用辅助函数时如何返回值。

另外，我的另一个问题是..

在这个问题中，我们通过循环找到第一个岛，然后我们对其余的岛进行 dfs。这是否意味着在一个 dfs 循环中回答了周边，或者 for 循环会再次运行...... ty

标签： javascriptfor-looprecursionreference

解决方案

如评论中所述，将解决问题的代码的最小更改是删除perimeter为 a parameterto dfs。

但我想提出一些改进建议。需要几步才能到达我们想去的地方。

不要修改输入数据

第一个更改是在处理网格时不修改网格。使用不可变数据有各种充分的理由，尤其是跨函数边界。但当然，这个算法本质上是关于修改网格以跟踪您已经访问过的地方。所以我只需将原始调用中的数据副本dfs传递给函数：

dfs (grid .map (row => row .slice (0)), i, j)

通过调用map网格，我们得到一个新的外部数组，其中包含对每一行的回调结果。通过调用.slice (0)每一行，我们得到原始行的副本。这共同为我们提供了一个与原始数据相同的新网格。（请注意，这仍然是一个相对较浅的副本；如果网格元素是对象而不是数字，它们将通过引用共享。）

使用return而不是修改更高范围的变量

接下来，dfs是在更高范围内修改一个值，即perimeter. 这使得难以理解该功能。相反，如果它返回该值，我们可以以更易于理解的方式将这些位收集在一起。所以我们可以写

  const dfs = (grid, i, j) => {
    grid[i][j] = 2;
    return ((i === 0 || grid[i - 1][j] === 0) ? 1 : 0) +
           ((i === grid.length - 1 || grid[i + 1][j] === 0) ? 1 : 0) +
           ((j === 0 || grid[i][j - 1] === 0) ? 1 : 0) +
           ((j === grid[0].length - 1 || grid[i][j + 1] === 0) ? 1 : 0) +

           ((i > 0 && grid[i - 1][j] === 1) ? dfs(grid, i - 1, j) : 0) +
           ((i < grid.length - 1 && grid[i + 1][j] === 1) ? dfs(grid, i + 1, j) : 0) +
           ((j > 0 && grid[i][j - 1] === 1) ? dfs(grid, i, j - 1) : 0) +
           ((j < grid[0].length - 1 && grid[i][j + 1] === 1) ? dfs(grid, i, j + 1) : 0);
  }

我们进行与以前相同的计算，但不是将结果添加到现有的外部范围变量中，而是将它们加在一起并返回它们。这意味着我们可以perimeter完全删除变量并简单地将外部调用的结果返回到dfs：

           if(grid[i][j] === 1) {
               return dfs(grid, i, j, perimeter);
           }

计算辅助变量而不是从循环中返回

但是我发现从不完整的循环返回的结果for非常不令人满意。我宁愿计算包含第一个的行和列1，然后简单地return使用它们。所以我可能会写这样的东西：

  const r = grid .findIndex ((row) => row .includes (1));
  const c = grid[r] .findIndex ((col) => col == 1);
  
  return dfs (grid .map (row => row .slice (0)), r, c)

优雅地处理不正确的数据

这里有一个可能的故障点。如果网格中没有1s，则此代码可能会出错。我们可以通过对这些值进行一些初始检查来避免这种情况，如下所示：

  const r = grid .findIndex ((row) => row .includes (1));
  const c = r > -1 ? grid[r] .findIndex ((col) => col == 1) : -1;
  
  return (r > -1 && c > -1) ? dfs (grid .map (row => row .slice (0)), r, c) : 0

如果我们没有找到带有 a 的行1，那么r将会是-1，并且我们也设置c为-1。然后，如果其中任何一个不大于-1我们 return 0，则在另一种情况下照常进行。

将内部函数移出

但是现在我们可以注意到，dfs它只依赖于它的参数。它是一个纯函数，不再需要嵌入到 main 函数中。根据您将函数打包在一起的方式，您可能仍希望将其保留在那里。但是，如果您使用的是模块，那么这可能只是一个模块私有函数。我们会在这里这样做。

把它放在一起

那么，我们到达了这个版本：

const dfs = (grid, i, j) => {
  grid[i][j] = 2;
  return ((i === 0 || grid[i - 1][j] === 0) ? 1 : 0) +
         ((i === grid.length - 1 || grid[i + 1][j] === 0) ? 1 : 0) +
         ((j === 0 || grid[i][j - 1] === 0) ? 1 : 0) +
         ((j === grid[0].length - 1 || grid[i][j + 1] === 0) ? 1 : 0) +

         ((i > 0 && grid[i - 1][j] === 1) ? dfs(grid, i - 1, j) : 0) +
         ((i < grid.length - 1 && grid[i + 1][j] === 1) ? dfs(grid, i + 1, j) : 0) +
         ((j > 0 && grid[i][j - 1] === 1) ? dfs(grid, i, j - 1) : 0) +
         ((j < grid[0].length - 1 && grid[i][j + 1] === 1) ? dfs(grid, i, j + 1) : 0);
}

const islandPerimeter = (grid) => {
  let r = grid .findIndex ((row) => row .includes (1));
  let c = r > -1 ? grid[r] .findIndex ((col) => col == 1) : -1;
  
  return (r > -1 && c > -1) ? dfs (grid .map (row => row .slice (0)), r, c) : 0
};

const grid = [
  [0, 1, 0, 0],
  [1, 1, 1, 0],
  [0, 1, 0, 0],
  [1, 1, 0, 0]
]

console .log (islandPerimeter (grid))
console .log (grid.map(r => r.join(' ')).join('\n'))

（我们执行第二个console.log语句是为了证明我们的函数没有修改初始网格。）

更纯粹的功能

函数式编程有许多原则，但其中两个核心原则是始终使用不可变数据并仅使用纯函数。我们可以注意到这dfs两者都被打破了。它会改变grid传递给它的参数，并依赖于该网格的早期突变才能正常运行。

这里有一个严肃的哲学问题：如果在函数中修改了数据结构并且没有代码可以观察它，它会产生副作用吗？我可能会保留该函数，因为除了函数内部之外，唯一被修改的东西在任何地方都不可见。但一些纯粹主义者可能不同意。这是我们可以满足他们的一种方式

我们可以编写一个快速帮助函数，创建一个网格的克隆，其中一个坐标更新为2，或更一般地，更新为输入值。这是一个版本：

const setCoord = (grid, x, y, val) => 
  grid .map ((row, r) => r == x ? row.map((col, c) => c == y ? val : col) : row.slice(0))

同样，我们有一个原始的稍微浅的克隆，但值(x, y)更新为val. 我们可以使用它dfs来避免通过将这种克隆传递给递归调用来修改我们的网格：

const dfs = (grid, i, j, newGrid = setCoord(grid, i, j, 2)) => 
  ((i === 0 || grid[i - 1][j] === 0) ? 1 : 0) +
  ((i === grid.length - 1 || grid[i + 1][j] === 0) ? 1 : 0) +
  ((j === 0 || grid[i][j - 1] === 0) ? 1 : 0) +
  ((j === grid[0].length - 1 || grid[i][j + 1] === 0) ? 1 : 0) +

  ((i > 0 && grid[i - 1][j] === 1) ? dfs(newGrid, i - 1, j) : 0) +
  ((i < grid.length - 1 && grid[i + 1][j] === 1) ? dfs(newGrid, i + 1, j) : 0) +
  ((j > 0 && grid[i][j - 1] === 1) ? dfs(newGrid, i, j - 1) : 0) +
  ((j < grid[0].length - 1 && grid[i][j + 1] === 1) ? dfs(newGrid, i, j + 1) : 0);

在这里以完全纯粹的方式工作有一种很好的感觉。如果我们想了解它，我们还可以避免在 main 函数中的赋值语句，r然后c我们甚至可以满足 Haskellers。

但是这里有个性能劣势就是JS。以前的版本对网格进行了一次克隆；它这样做是为了不修改输入结构的合法目的。在这里，我们需要为我们岛上的每个街区复制整个网格。对于具有大网格的大岛，这可能会占用大量内存，并且肯定会降低处理速度。我们可以使用更好的数据结构来减少这些问题，但我们无法消除它们。正如我们的哲学家指出的那样，无论如何，没有人会观察到我们正在做的突变。所以我很可能会坚持使用以前的版本。但值得一看的是，我们甚至可以在 Javascript 中进一步实现这一点。

更简单的算法

我们还可以更改使用的算法。我们一直在使用的算法找到一个岛屿的周长，这个岛屿恰好是所有岛屿最北的岛屿中最西的一个。换句话说，它在网格中的岛屿中找到一个相当随机的岛屿的周长。

这通常被网格中只有（或最多）一个岛的假设所扫除。但如果是这种情况，那么另一种算法使用起来更简单：我们计算网格中所有岛屿的总周长。如果只有一个，那么我们就有答案了！

这可以通过这个更简单的代码来实现：

const blockPerimeter = (grid, r, c) => 
  ((r == 0 || grid [r - 1] [c] == 0) ? 1 : 0) +                    // top
  ((c == 0 || grid [r] [c + 1] == 0) ? 1 : 0) +                    // right
  ((r == grid .length - 1 || grid [r + 1] [c] == 0) ? 1 : 0) +     // bottom
  ((c == grid [r] .length - 1 || grid [r] [c - 1] == 0) ? 1 : 0)   // left

const islandPerimeter = (grid) => 
  grid .reduce (
    (p, r, i) => r .reduce (
      (p, c, j) => p + (c == 1 ? blockPerimeter (grid, i, j) : 0), 
      p
    ), 
    0
  )

在这里，我们只是1在网格中找到每一个，并通过检查其北部、东部、南部和西部的邻居来计算其对周长的贡献。如果它们为零（或者如果我们已经脱离了网格），我们将在总数中加一。

而已。这就是整个算法。

这绝对比上面的简单，如果你知道只有一个岛，这是一个有用的技术。但是上面的计算和标记技术可以以这种方式无法扩展。通过捕获第一个找到的结果和下一个等的结果，可以很容易地扩展找到网格中每个岛屿的周长，直到没有' 剩余。没有明显的方法可以扩展这个算法来做到这一点。111

笔记

blockPerimeter我们可以通过将整个网格包裹在 s 的外壳中来简化核心功能0。虽然这会留下一个更好的版本，例如

const blockPerimeter = (grid, r, c) => 
  (grid [r - 1] [c] == 0 ? 1 : 0) + // top
  (grid [r] [c + 1] == 0 ? 1 : 0) + // right
  (grid [r + 1] [c] == 0 ? 1 : 0) + // bottom
  (grid [r] [c - 1] == 0 ? 1 : 0)   // left

甚至允许我们? 1 : 0由于添加导致的类型强制而删除子句（我不建议这样做！），我认为包装数组所需的额外基础设施会使整个过程更加复杂，不值得时间。

推荐阅读