24点游戏679

本文主要是介绍24点游戏679，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：
给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的
数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排
列成数学表达式，以获得值24。你须遵守以下规则:
（1）除法运算符 '/' 表示实数除法，而不是整数除法。例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。
（2）每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。
（3）你不能把数字串在一起例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。
如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false。输入: cards = [4, 1, 8, 7]
输出: true
解释: (8-4) * (7-1) = 24输入: cards = [1, 2, 1, 2]
输出: falsecards.length == 4
1 <= cards[i] <= 9

way：一开始有4个数字，按顺序选出2张A42，有12种顺序，然后将拿出的2张牌做4种运算中的一种运算得到一个结果牌，此时加上剩下的2张牌，还有3张牌，然后从3张牌有A32，6种顺序拿出2张牌做4种运算中的一种得到一个结果牌，此时加上剩下的1张牌，还有2张牌，最后这2张牌有A22的2种顺序进行4种运算中的一种运算，得到最后的结果牌，如果最后得到的结果是24，那么就可以，否则不能。为什么是A42而不是C42这种方式拿牌呢，因为除法和减法运算与数的运算顺序是有关的，所以要有顺序的拿，然后为了防止A+B，A*B, 与B+A，B * A 这样得到重复的运算结果，所以加了判断去除重复。12*6*2*4*4*4=9216种可能性。

我觉得此题的关键之处在于知道怎样去选牌，去选运算，减少到最后一个结果值，没那么难的啦!

看看别人说的多好！

#define ADD 0
#define SUB 1
#define MUL 2
#define DIV 3
double EPLISION =1e-6;class Solution {
public:bool solve(vector<double>& cards){if(cards.size()==0 ) return false;if(cards.size()==1)  return abs(cards[0]-24)<EPLISION;int n = cards.size();for(int i=0; i<n; i++){for(int j=0; j<n; j++){//顺序的选2个数if(i!=j){vector<double>nums;for(int x=0; x<n; x++){//将除了运算的2个数之外的其他数字push进nums中if(x!=i && x!=j){nums.push_back(cards[x]);}}//从4种运算中选取一种运算for(int op=0; op<4; op++){if((op==ADD || op == MUL) && j>i) continue;if(op == ADD){nums.push_back(cards[i]+cards[j]);}else if(op == SUB){nums.push_back(cards[i]-cards[j]);}else if(op == MUL){nums.push_back(cards[i]*cards[j]);}else{//除数是0时，continue掉if(abs(cards[j])<EPLISION) continue;nums.push_back(cards[i]/cards[j]);}if(solve(nums)) return true;//去除当前选择的运算结果nums.pop_back();}}}}return false;}bool judgePoint24(vector<int>& cards) {vector<double>cards2;for(int i=0; i<cards.size(); i++){cards2.push_back((double)cards[i]);}return solve(cards2);}
};

时间复杂度：O(1)。一共有 9216 种可能性，对于每种可能性，各项操作的时间复杂度都是 O(1)，因此总时间复杂度是 O(1)。

空间复杂度：O(1)。空间复杂度取决于递归调用层数与存储中间状态的列表，因为一共有 4个数，所以递归调用的层数最多为 4，存储中间状态的列表最多包含 4个元素，因此空间复杂度为常数。

这篇关于24点游戏679的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---