题目描述:
You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *
, /
, +
, -
, (
, )
to get the value of 24.
Example 1:
Input: [4, 1, 8, 7] Output: True Explanation: (8-4) * (7-1) = 24
Example 2:
Input: [1, 2, 1, 2] Output: False
Note:
- The division operator
/
represents real division, not integer division. For example, 4 / (1 - 2/3) = 12. - Every operation done is between two numbers. In particular, we cannot use
-
as a unary operator. For example, with[1, 1, 1, 1]
as input, the expression-1 - 1 - 1 - 1
is not allowed. - You cannot concatenate numbers together. For example, if the input is
[1, 2, 1, 2]
, we cannot write this as 12 + 12.
题目大意:
给定4个范围1~9的数字,判断是否可以利用四则运算和括号,组成24。
解题思路:
递归(Recursion)
Python代码:
class Solution(object):
def judgePoint24(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
return any(abs(x - 24) < 1e-9 for x in self.solve(nums))
def solve(self, nums):
size = len(nums)
if size == 1: return [nums[0]]
ans = []
for x in range(size):
left, n = nums[x], nums[ : x] + nums[x + 1 : ]
for right in self.solve(n):
ans.append(left + right)
ans.append(left - right)
ans.append(left * right)
if right: ans.append(1.0 * left / right)
if size >=3:
for x in range(size):
for y in range(x + 1, size):
left, right = nums[x], nums[y]
n = nums[:x] + nums[x + 1 : y] + nums[y + 1 : ]
ans += self.solve([left + right] + n)
ans += self.solve([left - right] + n)
ans += self.solve([left * right] + n)
if right: ans += self.solve([1.0 * left / right] + n)
return ans
本文链接:http://bookshadow.com/weblog/2017/09/17/leetcode-24-game/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。