一天一大 lee(24点游戏)难度:困难-Day20200822

题目:

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。

示例

1. 示例 1:

输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24

2. 示例 2:

输入: [1, 2, 1, 2]
输出: False

注意:

• 除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
• 每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
• 你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。

抛砖引玉

枚举所有可能出现的组合：

• 任取两个数加减乘除
  • 其中两个数相减存在两个结果
  • 两个数相除存在两种结果，且0不能作为分母
• 差值相差$10^-6$10−6可被忽略，则使用$10^-6$10−6代替0校验

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var judgePoint24 = function (nums) {
  let _result = false
  const diff = 10e-6

  function helper(nums) {
    if (_result) return

    // 四个数字枚举完，且最小差值满足条件则返回true
    if (nums.length === 1 && Math.abs(nums[0] - 24) < diff) {
      _result = true
      return
    }

    for (let i = 0; i < nums.length; i++) {
      for (let j = 0; j < i; j++) {
        // 枚举两个数
        let n1 = nums[i],
          n2 = nums[j]

        // 存放当前枚举的两个数的运算结果
        let next = new Set()

        // 两数运算存在的结果
        next.add(n1 + n2)
        next.add(n1 - n2)
        next.add(n1 * n2)
        next.add(n2 - n1)
        if (Math.abs(n2) > diff) next.add(n1 / n2)
        if (Math.abs(n1) > diff) next.add(n2 / n1)

        // 标记一下 当前数已参与运算
        nums[i] = 'X'
        nums[j] = 'X'

        for (let n of next) {
          let tmp = nums.filter((n) => n !== 'X')
          // 将当前运算结果和本轮未参与运算的元素进入下轮两数枚举运算
          helper([n, ...tmp])
        }

        // 避免上面标记影响枚举，恢复list原状态
        nums[i] = n1
        nums[j] = n2
      }
    }
  }

  helper(nums)

  return _result
}

博客: 小书童博客

每天的每日一题，写的题解会同步更新到公众号一天一大 lee 栏目
欢迎关注留言

公号: 坑人的小书童