679. 24 点游戏

题目来源：力扣（LeetCode）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 。

解题思路

思路：回溯

抛开本题，先说一下，我们平时玩 24 点游戏一般顺序是：

• 选择两个数字，进行四项运算；
• 然后就计算结果与剩下两个数字中，再次选取两个数字，再进行四项运算，得到结果；
• 最终剩下两个数字，进行四项运算，看最终结果是否等于 24。

现在看本题，我们也是采用上面的形式进行枚举，去尝试所有可能的组合。

这里额外提及一下，在例题当中出现了括号’(’、’)’，这里括号有优先级。但是在这里，我们不做处理，因为在枚举的时候，是包含这种情况的。

还有个需要注意的地方。题目中说明除法运算是实数除法，并不是整数除法，那么这里会涉及到精度问题。这里默认只要最终结果误差小于 1e-6，那么认为相等。除数不能为 0，这里也同样默认绝对值小于 1e-6，则认为等于 0。

我们知道，四项运算中，加法、乘法是符合交换律的。那么这两项运算当中，两个数字前后位置不影响结果，可考虑跳过其中一种情况。

具体代码如下。

代码实现

class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        def helper(nums):
            if not nums:
                return False
            if len(nums) == 1:
                return abs(nums[0] - 24) < 0.000001

            for i in range(len(nums)):
                for j in range(len(nums)):
                    # 不能选取同个位置的数字
                    if i == j:
                        continue
                    # 标记是否最终结果等于 24
                    status = False

                    x = nums[i]
                    y = nums[j]

                    # 选取 i,j 对应位置的数字进行计算，其他数字放入数组后续计算
                    new_nums = [nums[k] for k in range(len(nums)) if( k!=i and k!=j)]
                    # 执行四项运算，加法乘法符合交换律，a + b = b + a, a*b=b*a，可跳过其中一项
                    # 这里默认 i > j 部分跳过，or 短路语句
                    # 加法，乘法
                    if i < j:
                        status = status or helper(new_nums + [x+y])
                        status = status or helper(new_nums + [x*y])
                    # 减法
                    status = status or helper(new_nums + [x-y])
                    # 除法
                    if abs(y) > 0.000001:
                        status = status or helper(new_nums + [x/y])

                    if status:
                        return True
            return False
        return helper(nums)

实现结果

欢迎关注

公众号 【书所集录】