679. 24 点游戏

题目

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

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

示例 2:

输入: [1, 2, 1, 2]
输出: False

注意:

  1. 除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
  2. 每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
  3. 你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。

题解

没有很好的想法，就是纯粹地暴力搜索4个数能计算出的所有结果。

  1. 首先考虑1个数的情况，就是返回本身
  2. 对于2个数的情况，搜索所有结果
  3. 对于3个数的情况：
    1. 先取出两个数，利用第2步得到所有结果
    2. 然后将该结果与剩下的一个数合并，继续利用第2步搜索结果
    3. 重新取两个数，直到遍历所有情况
  4. 对于4个数的情况：
    1. 取1个数，对剩下的数用第3步
    2. 取2个数，对两组数都用第2步

然后为了减少重复计算，我们用字典储存搜索结果，注意由于列表是可变对象，因此不能作为字典的key，需要将其转化为tuple，同时记得保持列表为有序状态。
然后为了减少情况数，我们把字典中的value设为set，这样就能去除重复值。
然后比较坑的一点是，LeetCode 的 Python 解释器中， / 默认是返回整型的，所以还得先把列表浮点化。

发现自己又犯蠢了，编译器选的Python而不是Python3，怪不得经常结果不对。。。

class Solution(object):
    def __init__(self):
        self.D = dict()

    def Search(self, nums):
        n = len(nums)
        if n == 1:
            return nums
        tuple_nums = tuple(nums)
        if tuple_nums in self.D:
            return self.D[tuple_nums]
        L = []
        for i in range(0, n):
            val = nums[i]
            A = self.Search(nums[:i]+nums[i+1:])
            for s in A:
                L.append(s+val)
                L.append(s-val)
                L.append(s*val)
                L.append(val-s)
                if val != 0:
                    L.append(s/val)
                if s != 0:
                    L.append(val/s)
        if n == 4:
            for i in range(0, n-1):
                for j in range(i+1, n):
                    a, b = nums[i], nums[j]
                    print(a, b)
                    A1 = self.Search([a, b])
                    nums.remove(a)
                    nums.remove(b)
                    A2 = self.Search(nums)
                    nums += [a, b]
                    nums.sort()
                    for s1 in A1:
                        for s2 in A2:
                            L.append(s1+s2)
                            L.append(s1-s2)
                            L.append(s1*s2)
                            L.append(s2-s1)
                        if s1 != 0:
                            L.append(s2/s1)
                        if s2 != 0:
                            L.append(s1/s2)
        self.D[tuple_nums] = set(L)
        return set(L)

    def judgePoint24(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        nums.sort()
        S=[float(i) for i in nums]
        L = self.Search(S)
        for i in L:
            if abs(i-24)<0.01:
                return True
        return False

so = Solution()
s = [1,6,6,8]
L1 = so.Search(s)
print(L1)
so.judgePoint24(s)

执行用时：44 ms, 在所有 Python 提交中击败了86.84%的用户 内存消耗：12.9 MB, 在所有 Python 提交中击败了92.11%的用户

居然速度和内存消耗都还控制得挺好，让人吃惊。

官方题解

  1. 先取2个数，计算可能结果，再把结果和剩下的2个数组合（此时还剩3个数）
  2. 重复第1步

如此简洁的想法，我居然一时没有想到。

class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        TARGET = 24
        EPSILON = 1e-6
        ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3

        def solve(nums: List[float]) -> bool:
            if not nums:
                return False
            if len(nums) == 1:
                return abs(nums[0] - TARGET) < EPSILON
            for i, x in enumerate(nums):
                for j, y in enumerate(nums):
                    if i != j:
                        newNums = list()
                        for k, z in enumerate(nums):
                            if k != i and k != j:
                                newNums.append(z)
                        for k in range(4):
                            if k < 2 and i > j:
                                continue
                            if k == ADD:
                                newNums.append(x + y)
                            elif k == MULTIPLY:
                                newNums.append(x * y)
                            elif k == SUBTRACT:
                                newNums.append(x - y)
                            elif k == DIVIDE:
                                if abs(y) < EPSILON:
                                    continue
                                newNums.append(x / y)
                            if solve(newNums):
                                return True
                            newNums.pop()
            return False

        return solve(nums)

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/24-game/solution/24-dian-you-xi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

他人题解

官方的思路很简单，但代码写得比较冗杂，看到一位大佬的题解，顿时惊为天人。

import functools
import itertools
import math

class Solution:
    def judgePoint24(self, nums):
        @functools.lru_cache(None)
        def helper(nums):
            if len(nums) == 1:
                return math.isclose(nums[0], 24)
            return any(helper((x,)+tuple(rest)) for a, b, *rest in itertools.permutations(nums) for x in {a+b, a-b, a*b, b and a/b})
        return helper(tuple(nums))

他人题解2

Python 6行，表达式树

把式子转换为表达式树，即可不用计算括号。 表达式树中叶子结点为操作数，非叶子结点为运算符。> 则可枚举出4个操作数有5种表达式树：

679. 24 点游戏 - 图1
其中a,b,c,d为操作数，f,g,h为运算符
写成代码，则为：

f(g(h(a,b),c),d)
f(g(a,h(b,c)),d)
f(g(a,b),h(c,d))
f(a,g(h(b,c),d))
f(a,g(b,h(c,d)))

利用Python的Lambda表达式和itertools，即可6行解出答案

class Solution:
    def judgePoint24(self, nums: List[int]) -> bool:
        op=[lambda x,y:x+y,lambda x,y:x-y,lambda x,y:x*y,lambda x,y:x/y if y!=0 else float('inf')]
        for a,b,c,d in itertools.permutations(nums):
            for f,g,h in itertools.product(op,repeat=3):
                if -1e-5<f(g(h(a,b),c),d)-24<1e-5 or \
                   -1e-5<f(g(a,h(b,c)),d)-24<1e-5 or \
                   -1e-5<f(g(a,b),h(c,d))-24<1e-5 or \
                   -1e-5<f(a,g(h(b,c),d))-24<1e-5 or \
                   -1e-5<f(a,g(b,h(c,d)))-24<1e-5:     #（这段if算一行
                    return True
        return False

作者：azusatsang
链接：https://leetcode-cn.com/problems/24-game/solution/python-6xing-biao-da-shi-shu-by-azusatsang/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。