679. 24 点游戏
程序员文章站
2022-06-22 14:41:59
679. 24 点游戏你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *,/,+,-,(,) 的运算得到 24。思路回溯直接从四个数里面取2个数,然后执行一次运算符运算,把结果加入数组里面,变成了3个数,再取2个数,再执行一次运算,变成2个数,直到剩下一个数,判断是否和24相同即可。除数不能为0加法和乘法有交换律,可以跳过重复的除法是实数除法,需要将数据转换为double类型,并且计算精度问题。代码class Solution {public: static c...
679. 24 点游戏
你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *,/,+,-,(,) 的运算得到 24。
思路
回溯
直接从四个数里面取2个数,然后执行一次运算符运算,把结果加入数组里面,变成了3个数,再取2个数,再执行一次运算,变成2个数,直到剩下一个数,判断是否和24相同即可。
- 除数不能为0
- 加法和乘法有交换律,可以跳过重复的
- 除法是实数除法,需要将数据转换为double类型,并且计算精度问题。
代码
class Solution {
public:
static constexpr int target = 24;
static constexpr double epsilon = 1e-6;
static constexpr int add = 0, mul = 1, sub = 2, div = 3;
bool judgePoint24(vector<int>& nums) {
vector<double> list;
for(int i = 0; i < nums.size(); i++) {
list.push_back(static_cast<double>(nums[i]));
}
return solve(list);
}
bool solve(vector<double>& list) {
if(list.size() == 0) {
return false;
}
//列表只有一个数,判断是否等于24
if(list.size() == 1) {
return abs(list[0] - target) < epsilon;
}
//依次枚举2个数,不同序算不同
for(int i = 0; i < list.size(); i++) {
for(int j = 0; j < list.size(); j++) {
if(i != j) {
vector<double> tmp;
//先将剩余的数入列表
for(int k = 0; k < list.size(); k++) {
if(k != i && k != j) {
tmp.push_back(list[k]);
}
}
//计算取出的两个数运算结果
for(int k = 0; k < 4; k++) {
//加法和乘法符合交换律,可以跳过
if(k < 2 && i > j) {
continue;
}
//进行运算
if(k == add) {
tmp.push_back(list[i] + list[j]);
}
else if(k == mul) {
tmp.push_back(list[i] * list[j]);
}
else if(k == sub) {
tmp.push_back(list[i] - list[j]);
}
else {
if(list[j] < epsilon) {
continue;
}
tmp.push_back(list[i] / list[j]);
}
//继续递归判断
if(solve(tmp)) {
return true;
}
//回溯
tmp.pop_back();
}
}
}
}
return false;
}
};
本文地址:https://blog.csdn.net/weixin_38688399/article/details/108169476
上一篇: 原生js封装的ajax方法示例