本文主要是介绍leetcode 679. 24点游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
你有 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，说明可以算出24，结果res赋值为true返回。这里我们的结果res是一个全局的变量，如果已经为true了，就没必要再进行运算了，所以第一行应该是判断结果res，为true就直接返回了。我们遍历任意两个数字，分别用p和q来取出，然后进行两者的各种加减乘除的运算，将结果保存进数组临时数组t，记得要判断除数不为零。然后将原数组nums中的p和q移除，遍历临时数组t中的数字，将其加入数组nums，然后调用递归函数，记得完成后要移除数字，恢复状态，这是递归解法很重要的一点。最后还要把p和q再加回原数组nums，这也是还原状态。
class Solution {
public:bool judgePoint24(vector<int>& nums) {bool res = false;double eps = 0.001;vector<double> ans(nums.begin(), nums.end());judge(ans,eps,res);return res;}void judge(vector<double>& ans, double eps, bool& res){if(res == true) return;if(ans.size() == 1){if(abs(ans[0] - 24) < eps ) res = true;return ;}for(int i = 0; i < ans.size(); ++i){for(int j = 0; j < i; ++j){double p = ans[i], q = ans[j];vector<double> t{p + q, p - q, q - p, p * q};if(p > eps) t.push_back(q / p);if(q > eps) t.push_back(p / q);ans.erase(ans.begin() + i);ans.erase(ans.begin() + j);for(auto index : t){ans.push_back(index);judge(ans, eps, res);ans.pop_back();}ans.insert(ans.begin() + j, q);ans.insert(ans.begin() + i, p);}}return ;}
};
这篇关于leetcode 679. 24点游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
