C++刷leetcode（679. 24 点游戏）【深度优先搜索】
本帖最后由 糖逗 于 2020-5-8 17:51 编辑题目描述：
你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。
示例 1:
输入:
输出: True
解释: (8-4) * (7-1) = 24
示例 2:
输入:
输出: False
注意:
除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如， 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
你不能将数字连接在一起。例如，输入为 时，不能写成 12 + 12 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/24-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
void dfs(vector<double>&input, bool& res){
if (input.size() == 1) {
if (abs(input - 24) < 0.0001) res = true;
return;
}
for(int i = 0; i < input.size(); i++){
for(int j = 0; j < i; j++){
double temp1 = input, temp2 = input;
vector<double> temp {temp1 + temp2, temp1 - temp2, temp2 - temp1, temp1 * temp2};
if(temp2 > 0.0001) temp.push_back(temp1 / temp2);
if(temp1 > 0.0001) temp.push_back(temp2/temp1);
input.erase(input.begin() + i);
input.erase(input.begin() + j);
for(int i = 0; i < temp.size(); i++){
input.push_back(temp);
dfs(input, res);
input.pop_back();
}
input.insert(input.begin() + j, temp2);
input.insert(input.begin() + i, temp1);
}
}
}
bool solution(vector<int>&num){
bool res = false;
vector<double> input (num.begin(), num.end());
dfs(input, res);
return res;
}
int main(void){
vector<int> input;
int number;
while(cin >> number){
input.push_back(number);
}
cout << solution(input) << endl;
return 0;
}
注意事项：
1.input.insert(input.begin() + j, temp2);
input.insert(input.begin() + i, temp1);
上面的顺序不能反着，要正好和前面两句镜像对称
2. p-q q-p 包含了j+1到input.size（）的情况所以j取0到i即可。
3.bool后面一定要带&，因为res的值在运行dfs的时候可能会改变。
4.代码参考链接：https://leetcode-cn.com/problems/24-game/solution/679-24-dian-you-xi-jian-dan-hui-su-fa-by-guohaodin/
页:
[1]