数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 24 点游戏
假设我们有四张卡片，这些卡片上分别写着 1 到 9 之间的某个数字。我们需要检查是否可以通过一些运算符（如 +、-、*、/）来得到 24。例如，如果我们有一些数字，比如 [4, 9, 2, 6]，那么我们可以通过 (4 * 9) – (2 * 6) 得到 24，答案将为真。
为了解决这个问题，我们将遵循以下步骤：
- epsilon := 10.0^-5
- 定义一个函数 solve()，它将接收一个数组 v 作为参数。
- 如果 v 的大小为 1，则：
- 当 |v[0] - 24.0| <= epsilon 时返回 true
- 初始化 i := 0，当 i < v 的大小，更新 (i 增加 1)，执行：
- 初始化 j := 0，当 j < v 的大小，更新 (j 增加 1)，执行：
- 如果 i 等于 j，则：忽略以下部分，跳到下一个迭代
- 定义一个数组 res
- 初始化 k := 0，当 k < v 的大小，更新 (k 增加 1)，执行：
- 如果 i 不等于 k 且 j 不等于 k，则：
- 将 v[k] 插入到 res 的末尾
- 如果 i 不等于 k 且 j 不等于 k，则：
- 初始化 k := 0，当 k < 4，更新 (k 增加 1)，执行：
- 如果 operators[k] 等于 '+'，则：
- 将 v[i] + v[j] 插入到 res 的末尾
- 否则，如果 operators[k] 等于 '-'，则：
- 将 v[i] - v[j] 插入到 res 的末尾
- 否则，如果 operators[k] 等于 '*'，则：
- 将 v[i] * v[j] 插入到 res 的末尾
- 否则
- 将 v[i] / v[j] 插入到 res 的末尾
- 如果 solve(res) 返回 true，则：
- 返回 true
- 从 res 中删除最后一个元素
- 如果 operators[k] 等于 '+'，则：
- 初始化 j := 0，当 j < v 的大小，更新 (j 增加 1)，执行：
- 返回 false
- 从主方法执行以下步骤：
- 定义一个数组 v
- 初始化 i := 0，当 i < nums 的大小，更新 (i 增加 1)，执行：
- 将 nums[i] 插入到 v 的末尾
- 返回 solve(v)
让我们看看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
char operators[4] = {'+', '-', '/', '*'};
double epsilon = pow(10.0, -5);
bool judgePoint24(vector<int>& nums) {
vector <double> v;
for(int i = 0; i < nums.size(); i++){
v.push_back(nums[i]);
}
return solve(v);
}
bool solve(vector <double> v){
if(v.size() == 1){
return abs(v[0] - 24.0) <= epsilon;
}
for(int i = 0; i < v.size(); i++){
for(int j = 0; j < v.size(); j++){
if(i == j) continue;
vector <double> res;
for(int k = 0; k < v.size(); k++){
if(i != k && j != k){
res.push_back(v[k]);
}
}
for(int k = 0; k < 4; k++){
if(operators[k] == '+'){
res.push_back(v[i] + v[j]);
}else if(operators[k] == '-'){
res.push_back(v[i] - v[j]);
}else if(operators[k] == '*'){
res.push_back(v[i] * v[j]);
}else{
res.push_back(v[i] / v[j]);
}
if(solve(res)) return true;
res.pop_back();
}
}
}
return false;
}
};
main(){
Solution ob;
vector<int> v = {4,9,2,6};
cout << (ob.judgePoint24(v));
}输入
{4,9,2,6}输出
1
更新于: 2020年6月1日
1K+ 阅读量
广告