岛屿数量、求根节点到叶节点数字之和、二分查找

岛屿数量

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

思路：用 dfs，每查找到一个 1 就把与其相连的 1 全部淹了（变成 0），避免维护 visited 数组

tsCopy
function numIslands(grid: string[][]): number {
  let count = 0;

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === "1") {
        count++;
        dfs(grid, i, j);
      }
    }
  }

  return count;
}

const dfs = (grid, i, j) => {
  if (
    i < 0 ||
    i >= grid.length ||
    j < 0 ||
    j >= grid[0].length ||
    grid[i][j] === "0"
  ) {
    return;
  }

  grid[i][j] = "0";
  dfs(grid, i + 1, j);
  dfs(grid, i - 1, j);
  dfs(grid, i, j - 1);
  dfs(grid, i, j + 1);
};

求根节点到叶子节点数字之和

给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字。例如：从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的所有数字之和。

示例：

输入：root = [1,2,3]

输出：25

解释：

从根到叶子节点路径 1 -> 2 代表数字 12

从根到叶子节点路径 1 -> 3 代表数字 13

因此，数字总和 = 12 + 13 = 25

思路：因为每个递归调用返回的就是当前子树所有路径的和，所以我们可以直接把左右子树的结果相加，而不需要等所有路径都递归到根节点再处理。

注意递归过程中要带上 currentSum

tsCopy
function sumNumbers(root: TreeNode | null): number {
  function dfs(node: TreeNode | null, currentSum: number): number {
    if (!node) {
      return 0;
    }

    const newSum = currentSum * 10 + node.val;

    // 遇到叶子节点，返回当前数值
    if (!node.left && !node.right) {
      return newSum;
    }
    return dfs(node.left, newSum) + dfs(node.right, newSum); // 递归计算左右子树的总和
  }

  return dfs(root, 0);
}

二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target

写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

注意：

1. target > nums[mid] 时改动的是 lo 而非 hi，因为此时说明目标数字更大，区间应该右移

2. 注意移动时是 lo = mid + 1 和 hi = mid - 1，不要把加减 1 忘记了

tsCopy
function search(nums: number[], target: number): number {
  let lo = 0,
    hi = nums.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((hi - lo) / 2) + lo;
    if (target === nums[mid]) {
      return mid;
    }
    if (target > nums[mid]) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }

  return -1;
}