Leetcode.679.24Game

题目

给定4个数字，通过+，-，*，/组合出24，可以出现小数, 4 / (1 - 2/3) = 12.。

Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24
Input: [1, 2, 1, 2]
Output: False
Input: [1, 2, 3, 6]
Output: True
Input: [1, 3, 4, 6]
Output: True

思路1

穷举。

bool judgePoint24(vector<int>& nums) {
    double a = nums[0], b = nums[1], c = nums[2], d = nums[3];
    return judgePoint24_4(a, b, c, d);
}

bool judgePoint24_1(double a) {
    return abs(a - 24) < 1e-6;
}

bool judgePoint24_2(double a, double& b) {
    return
        judgePoint24_1(a + b) ||
        judgePoint24_1(a - b) ||
        judgePoint24_1(b - a) ||
        judgePoint24_1(a * b) ||
        judgePoint24_1(a / b) ||
        judgePoint24_1(b / a);
}

bool judgePoint24_3(double a, double& b, double& c) {
    return
        judgePoint24_2(b + c, a) ||
        judgePoint24_2(b - c, a) ||
        judgePoint24_2(c - b, a) ||
        judgePoint24_2(b * c, a) ||
        judgePoint24_2(b / c, a) ||
        judgePoint24_2(c / b, a) ||
        judgePoint24_2(a + c, b) ||
        judgePoint24_2(a - c, b) ||
        judgePoint24_2(c - a, b) ||
        judgePoint24_2(a * c, b) ||
        judgePoint24_2(a / c, b) ||
        judgePoint24_2(c / a, b) ||
        judgePoint24_2(a + b, c) ||
        judgePoint24_2(a - b, c) ||
        judgePoint24_2(b - a, c) ||
        judgePoint24_2(a * b, c) ||
        judgePoint24_2(a / b, c) ||
        judgePoint24_2(b / a, c);
}

bool judgePoint24_4(double& a, double& b, double& c, double& d) {
    return
        judgePoint24_3(c + d, a, b) ||
        judgePoint24_3(c - d, a, b) ||
        judgePoint24_3(d - c, a, b) ||
        judgePoint24_3(d * c, a, b) ||
        judgePoint24_3(c / d, a, b) ||
        judgePoint24_3(d / c, a, b) ||
        judgePoint24_3(b + d, a, c) ||
        judgePoint24_3(b - d, a, c) ||
        judgePoint24_3(d - b, a, c) ||
        judgePoint24_3(b * d, a, c) ||
        judgePoint24_3(b / d, a, c) ||
        judgePoint24_3(d / b, a, c) ||
        judgePoint24_3(b + c, a, d) ||
        judgePoint24_3(b - c, a, d) ||
        judgePoint24_3(c - b, a, d) ||
        judgePoint24_3(b * c, a, d) ||
        judgePoint24_3(b / c, a, d) ||
        judgePoint24_3(c / b, a, d) ||
        judgePoint24_3(a + d, b, c) ||
        judgePoint24_3(a - d, b, c) ||
        judgePoint24_3(d - a, b, c) ||
        judgePoint24_3(a * d, b, c) ||
        judgePoint24_3(a / d, b, c) ||
        judgePoint24_3(d / a, b, c) ||
        judgePoint24_3(a + c, b, d) ||
        judgePoint24_3(a - c, b, d) ||
        judgePoint24_3(c - a, b, d) ||
        judgePoint24_3(a * c, b, d) ||
        judgePoint24_3(a / c, b, d) ||
        judgePoint24_3(c / a, b, d) ||
        judgePoint24_3(a + b, c, d) ||
        judgePoint24_3(a - b, c, d) ||
        judgePoint24_3(b - a, c, d) ||
        judgePoint24_3(a * b, c, d) ||
        judgePoint24_3(a / b, c, d) ||
        judgePoint24_3(b / a, c, d);
}

思路2

先对数组进行全排列，然后两两结合。

vector<double> combine2(double a, double b) {
    return {a / b, b / a, a + b, a - b, b - a, a * b};
}

bool judgePoint24(vector<int>& nums) {
    vector<int> id ({0, 1, 2, 3});
    do {
        int a = nums[id[0]], b = nums[id[1]], c = nums[id[2]], d = nums[id[3]];
        for (auto x: combine2(a, b))
            for (auto y: combine2(c, d))
                for (auto z: combine2(x, y))
                    if (abs(z - 24) < 1e-4) {
                        return true;
                    }
        for (auto x: combine2(a, b))
            for (auto y: combine2(c, x))
                for (auto z: combine2(d, y))
                    if (abs(z - 24) < 1e-4) {
                        return true;
                    }
    } while (next_permutation(id.begin(), id.end()));
    return false;
}

总结

next_permutation可以对数组进行全排列。