leetcode679_24点游戏的暴力解法
leetcode679_24点游戏
01 问题描述
你有 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 。
02 暴力解法1-思想
24点游戏是一个耳熟能详的游戏，对于给定的4个数和4个操作符，我首先想到的方法就是暴力穷举。
具体来说，首先从给定的4个数里有序地选2个（为什么要有序呢，因为2-4和4-2的结果是完全不同的），一共有4×3=12个选择，然后4个操作符随机选一个，得到的结果和剩下的2个数字一起进入下一轮。
下一轮中，3个数里依旧有序地选择2个，一共3×2=6个选择，然后依旧4个操作符随机选一个，得到的结果和最后1个数字进入下一轮选择。
最后一轮，只剩2个数字，有序排列，有2种可能，然后选择操作符。
综上，一共有4×3×4×3×2×4×2×4=9216种可能。验证这些可能的计算结果是否等于24，如果有的话就直接返回return True。
具体实现过程中，使用一个新的list来存储当前剩余的数字。
另外，为了进行实数的除法，这里使用python中的Fraction模块
03 暴力解法2-code
这里代码部分参考了官方提供的解法
#python3
from fractions import Fraction #python中进行分数计算
class Solution:
def judgePoint24(self, nums: List[int]) -> bool:
if not nums or len(nums)!=4:
return False
def run(nums:List[float]) -> bool:
if not nums:
return False
if len(nums)==1:
return abs(nums[0]-24) == 0
for i,x in enumerate(nums):
for j,y in enumerate(nums):
if(i == j):
continue
newNums = []
for k,z in enumerate(nums):
if k != i and k != j:
newNums.append(z)
for k in range(4):
if k == 0:
newNums.append(x+y)
elif k ==1 :
newNums.append(x-y)
elif k==2 :
newNums.append(x*y)
elif k ==3 :
if y == 0:
continue
newNums.append(Fraction(x,y))
if run(newNums):
return True
newNums.pop()
return False
return run(nums)
04 暴力解法2-思想
python3里面有一个itertools模块，可以帮助我们遍历一个序列中元素的所有可能的排列或组合。如果我们想要用上这个module，应该怎么样进行穷举呢？
穷举的思想变成了：
首先对于给定的4个数进行有序排列，一共有4×3×2×1=24种组合，这部分的工作可以用itertools模块实现。
然后对于给定的4个有序的数字，例如，[a,b,c,d]，我们需要为他们选择3个运算符，共有4^3= 64种组合。
最后对于已经指定了彼此之间运算符的4个有序数字，例如，a obs1 b obs c obs d， 我们需要选择运算符计算的顺序，对于3个有序的运算符，一共有3×2=6种可能。这步操作相当于为表达式增加了括号。
因此，一共的可能性就是 24 × 64 × 6 = 9216种，和第二章节得到的结果一模一样。
05 暴力解法2-code
#python3
from fractions import Fraction #python中进行分数计算
from itertools import permutations #得到序列中所有元素的所有可能排列组成
from itertools import product
class Solution:
def judgePoint24(self, nums: List[int]) -> bool:
if not nums or len(nums)!=4:
return False
def compute(nums:List[float]) -> float :
op = nums[1]
a = nums[0]
b = nums[2]
if op== 0:
return a+b
elif op == 1 :
return a-b
elif op == 2:
return a*b
elif op == 3 and b!=0 :
return Fraction(a,b)
elif b==0 :
return -1000000 #当除数是0的时候，也必须返回一个值，不然会报错无法进行后续计算
x = list(range(4))
for permu in permutations(nums):
for op in product(x,x,x):
newList = list(permu) + []
for i in range(3):
newList.insert(i*2+1,op[i])
#手动遍历6种计算组合，有2种结果一样，被我注释掉了
if compute([compute(([compute(newList[0:3])]+newList[3:5]))]+newList[5:])==24: return True
elif compute([compute(newList[0:3])]+newList[3:4]+[compute(newList[4:])]) == 24: return True
elif compute([compute(newList[:2]+[compute(newList[2:5])])]+newList[5:]) ==24: return True
elif compute(newList[:2]+[compute([compute(newList[2:5])]+newList[5:])]) ==24: return True
#elif compute([compute(newList[:3])]+newList[3:4]+[compute(newList[4:])]) ==24 : return True
elif compute(newList[:2]+[compute(newList[2:4]+[compute(newList[4:])])])==24 : return True
return False
06 summary
这道理其实并没有体现多少算法思维，在可能性很有限的情况，凭借暴力解法完全可以解决。但是具体的实现过程中，还是有一些小心思需要考虑。比如实数除法的实现，对于非python，可以通过设置精度误差来实现；还比如除数不能为0的处理。反正感觉自己这次写的code很傻……
本文地址：https://blog.csdn.net/lalaxumelala/article/details/108169134