问题
你有 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 。
链接：https://leetcode-cn.com/problems/24-game
解答
递归暴力搜寻。。。
judgePoint24(cards)函数意义为 cards 数组 是否满足 24 点。
存在递归关系 ， 从cards中随便挑选两个进行任何运算，把运算出来的结果放回cards，调用递归算下去即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution:
def judgePoint24(self, cards: List[int]) -> bool:
size = len(cards)
if len(cards) == 1:
return abs(cards[0] - 24) < 0.0001
for i in range(size):
for j in range(size):
if i == j: continue
for sign in "+-*/":
newCards = cards[:]
newCards.remove(cards[i])
newCards.remove(cards[j])
try:
newCards.append(eval("%f%s%f" % (cards[i], sign, cards[j])))
if self.judgePoint24(newCards):
return True
except ZeroDivisionError:
pass
return False
|
输出表达式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| from typing import List
class Solution:
def dfs(self, cards, formulas):
size = len(cards)
if len(cards) == 1:
ans = abs(cards[0] - 24) < 0.0001
if ans:
print(formulas[0] + " = 24")
return True
for i in range(size):
for j in range(size):
if i == j: continue
for sign in "+-*/":
newCards = cards[:]
newCards.remove(cards[i])
newCards.remove(cards[j])
newFormulas = formulas[:]
newFormulas.remove(formulas[i])
newFormulas.remove(formulas[j])
try:
formula = "%f%s%f" % (cards[i], sign, cards[j])
newCards.append(eval(formula))
newFormulas.append('(' + formulas[i] + sign + formulas[j] + ')')
if self.dfs(newCards, newFormulas):
return True
except ZeroDivisionError:
continue
return False
def judgePoint24(self, cards: List[int]) -> bool:
return self.dfs(cards, list(map(str, cards)))
if __name__ == '__main__':
sol = Solution()
cards = [8, 1, 6, 6]
ret = sol.judgePoint24(cards)
print(ret)
|