679. 24 点游戏
题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/24-game
题目
你有 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 。
解题思路
思路：回溯
抛开本题，先说一下，咱们平时玩 24 点游戏个别程序是：
- 抉择两个数字，进行四项运算；
- 而后就计算结果与剩下两个数字中，再次选取两个数字，再进行四项运算，失去后果；
- 最终剩下两个数字，进行四项运算，看最终后果是否等于 24。
当初看本题，咱们也是采纳下面的模式进行枚举，去尝试所有可能的组合。
这里额定提及一下，在例题当中呈现了括号'('、')'，这里括号有优先级。然而在这里，咱们不做解决，因为在枚举的时候，是蕴含这种状况的。
还有个须要留神的中央。题目中阐明除法运算是实数除法，并不是整数除法，那么这里会波及到精度问题。这里默认只有最终后果误差小于 1e-6，那么认为相等。除数不能为 0，这里也同样默认绝对值小于 1e-6，则认为等于 0。
咱们晓得，四项运算中，加法、乘法是合乎交换律的。那么这两项运算当中，两个数字前后地位不影响后果，可思考跳过其中一种状况。
具体代码如下。
代码实现
class Solution: def judgePoint24(self, nums: List[int]) -> bool: def helper(nums): if not nums: return False if len(nums) == 1: return abs(nums[0] - 24) < 0.000001 for i in range(len(nums)): for j in range(len(nums)): # 不能选取同个地位的数字 if i == j: continue # 标记是否最终后果等于 24 status = False x = nums[i] y = nums[j] # 选取 i,j 对应地位的数字进行计算，其余数字放入数组后续计算 new_nums = [nums[k] for k in range(len(nums)) if( k!=i and k!=j)] # 执行四项运算，加法乘法合乎交换律，a + b = b + a, a*b=b*a，可跳过其中一项 # 这里默认 i > j 局部跳过，or 短路语句 # 加法，乘法 if i < j: status = status or helper(new_nums + [x+y]) status = status or helper(new_nums + [x*y]) # 减法 status = status or helper(new_nums + [x-y]) # 除法 if abs(y) > 0.000001: status = status or helper(new_nums + [x/y]) if status: return True return False return helper(nums)实现后果
欢送关注
公众号 【书所集录】