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

复原 IP 地址

题目描述

示例：

输入：s = "25525511135"

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

思路

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 = 3

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

思路

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