js解leetcode(80)-中等

1.节点与其祖先的最大差值

题目：

给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

思路：在低估时，不断更新最大值和最小值即可

时间复杂度O(n) 空间复杂度O(logn)

var maxAncestorDiff = function (root, min = root?.val, max = root.val) {
  if (!root) return 0;
  min = Math.min(min, root.val);
  max = Math.max(max, root.val);
  return Math.max(
    max - min,
    maxAncestorDiff(root.left, min, max),
    maxAncestorDiff(root.right, min, max)
  );
};

2.两地调度

题目：

公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为 costs[i][1]。

返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达。

思路：采用贪心的方式决定每个人去哪个地方。标准就是某个人去A和B的费用的绝对值。这个差值越大，说明这个人应该优先安排。

所以计算每个人前往两个地方的费用之差，然后按照差值的大小从大到小排序，类似两个栈，某个栈满了就只推入另一个栈

时间复杂度O(nlogn)，空间复杂度O(n)

/**
 * @param {number[][]} costs
 * @return {number}
 */
var twoCitySchedCost = function(costs) {
  const dis = costs.map((item, index) => index);
  dis.sort(
    (a, b) =>
      Math.abs(costs[b][0] - costs[b][1]) - Math.abs(costs[a][0] - costs[a][1])
  );
  let v1 = 0,
    v2 = 0;
  let c = 0;
  const l = costs.length;
  for (let i = 0; i < l; i++) {
    if (v1 < l / 2 && v2 < l / 2) {
      if (costs[dis[i]][0] < costs[dis[i]][1]) {
        c += costs[dis[i]][0];
        v1++;
      } else {
        c += costs[dis[i]][1];

        v2++;
      }
    } else if (v1 < l / 2) {
      c += costs[dis[i]][0];

      v1++;
    } else {
      c += costs[dis[i]][1];

      v2++;
    }
  }
  return c;
};

3.两个非重叠子数组的最大和

题目：

给出非负整数数组 A ，返回两个非重叠（连续）子数组中元素的最大和，子数组的长度分别为 L 和 M。（这里需要澄清的是，长为 L 的子数组可以出现在长为 M 的子数组之前或之后。）

从形式上看，返回最大的 V，而 V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) 并满足下列条件之一：

 

0 <= i < i + L - 1 < j < j + M - 1 < A.length, 或
0 <= j < j + M - 1 < i < i + L - 1 < A.length.
 

思路：最开始的思路，是缓存前缀和，然后双重遍历。

时间复杂度O(n2)，空间复杂度O(n)

/**
 * @param {number[]} A
 * @param {number} L
 * @param {number} M
 * @return {number}
 */
var maxSumTwoNoOverlap = function(A, L, M) {
  const l = A.length;
  const lList = new Array(l).fill(0);
  const mList = new Array(l).fill(0);
  const sumLeft = new Array(l).fill(0);
  sumLeft[0] = A[0];
  for (let i = 1; i < l; i++) {
    sumLeft[i] = sumLeft[i - 1] + A[i];
  }
  for (let i = 0; i + L - 1 < l; i++) {
    lList[i] = A[i] + sumLeft[i + L - 1] - sumLeft[i];
  }
  for (let i = 0; i + M - 1 < l; i++) {
    mList[i] = A[i] + sumLeft[i + M - 1] - sumLeft[i];
  }
  let max = 0;
  for (let i = 0; i + L + M - 1 < l; i++) {
    for (let j = i + L; j + M - 1 < l; j++) {
      max = Math.max(max, lList[i] + mList[j]);
    }
  }
  for (let i = 0; i + L + M - 1 < l; i++) {
    for (let j = i + M; j + L - 1 < l; j++) {
      max = Math.max(max, mList[i] + lList[j]);
    }
  }
  return max;
};

然后，可以优化一下时间。可以缓存对于下标i时，两个数组分别对应该下标的前缀最大和和后缀最大和

也就是对于每个下标i，leftL[i]表示i左侧的l数组的最大和，对应的就是rightL[i]是l在右侧时，的最大和。同理计算m的最大前缀和和后缀和

这样只需要枚举每一个i，计算以当前的i为M和L的分界时对应的和，然后取最大值

时间复杂度O(n)，空间复杂度O(n)

/**
 * @param {number[]} A
 * @param {number} L
 * @param {number} M
 * @return {number}
 */
var maxSumTwoNoOverlap = function(A, L, M) {
  const l = A.length;
  const lList = new Array(l).fill(0);
  const mList = new Array(l).fill(0);
  const sumLeft = new Array(l).fill(0);
  sumLeft[0] = A[0];
  for (let i = 1; i < l; i++) {
    sumLeft[i] = sumLeft[i - 1] + A[i];
  }
  for (let i = 0; i + L - 1 < l; i++) {
    lList[i] = A[i] + sumLeft[i + L - 1] - sumLeft[i];
  }
  for (let i = 0; i + M - 1 < l; i++) {
    mList[i] = A[i] + sumLeft[i + M - 1] - sumLeft[i];
  }
  let max = 0;
  const maxLKLeftList = new Array(l).fill(0);
  for (let i = L - 1; i + 1 <= l; i++) {
    maxLKLeftList[i] = Math.max(maxLKLeftList[i - 1] || 0, lList[i - L + 1]);
  }
  const maxMLeftList = new Array(l).fill(0);
  for (let i = M - 1; i + 1 <= l; i++) {
    maxMLeftList[i] = Math.max(maxMLeftList[i - 1] || 0, mList[i - M + 1]);
  }
  const maxLKRightList = new Array(l).fill(0);
  for (let i = l - L; i >= 0; i--) {
    maxLKRightList[i] = Math.max(maxLKRightList[i + 1] || 0, lList[i]);
  }
  const maxMRightList = new Array(l).fill(0);
  for (let i = l - M; i >= 0; i--) {
    maxMRightList[i] = Math.max(maxMRightList[i + 1] || 0, mList[i]);
  }
  for (let i = Math.min(L - 1, M - 1); i + L < l || i + M < l; i++) {
    max = Math.max(
      max,
      maxLKLeftList[i] + maxMRightList[i + 1],
      maxMLeftList[i] + maxLKRightList[i + 1]
    );
  }
  return max;
};

4.边框着色

题目：

给出一个二维整数网格 grid，网格中的每个值表示该位置处的网格块的颜色。

只有当两个网格块的颜色相同，而且在四个方向中任意一个方向上相邻时，它们属于同一连通分量。

连通分量的边界是指连通分量中的所有与不在分量中的正方形相邻（四个方向上）的所有正方形，或者在网格的边界上（第一行/列或最后一行/列）的所有正方形。

给出位于 (r0, c0) 的网格块和颜色 color，使用指定颜色 color 为所给网格块的连通分量的边界进行着色，并返回最终的网格 grid 。

思路：初看，是一个典型的dfs，不过题目要求只修改边界的颜色，所以重点就是如何判断某个点是不是边界。

我的想法是，第一次dfs不修改矩阵中的值，但是记录边界的点的坐标。所以这时需要用set记录遍历过的点。然后dfs的函数返回该店是否是连通分量，通过四个方向的dfs的返回值，就可以知道当前点是否是边界。

是边界的话，就把当前点推入数组。在dfs完成之后，遍历数组，将颜色修改

时间复杂度O(mn)，空间复杂度O(mn)

/**
 * @param {number[][]} grid
 * @param {number} r0
 * @param {number} c0
 * @param {number} color
 * @return {number[][]}
 */
var colorBorder = function(grid, r0, c0, color) {
  const h = grid.length;
  const w = grid[0].length;
  if (grid[r0][c0] === color) return grid;
  const init = grid[r0][c0];
  const points = [];
  const set = new Set();
  const dfs = (i, j) => {
    if (i < 0 || i >= h) return 0;
    if (j < 0 || j >= w) return 0;
    if (set.has(`${i}-${j}`)) return 1;
    if (grid[i][j] !== init) return 0;
    set.add(`${i}-${j}`);
    const count = dfs(i, j + 1) + dfs(i, j - 1) + dfs(i + 1, j) + dfs(i - 1, j);
    if (count < 4) {
      points.push([i, j]);
    }
    return 1;
  };
  dfs(r0, c0);
  points.forEach((item) => {
    grid[item[0]][item[1]] = color;
  });
  return grid;
};

5.不相交的线

题目：

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。

以这种方法绘制线条，并返回我们可以绘制的最大连线数。

思路：和两个字符串的最长公共子序列是一样的，动态规划即可

dp[i][j]表示A中前i个字符和B中前j个字符的连线数量。

时间复杂度O(mn)，空间复杂度O(mn)

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number}
 */
var maxUncrossedLines = function(A, B) {
  const l1 = A.length;
  const l2 = B.length;
  const dp = new Array(l1 + 1).fill("").map(() => new Array(l2 + 1).fill(0));
  for (let i = 1; i <= l1; i++) {
    for (let j = 1; j <= l2; j++) {
      if (A[i - 1] === B[j - 1]) {
        dp[i][j] = Math.max(dp[i - 1][j - 1] + 1, dp[i][j]);
      } else {
        dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
      }
    }
  }
  return dp[l1][l2];
};

压缩一下

时间复杂度O(mn)，空间复杂度O(m)

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number}
 */
var maxUncrossedLines = function(A, B) {
  const l1 = A.length;
  const l2 = B.length;
  const dp1 = new Array(l2 + 1).fill(0);
  const dp2 = new Array(l2 + 1).fill(0);
  for (let i = 1; i <= l1; i++) {
    for (let j = 1; j <= l2; j++) {
      if (A[i - 1] === B[j - 1]) {
        dp2[j] = dp1[j - 1] + 1;
      } else {
        dp2[j] = Math.max(dp2[j - 1], dp1[j]);
      }
    }
    for (let j = 1; j <= l2; j++) {
      dp1[j] = dp2[j];
      dp2[j] = 0;
    }
  }
  return dp1[l2];
};