679. 24 点游戏

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