题目分析

本题是一个大家都玩过的扑克游戏，小时候为了锻炼计算能力，家长和老师经常用扑克牌比赛，看谁能够使用四张牌迅速通过加减乘除得到24。

递归

这个题目其实也不难，我们模拟一下计算的过程即可，想得到24，肯定最后是由两个数字计算得到的。

题意中四个数字放在数组中，因此最后一步一定是两个数字放在数组中。

反过来说，倒数第二步一定是三个数字放在数组中，倒数第三步一定是四个数字放在数组中。

可以理解为F4 -> F3 -> F2 -> F1，其中F表示数组中的元素个数。F1如果唯一的一个数字等于24，表示最终答案正确。

所以本题可以使用递归的方式求解，由 $ F_n->F_{n-1} $ 的过程是从n个元素中选择两个进行加减乘除运算，因为运算有顺序，因此选择方式不是$ C_n^2$，而是$ A_n^2 $，每一次选择有4种运算符，因此时间复杂度是 $ 4n^2 $。递归n次的结果，算法的**时间复杂度为O(4^n \times n^{2n})，空间复杂度为O(n)**。

因为这里n = 4固定，所以时间复杂度和空间复杂度都是$$ O(1) $$。

class Solution {
    public static final double EPS = 1e-5;

    public static final int RES = 24;

    public static final char[] SIGN = new char[]{'+', '-', '*', '/'};

    public boolean judgePoint24(int[] cards) {
        return helper(Arrays.stream(cards).mapToDouble(i -> i).toArray());
    }

    private boolean helper(double[] remain) {
        int n = remain.length;
        if (n == 1) {
            return Math.abs(remain[0] - RES) < EPS;
        }
        double[] cur = new double[n - 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                int idx = 0;
                for (int k = 0; k < n; k++) {
                    if (k != i && k != j) {
                        cur[idx++] = remain[k];
                    }
                }
                for (char c : SIGN) {
                    switch (c) {
                        case '+':
                            cur[idx] = remain[i] + remain[j];
                            break;
                        case '-':
                            cur[idx] = remain[i] - remain[j];
                            break;
                        case '*':
                            cur[idx] = remain[i] * remain[j];
                            break;
                        case '/':
                            cur[idx] = remain[i] / remain[j];
                            break;
                    }
                    if (helper(cur)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

刷题总结

本题难度不大，能否想到使用递归的思路非常重要，此题还有一个陷阱是要注意浮点数计算时要考虑精度问题。