登录
转载

leetcode-戳气球

发布于 2025-01-14 阅读 53
  • GitHub
  • LeetCode
转载

戳气球

二 题目

有 n 个气球,编号为 0 到 n-1,
每个气球上都标有一个数字,
这些数字存在数组 nums 中。

现在要求你戳破所有的气球。
如果你戳破气球 i ,就可以获得 nums[left] * nums[i] * nums[right] 个硬币。

这里的 left 和 right 代表和 i 相邻的两个气球的序号。
注意当你戳破了气球 i 后,
气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

说明:

你可以假设 nums[-1] = nums[n] = 1,
但注意它们不是真实存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例:
输入: [3,1,5,8]
输出: 167 
解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
     coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/burst-balloons
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function(nums) {

};

根据上面的已知函数,小伙伴们可以先尝试破解本题,确定了自己的答案后再看下面代码。

三 解题思路

拿到题目,大脑开始运转:

// 思考:
// 如果数组长度大于 2,那就戳中间最小的数字。
// 例如:
// [3, 1, 5, 8] 戳 1(注意这里的中间是指 1, 5)
// [3, 5, 8] 戳 5 (注意这里的中间是指 5)
// 如果数组长度等于 2,那就先戳最小的,再戳最大的
// [3, 8] 先戳 3(1 * 3 * 8),再戳 8(1 * 8 * 1)
/**
 * @param {number[]} nums
 * @return {number}
 */
const maxCoins = (nums) => {
  const length = nums.length;
  // 如果没有
  if (!length) {
    return 0;
  }
  // 如果剩 1 个
  if (length === 1) {
    return 1 * nums[0] * 1;
  }
  // 如果剩 2 个
  if (length === 2) {
    if (nums[0] < nums[1]) {
      return (1 * nums[0] * nums[1]) + (1 * nums[1] * 1);
    } else {
      return (nums[0] * nums[1] * 1) + (1 * nums[0] * 1);
    }
  }
  // 如果剩 2 个以上
  const minIndex = 0, min = 101; // 注意界限,气球的个数范围是 [0, 500],气球的数字范围是 [0, 100]
  // 我们要戳的范围不包含 0 以及 length - 1,即范围:[1, length - 2]
  for (let i = 1; i < length - 1; i++) {
    if (nums[i] < min) {
      min = nums[i];
      minIndex = i;
    }
  }
  return nums[minIndex - 1] * nums[minIndex] * nums[minIndex + 1];
};

console.log(maxCoins(
  [3, 1, 5, 8],
));

这时候我们写了一遍基础的,即每次应该戳破的是哪个气球。

然后我们要做的,就是将其他累加起来,得到最终答案:

// 思考:
// 如果数组长度大于 2,那就戳中间最小的数字。
// 例如:
// [3, 1, 5, 8] 戳 1(注意这里的中间是指 1, 5)
// [3, 5, 8] 戳 5 (注意这里的中间是指 5)
// 如果数组长度等于 2,那就先戳最小的,再戳最大的
// [3, 8] 先戳 3(1 * 3 * 8),再戳 8(1 * 8 * 1)
/**
 * @param {number[]} nums
 * @return {number}
 */
const maxCoins = (nums) => {
  let sum = 0;
  const ergodic = (nums) => {
    const length = nums.length;
    console.log('------');
    console.log(sum);
    console.log(nums);
    // 如果没有
    if (!length) {
      return;
    }
    // 如果剩 1 个
    if (length === 1) {
      sum += (1 * nums[0] * 1); 
      return;
    }
    // 如果剩 2 个
    if (length === 2) {
      if (nums[0] < nums[1]) {
        sum += (1 * nums[0] * nums[1]) + (1 * nums[1] * 1);
        return;
      } else {
        sum += (nums[0] * nums[1] * 1) + (1 * nums[0] * 1);
        return;
      }
    }
    // 如果剩 2 个以上
    // 注意界限,气球的个数范围是 [0, 500],气球的数字范围是 [0, 100]
    let minIndex = 0, min = 101;
    // 我们要戳的范围不包含 0 以及 length - 1,即范围:[1, length - 2]
    for (let i = 1; i < length - 1; i++) {
      if (nums[i] < min) {
        min = nums[i];
        minIndex = i;
      }
    }
    sum += (nums[minIndex - 1] * nums[minIndex] * nums[minIndex + 1]);
    // 戳破这一个气球
    nums.splice(minIndex, 1);
    // 将剩下的带进去
    ergodic(nums);
  };

  ergodic(nums);

  return sum;
};

// console.log(maxCoins(
//   [3, 1, 5, 8],
// )); // 167

console.log(maxCoins(
  [9,76,64,21,97,60],
)); // 1086136

提交之后,我们发现在 “14 / 70 个通过测试用例” 中:

  • 已知:[9,76,64,21,97,60]
  • 解出:721504
  • 实际答案:1086136

这么说我们的思路有问题了。

仔细研究了下这个的戳破过程:

[60]       [9,76,60]  [9,75,64,97,60]
 60 ——> 9 ——> 76 ——> 97 ——> 64 -> 21
       [9,60]  [9,75,97,60]   [9,76,64,21,97,60]

即从 21 开始,一直到最后一个 60。

相比:

  • 正确:21->64->97->76->9->60
  • 错误:21->64->76->97->9->60

正确题解:

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxCoins = function(nums) {
  let n = nums.length
  let dp = Array.apply(null, Array(n + 2)).map(t => Array(n + 2).fill(0))
  nums = [1, ...nums, 1]
  for(let i = n - 1; i >= 0; i--){
    for(let j = i + 1; j < n + 2; j++){
      for(let k = i + 1; k < j; k++){
        let temp = dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]
        dp[i][j] = Math.max(dp[i][j], temp)
      }
    }
  }
  console.log(dp);
  return dp[0][n + 1];
};

// console.log(maxCoins(
//   [3, 1, 5, 8],
// )); // 167

console.log(maxCoins(
  [9,76,64,21,97,60],
)); // 1086136

四 统计分析

本题暂不能统计分析。

五 套路分析

如果小伙伴有更好的思路想法,或者没看懂其中某种解法,欢迎评论留言或者私聊 jsliang~


知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

评论区

leon
2粉丝

励志做一条安静的咸鱼,从此走上人生巅峰。

0

0

4

举报