679 24 点游戏（dfs）

冷不防 2022-09-03 00:18 179阅读 0赞

**1. 问题描述：**

你有 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 。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/24-game

**2. 思路分析：**

分析题目可以知道我们需要尝试计算所有可能的表达式的结果，所以可以使用**递归**来解决（一看这种问题肯定使用递归解决），考虑到存在括号的问题，我们可以采取这样的策略搜索所有方案，每一次任意选择两个数字a，b，尝试加减乘除四种不同的运算，删除掉在原来数组中的这两个数字，将两个数的运算结果加入进来那么继续相同的操作...直到数组中只存在一个数字当前这一层的递归就结束了（每一次选择两个不同的数字进行四种不同的运算一定可以尝试所以表达式的运算结果，任意选择两个数字进行运算可以巧妙处理括号优先级的问题），因为除法存在精度问题所以我们得到最后一个数字的时候求解与24的绝对值之差，判断误差是否在一个很小的范围即可，如果误差在一个很小的范围那么我们认为最终的结果是相等的，返回True，否则返回False，如果在求解表达式的过程发现存在这样一组解使得结果为24那么直接返回True即可。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # 将i, j位置对应的数字删除掉, 将x加进来
        def get(self, nums: List[float], i: int, j: int, x: float):
            res = list()
            for u in range(len(nums)):
                if u != i and u != j: res.append(nums[u])
            res.append(x)
            return res
    
        def dfs(self, nums: List[float]):
            # 当误差在很小的范围可以认为是相等的
            if len(nums) == 1 and abs(nums[0] - 24) < 10 ** -8: return True
            # 结果不等于24返回False
            if len(nums) == 1: return False
            for i in range(len(nums)):
                for j in range(len(nums)):
                    # 任意选两个数字进行四种运算
                    if i != j:
                        a, b = nums[i], nums[j]
                        # 上面的两层循环都是从0开始的所以保证的两个数字是顺序是不一样的, 只要在搜索的过程中发现存在一组表达式的值等于24那么就返回True, 这样就会层层返回True了
                        if self.dfs(self.get(nums, i, j, a + b)): return True
                        if self.dfs(self.get(nums, i, j, a - b)): return True
                        if self.dfs(self.get(nums, i, j, a * b)): return True
                        # 注意b不能够等于0
                        if b != 0 and self.dfs(self.get(nums, i, j, a / b)): return True
            return False
    
        def judgePoint24(self, cards: List[int]) -> bool:
            nums = list()
            # 将所有数字转为float类型
            for x in cards:
                nums.append(float(x))
            return self.dfs(nums)