题目描述
You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.
Example 1:
Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24
Example 2:
Input: [1, 2, 1, 2]
Output: False
Note:
- The division operator
/represents real division, not integer division. For example,4 / (1 - 2/3) = 12. - Every operation done is between two numbers. In particular, we cannot use
-as a unary operator. For example, with[1, 1, 1, 1]as input, the expression-1 - 1 - 1 - 1is not allowed. - You cannot concatenate numbers together. For example, if the input is
[1, 2, 1, 2], we cannot write this as12 + 12.
解题思路
此题目给了 4 个 10 以内的数字，要求判断这四个数字是否能够通过 加减乘除 操作得到 24 .
最简单粗暴的方法：穷举法。
4 个数字全排列，一共有 24 种情况；3 个符号，64 种情况；考虑到对称重复，总共情况不超过 24 × 64 ÷ 2 = 768 种；再考虑到加法和乘法的交换，情况可能更少。
Tips:
使用 sort() 和 next_permutation() 可以产生数组的全排列，并且是从数组中当前的字典序开始依次增大直至到最大字典序。
函数包含在头文件
int a[];
do
{
}while(next_permutation(a,a+n));
参考代码
class Solution {
public:
bool judgePoint24(vector<int>& nums)
{
sort(nums.begin(), nums.end());
do
{
if (Valid(nums))
return true;
} while (next_permutation(nums.begin(), nums.end()));
return false;
}
bool Valid(vector<int>& nums)
{
double a, b, c, d;
a = nums[0]; b = nums[1]; c = nums[2]; d = nums[3];
if (Valid(a + b, c, d) || Valid(a - b, c, d) || Valid(a*b, c, d) || (b != 0 && Valid(a / b, c, d)))
{
return true;
}
if (Valid(a, b + c, d) || Valid(a, b - c, d) || Valid(a, b*c, d) || (c != 0 && Valid(a, b / c, d)))
{
return true;
}
if (Valid(a, b, c + d) || Valid(a, b, c - d) || Valid(a, b, c* d) || (d != 0 && Valid(a, b, c / d)))
{
return true;
}
return false;
}
bool Valid(double a, double b, double c)
{
if (Valid(a + b, c) || Valid(a - b, c) || Valid(a*b, c) || (b != 0 && Valid(a / b, c)))
{
return true;
}
if (Valid(a, b + c) || Valid(a, b - c) || Valid(a, b* c) || (c != 0 && Valid(a, b / c)))
{
return true;
}
return false;
}
bool Valid(double a, double b)
{
if (abs(a + b - 24.0) < 0.000001 || abs(a - b - 24.0) < 0.000001 || abs(a * b - 24.0) < 0.000001 || (b != 0 && abs(a / b - 24.0) < 0.000001))
{
return true;
}
else
return false;
}
};
参考资料
【1】24 Game 4个数加减乘除得到24 + 24点游戏 + 暴力求解
【2】关于全排列 next_permutation() 函数的用法
本文由 机灵鹤 SmartCrane 创作
本站文章所有原创文章, 转载前请务必署名
最后编辑时间为: 2018-09-27 20:50