岛屿数量(二维数组)

  1. 输入：[
  2.       [1,1,0,0,0],
  3.       [0,1,0,1,1],
  4.       [0,0,0,1,1],
  5.       [0,0,0,0,0],
  6.       [0,0,1,1,1]
  7.      ]
  9. 输出：3
  1. 解题思路：当遍历到元素值为1时，需复位为0；然后再深搜相邻元素，复位为0
  3. function solve( grid ) {
  4.     // write code here
  5.     let res=0;
  6.     // dfs把相邻的1复位成0
  7.     const dfs = (arr,x,y) => {
  8.         if(arr[x][y]==0) return
  9.         arr[x][y] = 0
  10.         // dfs相邻元素
  11.         if(x-1>=0) dfs(arr,x-1,y)
  12.         if(y-1>=0) dfs(arr,x,y-1)
  13.         if(x+1 < arr.length) dfs(arr,x+1,y)
  14.         if(y+1 < arr[x].length) dfs(arr,x,y+1)
  16.     }
  17.     for(let i=0;i < grid.length;i++) {
  18.         for(let j=0;j < grid[i].length;j++) {
  19.             if(grid[i][j]==1) {
  20.                 res++;
  21.                 dfs(grid,i,j)
  22.             }
  23.         }
  24.     }
  25.     return res
  26. }

矩阵最长递增路径(*)

  1. 输入：[
  2.       [3,4,5],
  3.       [3,2,6],
  4.       [2,2,1]
  5.      ]
  7. 输出：4
  9. 说明：最长递增路径是【3，4，5，6]。注意不允许在对角线方向上
  10. 移动。
function solve( matrix ) {
  // 获取举证行n 列m
  const [n, m] = [matrix.length, matrix[0].length];
  const dp = new Array(n).fill(0).map(() => new Array(m).fill(0));
  const dir = [[0, 1], [0, -1], [-1, 0], [1, 0]];

  const dfs = (i, j, lastNum) => {
      // 当数组元素越界时 返回0
      // 直接过滤小于缓存路径的元素，避免运行超时
      if(i < 0 || j < 0 || i >= n || j >= m || matrix[i][j] <= lastNum) return 0;
      // 直接输出最大值
      if(dp[i][j]) return dp[i][j];  
      let pathLen = 0;
      // 寻找四个方向的最大值
      for (const [x, y] of dir) { 
          const [curx, cury] = [i + x, j + y];
          const temp = dfs(curx, cury, matrix[i][j]) + 1;
          if (temp > pathLen) {
              pathLen = temp;
          }
      }
      // 缓存最大值
      dp[i][j] = pathLen;
      return dp[i][j];
  }

  let maxLen = 0;
  for(let i = 0; i < m; i++) {
      for(let j = 0; j < n; j++) {
          // lastNum=-1，防止矩阵元素中存在0
          maxLen = Math.max(maxLen, dfs(i, j ,-1))
      }
  }
  return maxLen;
}