js解leetcode(81)-中等

1.多边形三角剖分的最低得分

题目：

给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。

假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。

返回多边形进行三角剖分后可以得到的最低分。

思路：动态规划，可让dp[i][j]为第i个点到第j个点的三角形剖分的和，所以有

dp[i][j] = max(dp[i][j], nums[i] * nums[j] * nums[k] + dp[i][k] + dp[k][j])，其中k为i和j中的一点

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

/**
 * @param {number[]} values
 * @return {number}
 */
var minScoreTriangulation = function(nums) {
  const n = nums.length;
  const dp = new Array(n).fill("").map(() => new Array(n).fill(Infinity));

  for (let i = 0; i < n - 1; i++) {
    dp[i][i + 1] = 0;
  }

  for (let d = 2; d < n; d++) {
    for (let l = 0; l < n - d; l++) {
      const r = l + d;
      for (let i = l + 1; i < r; i++) {
        dp[l][r] = Math.min(
          dp[l][r],
          nums[i] * nums[l] * nums[r] + dp[l][i] + dp[i][r]
        );
      }
    }
  }
  return dp[0][n - 1];
};

2.移动石子直到连续II

题目 :

在一个长度 无限 的数轴上，第 i 颗石子的位置为 stones[i]。如果一颗石子的位置最小/最大，那么该石子被称作 端点石子 。

每个回合，你可以将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。

值得注意的是，如果石子像 stones = [1,2,5] 这样，你将 无法 移动位于位置 5 的端点石子，因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。

当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。

要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves] 。

思路：

第一个石头移到第二个石头的后面的第一个空位上 重复执行以上操作 直到所有石头连在一起
移动的位数 就等于第一个石头到最后一个石头之间的空位数
还有一种可能就是从右到左 倒数第一个石头移到倒数第二个石头的前面的第一个空位上
最小值
一个长度为n的滑动窗口 用来表示石头的最终位置
为了尽可能少的移动 则滑动窗口在初始时应该尽可能多的放石头
因此第一个石头必须在滑动窗口的第一个位置
然后找到滑动窗口的空位 就知道了移动的步数
有一种特殊情况 就是在滑动窗口初始化时出现连续n-1个石头 但不是连续n个石头时
不需要计算 因为这个滑动窗口无法被填满 最优解不会是以这个石头为起点

/**
 * @param {number[]} stones
 * @return {number[]}
 */
var numMovesStonesII = function(stones) {
  stones.sort((a, b) => a - b);
  const len = stones.length;
  let min = len - 1;
  for (let i = 0; i <= len - 1; ++i) {
    let tempI = i + 1;
    while (tempI <= len - 1 && stones[tempI] - stones[i] <= len - 1) {
      ++tempI;
    }
    if (
      tempI - 1 - i === len - 2 &&
      stones[tempI - 1] - stones[i] === len - 2
    ) {
      continue;
    }
    min = Math.min(min, len + i - tempI);
    if (tempI === len - 1) {
      break;
    }
  }
  return [
    min,
    Math.max(stones[len - 1] - stones[1], stones[len - 2] - stones[0]) +
      2 -
      len,
  ];
};

3.把二叉搜索树转换为累加树

题目：

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。

思路：每个节点要加上比自己大的节点的值，又是二叉搜索树，所以先右再根再左的遍历顺序，记录之前的节点的值即可

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var bstToGst = function(root) {
  let v = 0;
  const dfs = (root) => {
    if (!root) return;
    dfs(root.right);
    const val = root.val;
    root.val += v;
    v += val;
    dfs(root.left);
  };
  dfs(root);
  return root;
};

4.最大层内元素和

给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。

请你找出层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。

思路：层序遍历，记录和即可

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxLevelSum = function(root) {
  const res = [-Infinity];
  const dfs = (root, level = 1) => {
    if (!root) return;
    res[level] = (res[level] || 0) + root.val;
    dfs(root.left, level + 1);
    dfs(root.right, level + 1);
  };
  dfs(root);
  let max = res[0];
  let index = 0;
  for (let i = 1; i < res.length; i++) {
    if (res[i] > max) {
      max = res[i];
      index = i;
    }
  }
  return index;
};

5.地图分析

题目：

你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

如果网格上只有陆地或者海洋，请返回 -1。

思路：BFS。从陆地开始，记录所有点的坐标，每一步往外扩张1个单位，记录下一层坐标，直到把所有点遍历完。步数 - 1就是最大距离

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

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxDistance = function(grid) {
  const position = [];
  const n = grid.length;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        position.push([i, j]);
        grid[i][j] = -1;
      }
    }
  }
  const len = position.length;
  if (len === n * n || !len) return -1;
  let dis = 0;
  const handle = (i, j) => {
    if (i < 0 || i >= n) return;
    if (j < 0 || j >= n) return;
    if (grid[i][j] !== 0) return;
    position.push([i, j]);
    grid[i][j] = -1;
  };
  while (position.length) {
    const l = position.length;
    for (let i = 0; i < l; i++) {
      const [j, k] = position.shift();
      handle(j, k + 1);
      handle(j, k - 1);
      handle(j + 1, k);
      handle(j - 1, k);
    }
    dis++;
  }
  return dis - 1;
};