24点游戏

  • 该题目本质是暴力搜索

  • 比较简单的暴力搜索顺序为，从4个数中任选两个数进行四种不同的运算，进入下层搜索，知道只剩下最后的结果

    1. class Solution {
    2. public:
    3.   // 这里要注意的是，其实不在乎res的顺序，因为我们都是要在下层循环全排列的
    4.   vector<double> calculate(vector<double> &nums, int i, int j, double x) {
    5.       vector<double> res;
    6.       for (int k = 0; k < nums.size(); k ++) {
    7.           if (k != i && k != j) {
    8.               res.push_back(nums[k]);
    9.           }
    10.       }
    11.       res.push_back(x);
    12.       return res;
    13.   }
    15.   bool dfs(vector<double> nums) {
    16.       if (nums.size() == 1) {
    17.           return fabs(nums[0] - 24) < 1e-8;
    18.       }
    20.       // 选择两个位置进行运算
    21.       for (int i = 0; i < nums.size(); i ++) {
    22.           for (int j = 0; j < nums.size(); j ++) {
    23.               if (i == j) {
    24.                   continue;
    25.               }
    26.               double a = nums[i], b = nums[j];
    27.               // 该位置可能的4种运算
    28.               if (dfs(calculate(nums, i, j, a + b))) return true;
    29.               if (dfs(calculate(nums, i, j, a - b))) return true;
    30.               if (dfs(calculate(nums, i, j, a * b))) return true;
    31.               if (dfs(calculate(nums, i, j, a / b))) return true;
    32.           }
    33.       }
    34.       return false;
    35.   }
    37.   bool judgePoint24(vector<int>& nums) {
    38.       vector<double> a(nums.begin(), nums.end());
    39.       return dfs(a);
    40.   }
    41. };