LeetCode-24点游戏(每日一题)

题目描述

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

注意:

除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。

示例 1:

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

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

解法

1. 回溯

思路：这道题拿到手里我是一点想法都没有😑(太菜了)，直接看的官方题解。[其实这里也类似于DFS😮]

可以通过回溯的方法来遍历所有的不同可能性。具体做法是，使用一个列表储存所有数字，每次从列表中选出两个索引不同的数字，再选择一种运算操作，得到的数用来代替之前选的两个数，列表中的数字就减少1个。重复过程一直到列表只剩下一个数字，这个数字就是一种可能性结果。如果等于24，则可以通过运算得到24；如果所有可能结果都不等于24，则无法通过运算得到24。

注意

除法运算为实数运算，不是整数除法，需要先转换为double类型。此时判断是否等于24需要考虑到精度，这里误差小于$10^{-6}$即可认为相等。
加法和乘法都具有交换律，所以如果是这两种运算，可以不考虑选择元素的顺序，减小运算量。

import java.util.ArrayList;
import java.util.List;
class Solution {
    static final int TARGET = 24;
    static final double EPSILON = 1e-6;
    static final int ADD = 0, MULTIPLY = 1, SUBSTRACT = 2, DIVIDED = 3;

    public boolean judgePoint24(int[] nums) {
        // 建立集合，将数组中元素转换为double类型添加到集合中
        if (nums == null || nums.length == 0) return false;
        List<Double> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            list.add((double) nums[i]);
        }
        return solve(list);
    }

    private boolean solve(List<Double> list) {
        // if (list.size() == 0) return false;
        // 只剩一个数字，判断是否等于24
        if (list.size() == 1) return Math.abs(list.get(0) - TARGET) < EPSILON;
        // 选择两个数字，两个数字不能相同
        for (int i = 0; i < list.size(); i++) {
            for (int j = 0; j < list.size(); j++) {
                if (i != j) {
                    // 将集合中剩下的元素添加到新集合中
                    List<Double> list2 = new ArrayList<>();
                    for (int k = 0; k < list.size(); k++) {
                        if (k != i && k != j) list2.add(list.get(k));
                    }
                    // 分别对选择的两个数进行不同的运算操作
                    for (int method = 0; method < 4; method++) {
                        // 加法与乘法对顺序没有要求
                        if (method < 2 && i > j) continue;
                        if (method == ADD) {
                            list2.add(list.get(i) + list.get(j));
                        } else if (method == MULTIPLY) {
                            list2.add(list.get(i) * list.get(j));
                        } else if (method == SUBSTRACT) {
                            list2.add(list.get(i) - list.get(j));
                        } else if (method == DIVIDED) {
                            // 除法对0的判断
                            if (Math.abs(list.get(j)) < EPSILON) continue;
                            list2.add(list.get(i) / list.get(j));
                        }
                        // 对剩下的数组进行递归判断
                        if (solve(list2)) return true;
                        // 删除最后一个元素
                        list2.remove(list2.size() - 1);
                    }
                }
            }
        }
        return false;
    }
}