By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、24点游戏

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。

注意:

1、除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。

2、每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。

3、你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。

示例 1:

输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24

示例 2:

输入: [1, 2, 1, 2]
输出: False

1.1、解题思路

1、将4个数字全排列，一共应该有 4 * 3 * 2 * 1 = 24种

2、然后将这24中依次进行判断

1.2、算法

public boolean judgePoint24(int[] nums) {
    boolean flag = false;
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    //1、获取全排列数据
    dsf(nums, res, new LinkedList<>(), used);


    //2、讲全排列的每组进行判断
    for (List<Integer> list : res){
        flag =  judge(list.get(0),list.get(1),list.get(2),list.get(3) );
        if(flag){
            return true;
        }
    }
    return flag;
}

/** 求出全排列数据 */
public void dsf(int[] nums, List<List<Integer>> res , LinkedList<Integer> linkedList, boolean[] used) {
    if (linkedList.size() == 4) {
        res.add(new ArrayList<>(linkedList));
    }
    for (int i = 0; i < 4; i++) {
        if (used[i]){
            continue;
        }
        used[i] = true;
        linkedList.add(nums[i]);
        dsf(nums, res, linkedList, used);
        linkedList.removeLast();
        used[i] = false;
    }
}

// 第二步：由于已经全排列，a、b、c、d 都是等价的，利用四种运算符选出三个数继续
public boolean judge(double a, double b, double c, double d) {
    return judge(a + b, c, d) ||
        judge(a - b, c, d) ||
        judge(a * b, c, d) ||
        judge(a / b, c, d);
}

// 第三步：a 是由两个数组成的，b、c 只表示一个数；a 与 b、c 不等价，b、c 等价
public boolean judge(double a, double b, double c) {
    // 情况一：a 和 b(c) 组合，a 和 b(c) 不等价， (不等价的有8中组合方式，其中两种是重复的)
    return judge(a + b, c) ||
        judge(a - b, c) ||
        judge(a * b, c) ||
        judge(a / b, c) ||
        // judge(b + a, c) || 其实和上面是重复的
        // judge(b * a, c) ||  其实和上面是重复的
        judge(b - a, c) ||
        judge(b / a, c) ||

        // 情况二：b 和 c 组合 (b和c是等价的)
        judge(a, b + c) ||
        judge(a, b - c) ||
        judge(a, b * c) ||
        judge(a, b / c);
}

// 第四步：a 和 b 不等价
public boolean judge(double a, double b) {
    return Math.abs(a + b - 24) < 0.001 ||
        Math.abs(a - b - 24) < 0.001 ||
        Math.abs(a * b - 24) < 0.001 ||
        Math.abs(a / b - 24) < 0.001 ||
        // Math.abs(b + a - 24) < 0.001 || 其实和上面 Math.abs(a + b - 24) < 0.001 || 是重复的
        // Math.abs(b * a - 24) < 0.001 || 其实和上面  Math.abs(a * b - 24) < 0.001 ||是重复的
        Math.abs(b - a - 24) < 0.001 ||
        Math.abs(b / a - 24) < 0.001;
}

1.3、测试

@Test
public void test() {
    int[] nums = {4, 1, 8, 7};
    System.out.println(judgePoint24(nums));
}

​

ContactAuthor