java - LeetCode - 检查给定的 4 个整数是否可以变成 24

Question

我正在尝试这个LeetCode 问题，它要求纠正一个布尔函数，如果给定的 4 个整数数组可以通过基本算术运算符得到 24，则+返回-true 。括号无关紧要，因为如果所有排列都正确，它们将被隐式考虑。/*

对于这个问题，我使用 (n P k) 表示从 n 个元素中找到所有 k 大小的排列，因为顺序对于-和很重要/。

对于第一个选择，我们有 (4 P 2) = 12 和 4 个运算符，因此 12*4 = 48 个结果。对于第二个选择，我们剩下 3 个元素，或 (3 P 2) = 6 和 4 个运算符，得到 6*4 = 24 个结果。最后，我们有 2 个元素和 4 个运算符，总共有 8 个结果。总的来说，我们有 48 * 24 * 8 = 9216个元素和运算符的总排列。

我的解决方案适用于 LeetCode 的 69/70 测试用例（列表 3、3、8、8 错误地返回 false）。但是，每当我尝试调整代码以使最后一个测试用例工作时，一组新的测试用例就会失败。代码看起来是正确的，但显然不是，而且几个小时后我仍然很难过。

首先，一个交换数组中两个元素的辅助方法。

// swap indices x and y of array A
static void swap(double[] A, int x, int y) {
    double temp = A[x];
    A[x] = A[y];
    A[y] = temp;
}

核心思想是保留剩余的值A[0..right]（注意包含的上限）。指标i和j表示为操作选择的 2 个元素。将此新结果放入i.

现在A[j]，在该计算中用完，需要“删除”。这是通过与 交换来完成j的right。在递归调用中，递减right是因为您将 2 个值与某个运算符组合在一起，现在剩下的元素少了 1 个。所以现在j驻留在数组的正确分区中，将不再用于未来的计算。

/**
 * Iterate through all 9216 permutations of elements and operators until a permutation
 * that can make 24 has been found.
 * 
 * @param  A     Array of doubles
 * @param  right Rightmost index of current subarray A[0..right],
                 which stores the remaining elements
 * @return       True if the original given array can produce 24
 */
static boolean permute(double[] A, int right) {
    // base case, array of size 1
    if (right == 0) { return A[0] == 24; }

    // choose 2 distinct elements and apply all 4 operators
    for (int i = 0; i <= right; i++) {
        double temp = A[i];  // used for restoring value later

        for (int j = 0; j <= right; j++) {
            if (i==j) continue;

            for (int op = 0; op < 4; op++) {
                switch(op) {
                    case 0: A[i] += A[j]; break;
                    case 1: A[i] *= A[j]; break;
                    case 2: { if(A[j] <= 0) return false;
                                A[i] /= A[j]; break; }
                    case 3: A[i] -= A[j]; break;
                }

                swap(A,j,right);
                if(permute(A,right-1)) return true;

                // restore values
                swap(A,j,right);
                A[i] = temp;
            }
        }
    }
    return false;
}

在调试时，我添加了打印语句，对于每种情况，无论实际布尔值是对还是错，都打印了 9216 个数组，所以我知道迭代次数是正确的。我怀疑在内for循环中递归调用后恢复值时会发生错误。

允许兼容的附加方法int[]

static boolean make24(int[] A) {
    return permute(IntStream.of(A).mapToDouble(num -> num).toArray(), A.length-1);
}

最后，驱动方法：

public static void main(String[] args) {
    int[] a = new int[] {8,8,3,3};  
    System.out.println(make24(a));  // incorrectly returns false
}

其他可能有用的测试用例：

1,3,4,6 --> true
3,3,8,8 --> true
1,2,1,2 --> false
3,4,6,7 --> false
1,5,9,1 --> false

我已经尽力评论和解释了，不过分。我在这里要求很多，所以我不希望有很多回应，但感谢您阅读这篇文章！

编辑：从我发现的这个解决方案中，看来任意精度算术可能会导致一些错误。例如，代替return A[0] == 24;，做return Math.abs(A[0]-24) < 1e-8;。进行这些更改可以修复程序，因此实际的算法逻辑还可以：)

标签： javaarraysrecursionpermutation