每日一题 LeetCode 679. 24点游戏 【递归】【全排列】

题目链接

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

题目说明

题解

主要方法：递归 + 全排列

解释说明：

1. 将 4 个数进行组合形成算式，发现除了 (a❈b)❈(c❈d) 的形式外，都可以通过单一的数字进行拆解，比如 (a*b+c)/d 可以逐步拆解成 (d -> (c -> (a -> (b))))。所以我们将特殊形式单独用全排列处理，一般情况用递归进行处理。

2. 递归：
   
   入口（数字list，目标值target）
   
   下一步（取list中的一个值，将该值与target运算，算出list剩余的数应该得到怎样的值）
   
   出口（list只剩一个值，与target相等）

3. 特殊处理： 对于 (a❈b)❈(c❈d) 的形式，将四个数字进行全排列后对每个可能的算式进行运算

代码示例：

class Solution:

    def judgePoint24(self, nums: List[int]) -> bool:

        #考虑精度误差，当结果与 24 的误差在 1e6 以内可以认为相等

        EPSILON = 1e-6

        def dfs(numbers, target):

            if len(numbers) == 1:

                return True if abs(numbers[0] - target) < EPSILON else False

            for idx,num in enumerate(numbers):

                tmp_nums = numbers[:]

                tmp_nums.remove(num)

                if dfs(tmp_nums, target - num) or dfs(tmp_nums, num - target) or (target and dfs(tmp_nums, num / target)) or (num and dfs(tmp_nums, target / num)):

                    return True

            return False

        if dfs(nums, 24):

            return True

        # 将 (a b) (c d) 的特殊情况单独处理，其他情况都可以从一个数逐步拆解

        for num_arrange in list(permutations(nums)):

            if (num_arrange[0] + num_arrange[1]) * (num_arrange[2] + num_arrange[3]) == 24 \

                or (num_arrange[0] + num_arrange[1]) * (num_arrange[2] - num_arrange[3])  == 24 \

                or (num_arrange[0] - num_arrange[1]) * (num_arrange[2] + num_arrange[3])  == 24 \

                or (num_arrange[0] - num_arrange[1]) * (num_arrange[2] - num_arrange[3])  == 24 \

                or ((num_arrange[2] + num_arrange[3]) and (num_arrange[0] + num_arrange[1]) / (num_arrange[2] + num_arrange[3])  == 24) \

                or ((num_arrange[2] - num_arrange[3]) and (num_arrange[0] + num_arrange[1]) / (num_arrange[2] - num_arrange[3])  == 24) \

                or ((num_arrange[2] + num_arrange[3]) and (num_arrange[0] - num_arrange[1]) / (num_arrange[2] + num_arrange[3])  == 24) \

                or ((num_arrange[2] - num_arrange[3]) and (num_arrange[0] - num_arrange[1]) / (num_arrange[2] - num_arrange[3])  == 24):

                return True

        return False

大神的暴力美学

https://leetcode.com/problems/24-game/discuss/107675/Short-Python

def helper(nums):

    print(nums)

    if len(nums) == 1:

        return math.isclose(nums[0], 24)

    return any(helper((x,) + tuple(rest)) for a, b, *rest in permutations(nums) for x in

               {a + b, a - b, a * b, b and a / b})

return helper(tuple(nums))