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)

实现后果

欢送关注

公众号【书所集录】