0679. 24 点游戏

题目地址(679. 24 点游戏)

https://leetcode-cn.com/problems/24-game/

题目描述

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

示例 1:

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


示例 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 。

前置知识

  • 数字精度问题

  • 分治

公司

  • 暂无

思路

题目给了我们四个数字,让我们通过 + - $\times$ $\div$ 将其组成 24。由于题目数据范围只可能是 4,因此使用暴力回溯所有可能性是一个可行的解。

我们先使用回溯找出 nums 的全部全排列,这一步需要枚举 $4 \times 3 \times 2 \times 1$ 种可能。由于四种运算都是双目运算(题目明确指出 - 不能当成负号),因此我们可以任意选出两个,继续枚举四种运算符。 由于选出哪个对结果没有影响,因此不妨我们就选前两个。接下来,将前两个的运算结果和后面的数继续使用同样的方法来解决。 这样问题规模便从 4 缩小到了 3,这样不断进行下去直到得到一个数字为止。如果剩下的这唯一的数字是 24,那么我们就返回 true,否则返回 false。

值得注意的是,实数除存在精度误差。因此我们需要判断一下最后的结果离 24 不超过某个精度范围即可,比如如果结果和 24 误差不超过 $10^{-6}$,我们就认为是 24,返回 true 即可。

关键点

  • 使用递归将问题分解成规模更小的同样问题

  • 精度控制,即如果误差不超过某一个较小的数字就认为二者是相等的

代码

  • 语言支持:Python3

Python3 Code:


class Solution:
    def judgePoint24(self, nums: List[int]-> bool:
        if len(nums) == 1:
            return math.isclose(nums[0], 24)
        return any(self.judgePoint24([x] + rest) for a, b, *rest in permutations(nums) 
for x in [a+b, a-b, a*b, b and a/b])

复杂度分析

由于题目输入大小恒为 4 ,因此实际上我们算法复杂度也是一个定值。

  • 时间复杂度:$O(1)$

  • 空间复杂度:$O(1)$

更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。

最后更新于