复原 IP 地址、括号生成、二叉树的最大深度

复原 IP 地址

题目描述

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。 给定一个只包含数字的字符串 s，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

示例：

输入：s = "25525511135"

输出：["255.255.11.135","255.255.111.35"]

思路

用回溯。工具函数的入参是此次的起始字符下标 start、当前已添加的路径 path、已有的段数 segment

找到答案的条件是 segment === 4 && start === s.length

在前面的回溯里，因为一个片段的长度就是 1-3，需要遍历 len = 1 -> len = 3 来试验能不能组成合法的路径

判断是否合法：

1. s[0] !== '0'（因为 011 不合法，001 可以通过 s[0] !== '0' 捕获到，而 100 是合法的，所以只要判断 s[0]）

2. 把 s 转换成 number 类型后，值在 0-255 的区间

tsCopy
function restoreIpAddresses(s: string): string[] {
  const result: string[] = [];

  function backtrack(start: number, path: string[], segment: number): void {
    if (segment === 4 && start === s.length) {
      // 成功分成4段且用完所有字符
      result.push(path.join("."));
      return;
    }

    if (segment === 4 || start === s.length) return; // 剪枝：分割次数超限或提前用完字符

    for (let len = 1; len <= 3; len++) {
      // 每次尝试切 1 到 3 个字符
      if (start + len > s.length) break;

      const part = s.substring(start, start + len);
      if (isValid(part)) {
        // 只有当 part 是合法 IP 段时，才继续递归
        path.push(part);
        backtrack(start + len, path, segment + 1);
        path.pop(); // 回溯
      }
    }
  }

  function isValid(segment: string): boolean {
    if (segment.length > 1 && segment[0] === "0") return false; // 不能有前导0
    const num = Number(segment);
    return num >= 0 && num <= 255;
  }

  backtrack(0, [], 0);
  return result;
}

括号生成

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例：

输入：n = 3

输出：["((()))","(()())","(())()","()(())","()()()"]

思路

工具函数入参为：剩余可用左括号数量 left、剩余可用左括号数量 right、记录路径的 track

得到答案的条件：left === 0 && right === 0

终止返回条件：left > right（left 不能剩得比 right 多），以及 left < 0 || right < 0

然后依次往 res 加入又 pop 出左括号和右括号，各自回溯

tsCopy
var generateParenthesis = function (n) {
  if (n === 0) return [];
  // 记录所有合法的括号组合
  let res = [];
  // 回溯过程中的路径
  let track = [];
  // 可用的左括号和右括号数量初始化为 n
  backtrack(n, n, track, res);
  return res;
};

// 可用的左括号数量为 left 个，可用的右括号数量为 right 个
var backtrack = function (left, right, track, res) {
  // 若左括号剩下的多，说明不合法
  if (right < left) return;
  // 数量小于 0 肯定是不合法的
  if (left < 0 || right < 0) return;
  // 当所有括号都恰好用完时，得到一个合法的括号组合
  if (left === 0 && right === 0) {
    res.push(track.join(""));
    return;
  }

  // 尝试放一个左括号
  // 选择
  track.push("(");
  backtrack(left - 1, right, track, res);
  // 撤消选择
  track.pop();

  // 尝试放一个右括号
  // 选择
  track.push(")");
  backtrack(left, right - 1, track, res);
  // 撤消选择
  track.pop();
};

思路：

tsCopy
undefined