给定一个长度为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
。
思路:
- 每次从剩余牌中取两张牌,执行计算,合并成一张新牌。所以每次计算后会减少一张牌,得到一个新的数组 newCards。
- 用 newCards 递归调用 judgePoint24,直到只剩一张牌。判断这张牌的数字是否等于 24。
一共有六种运算方式:加减乘除,其中减和除有两种不同的顺序(不满足交换律)。
注意除法需要保证分母不为 0。
有两种方法实现除法:浮点数、分数类。如果用浮点数的话,会有舍入误差。但本题只有 4 张牌,舍入误差不会很大,取 ϵ=10−9足矣。如果两数绝对差小于 ϵ,则认为两数相等。