合并区间 && 不同路径

• 合并区间 && 不同路径
  • 合并区间
  • 不同路径 今天两道题有点简单了（难道我变强了？ 无所谓，明天我会接受高德的拷打

合并区间

这题将数组按左端点大小排序后，主要就是考虑分类了（数形结合，相邻两个数组关系可以分为：

1. 完全分开
   l1--r1---l2----r2
2. 部分重叠
   l1--l2---r1----r2
3. 完全包含
   l1--l2---r2----r1

但其实 2 和 3 状况只要保存右边最大的边就行, 代码实现如下： (顺便由于最近有点忙，然后前两次笔试每次 ts/js 写不出来就掏 Python，所以这段时间限定 ts 写)

function merge(intervals: number[][]): number[][] {
  // 按照数组左端点进行排序
  intervals.sort((a, b) => a[0] - b[0]);
  let res: number[][] = [];
  for (let i = 0; i < intervals.length; i++) {
    let left = intervals[i][0];
    let right = intervals[i][1];
    //情况1：l1--r1---l2----r2
    if (res.length === 0 || res[res.length - 1][1] < left) {
      res.push([left, right]);
    }
    // 如果有重叠，合并区间
    //  情况2：l1--l2---r1----r2
    //  情况3：l1--l2---r2----r1
    if (left <= res[res.length - 1][1]) {
      res[res.length - 1][1] = Math.max(res[res.length - 1][1], right);
    }
  }
  return res;
}

不同路径

这题开始想使用递归，不断寻找每个方块的右方和下方是否为终点，但这样时间复杂度疯狂加大，导致超时

• 失败代码：

  let res = 0;
  function findPath(x: number, y: number): void {
    if (x === m - 1 && y === n - 1) {
      res++;
      return;
    } else {
      //同时寻找向下与向右的路径
      //递归过多，会超时
      if (x < m - 1) {
        findPath(x + 1, y);
      }
      if (y < n - 1) {
        findPath(x, y + 1);
      }
    }
  }
  findPath(0, 0);
  return res;

后面使用动态规划的思想，每个方块到达的路径，取决于它上方和左方有多少路径可以到达，而第一行和第一列只有一种方法可以到达 代码如下：

  const dp: number[][] = Array(m)
    .fill(0)
    .map(() => Array(n).fill(0));
  // 第一行和第一列的所有点只有一条路径可以到达
  for (let i = 0; i < m; i++) dp[i][0] = 1;
  for (let j = 0; j < n; j++) dp[0][j] = 1;
  // 逐行填充 dp 数组
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  // 返回从左上角到右下角的唯一路径数量
  return dp[m - 1][n - 1];