0679：24 点游戏（★★）

2016-11-09 约 602 字预计阅读 2 分钟次阅读

力扣第 679 题

题目

给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。

你须遵守以下规则:

除法运算符 '/' 表示实数除法，而不是整数除法。
- 例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。
每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。
- 例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。
你不能把数字串在一起
- 例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。

如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。

示例 1:

输入: cards = [4, 1, 8, 7]
输出: true
解释: (8-4) * (7-1) = 24

示例 2:

输入: cards = [1, 2, 1, 2]
输出: false

提示:

cards.length == 4
1 <= cards[i] <= 9

分析

#1

每次任选两张和一个运算符，合并成一张，最后合成 24 即成功
为了防止处理浮点数，可以用 Fraction

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        from fractions import Fraction
        @cache
        def dfs(A):
            n = len(A)
            if n==1:
                return A[0]==24
            for i,j in product(range(n),range(n)):
                if i!=j:
                    B = [A[k] for k in range(n) if k not in [i,j]]
                    for x in [A[i]+A[j],A[i]-A[j],A[i]*A[j]]:
                        if dfs(tuple(B+[x])):
                            return True
                    if A[j]!=0 and dfs(tuple(B+[A[i]/A[j]])):
                        return True
            return False
        return dfs(tuple(Fraction(a,1) for a in cards))

147 ms

#2

更通用的做法是枚举所有可能拼成的值
令 f(A) 代表集合 A 所有能拼成的值
枚举 A 划分为两个集合 B、C，根据 f(B) 和 f(C) 和运算符的组合，即可得到 f(A)
可以将集合状态压缩为一个数

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        from fractions import Fraction
        m = 1<<4
        sub = [[] for _ in range(m)]
        f = [set() for _ in range(m)]
        for st in range(1,m):
            y = (st-1)&st
            while y:
                sub[st].append((y,st^y))
                y = (y-1)&st
            k,i = st.bit_count(),st.bit_length()-1
            if k==1:
                f[st].add(Fraction(cards[i],1))
            else:
                for a,b in sub[st]:
                    for x,y in product(f[a],f[b]):
                        f[st] |= {x+y,x-y,x*y}|({x/y} if y else set())
        return 24 in f[-1]

413 ms

目录

0679：24 点游戏（★★）

题目

分析

#1

#2

解答