1 題目描述

2 解題思路

2.1 遍歷所有可能情況

我們先找出四張牌所有可能的排列組合。

然后對于每一種排列組合，我們先提出排列組合中最前面的兩個數(shù)。然后對這兩個數(shù)進行加\減\乘\除操作。將結(jié)果放入我們當前考慮的排列組合中。

此時排列組合中有三個元素：原來的后兩個元素。和前兩個元素進行數(shù)學計算后的結(jié)果。

慢的操作是對這三個數(shù)組成的序列，再求它們 的排列組合。但實際上后兩個數(shù)的順序我們是可以固定的。也就是說，如果我們接下來提取出來的兩個數(shù)。有前兩個數(shù)運算后的結(jié)果，那么這個結(jié)果可能在運算符的左邊，也可能在運算符的右邊。這兩種情況我們都需要考慮

然后三個數(shù)組成的序列，經(jīng)過上面一部變成了兩個數(shù)。同第三步的考慮一樣。兩個操作數(shù)哪個在運算符的左邊，哪個在右邊。我們都需要進行討論和考慮。

還有一個tips。因為這種方法我們沒有排除掉除以0 的情況。為了防止除0報錯，進行除法的時候，我們需要對被除數(shù)加上一個很小的數(shù)值。

class Solution:def judgePoint24(self, cards: List[int]) -> bool:ret=[]for i in cards:tmp=copy.deepcopy(cards)tmp.remove(i)for j in tmp:tmp1=copy.deepcopy(tmp)tmp1.remove(j)for k in tmp1:tmp2=copy.deepcopy(tmp1)tmp2.remove(k)l=tmp2[0]ret.append([i,j,k,l]) #四張牌所有的排列組合 ''' 求排列組合的大致思想是： 我們先從四個元素組成的序列中提取一個； 然后從不含這個元素的三元素序列中提取一個； 然后是兩個中選一個，最后就是另外的一個 '''def judge2(ab,cd):#print(ab,cd)return((abs(ab+cd-24)<0.001)or(abs(ab*cd-24)<0.001)or(abs(ab-cd-24)<0.001)or(abs(ab/(cd+0.0000001)-24)<0.001)or(abs(cd-ab-24)<0.001)or(abs(cd/(ab+0.0000001)-24)<0.001)) #三元序列中提取兩個進行計算，得到的結(jié)果和序列中剩余的一個，這兩個數(shù)能否通過某種運算達到24def judge3(ab,c,d):#print(ab,c,d)return( judge2(ab+c,d) or judge2(ab-c,d)orjudge2(ab*c,d)orjudge2(ab/(c+0.0000001),d)orjudge2(c/(ab+0.0000001),d)orjudge2(c-ab,d)orjudge2(ab,c+d)orjudge2(ab,c-d)orjudge2(ab,c*d)orjudge2(ab,c/(d+0.0000001))) #四元序列中提取兩個進行運算，得到的結(jié)果和序列中剩余的兩個，這三個數(shù)能否通過什么方法使結(jié)果到24def judge4(a,b,c,d):return( judge3(a+b,c,d) or judge3(a-b,c,d)orjudge3(a*b,c,d)orjudge3(a/(b+0.0000001),c,d)) #四個數(shù)能否通過某些操作使得結(jié)果為24for i in ret:if(judge4(i[0],i[1],i[2],i[3])==True):return(True)return(False)

2.2 方法2 ：遞歸

class Solution:def judgePoint24(self, nums: List[int]) -> bool:TARGET = 24EPSILON = 1e-6ADD, MULTIPLY, SUBTRACT, DIVIDE = 0, 1, 2, 3def solve(nums: List[float]) -> bool:if len(nums) == 1:return abs(nums[0] - TARGET) < EPSILON #只剩下一個數(shù)了，就判斷這個數(shù)和24之間的差距是否在臨界差距以內(nèi) #在的話，那么說明可以通過運算得到24for i, x in enumerate(nums):for j, y in enumerate(nums):if i != j: #從nums中找不同的兩個數(shù)（區(qū)別于方法2.1的思路）newNums = list()for s, z in enumerate(nums):if s != i and s != j:newNums.append(z) #找第三個數(shù)for k in range(4):if k < 2 and i > j:continue ''' 加和乘運算，而且第一個運算數(shù)比第二個大 這說明之前在x等于第二個運算數(shù)的時候，x+y 或者x*y已經(jīng)計算過了 所以不用再次計算，直接繼續(xù)循環(huán) '''if k == ADD:newNums.append(x + y)elif k == MULTIPLY:newNums.append(x * y)elif k == SUBTRACT:newNums.append(x - y)elif k == DIVIDE:if abs(y) < EPSILON:continuenewNums.append(x / y)if solve(newNums):return True #如果x，y運算的結(jié)果和nums中剩下的兩個數(shù)組成的三個數(shù)可以算出24，那么返回TruenewNums.pop() ''' 不然的話，在三元素序列中，把當前算的這個達不到24的x，y運算結(jié)果pop出來， 然后看下一個操作符算出來的X,Y結(jié)果，和nums中剩下的兩個元素組成的三元素序列滿足不滿足條件要求 '''return Falsereturn solve(nums)

2.3 方法3：dfs

class Solution:def judgePoint24(self, cards: List[int]) -> bool:def dfs(nums):if len(nums) == 1:return abs(nums[0] - 24) < 0.00001 #序列中只有最后一個數(shù)了，進行判斷for i in range(len(nums)-1):for j in range(i+1, len(nums)):x, y = nums[i], nums[j] #提取兩個不一樣的數(shù)（這里假設(shè)x在序列中的排位一定在y前面） #所以之后考慮減法和除法的時候，需要分別考慮x和y在除/減數(shù)和被除/減數(shù)的情況rst = nums[:i] + nums[i+1:j] + nums[j+1:] #x和y元素以外的元素拼成一個序列a = dfs(rst + [x + y])b = dfs(rst + [x - y])c = dfs(rst + [y - x])d = dfs(rst + [x * y])e = (y != 0) and dfs(rst + [x / y])f = (x != 0) and dfs(rst + [y / x]) #將x，y經(jīng)過不同操作數(shù)的結(jié)果放到rst中，拼接而成的序列繼續(xù)進行dfsif a or b or c or d or e or f:return Truereturn Falsereturn dfs(cards)

總結(jié)

以上是生活随笔為你收集整理的文巾解题 679. 24 点游戏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。