0%

leetcode每日一题-24点游戏

Posted on In ,

24点游戏

image1

##方法一：回溯

可以通过回溯的方法遍历所有不同的可能性。具体做法是，使用一个列表存储目前的全部数字，每次从列表中选出 2 个数字，再选择一种运算操作，用计算得到的结果取代选出的 2 个数字，这样列表中的数字就减少了 1 个。重复上述步骤，直到列表中只剩下 1 个数字，这个数字就是一种可能性的结果，如果结果等于 24，则说明可以通过运算得到 24。如果某一种可能无法得到等于24的结果，那么就进行回溯，具体做法是把之前计算得到的结果从列表中移除，然后进行下一轮搜索。如果所有的可能性的结果都不等于 24，则说明无法通过运算得到 24。

实现时，有一些细节需要注意。

  • 除法运算为实数除法，因此结果为浮点数，列表中存储的数字也都是浮点数。在判断结果是否等于 2424 时应考虑精度误差，这道题中，误差小于 $10^{-6}$可以认为是相等。

  • 进行除法运算时，除数不能为 0，如果遇到除数为 0 的情况，则这种可能性可以直接排除。由于列表中存储的数字是浮点数，因此判断除数是否为 0 时应考虑精度误差，这道题中，当一个数字的绝对值小于 $10^{-6}$时，可以认为该数字等于 0。

还有一个可以优化的点。加法和乘法都满足交换律，因此如果选择的运算操作是加法或乘法，则对于选出的 2 个数字不需要考虑不同的顺序，在遇到第二种顺序时可以不进行运算，直接跳过。

1
class Solution {
2
    public static final double EPSILON = 1e-6;
3
    public static final int ADD = 0;
4
    public static final int MUL = 1;
5
    public static final int SUB = 2;
6
    public static final int DIV = 3;
7
    public static final int TARGET = 24;
8
    public boolean judgePoint24(int[] nums) {
9
        List<Double> list = new ArrayList<Double>();
10
        for(int num : nums){
11
            list.add((double)num);
12
        }
13
        return solve(list);
14
    }
15
16
    public boolean solve(List<Double> list){
17
        if(list.size() == 0){
18
            return false;
19
        }
20
        if(list.size() == 1){
21
            //判断是否满足24点
22
            return Math.abs(list.get(0)-TARGET)<EPSILON;
23
        }
24
        int size = list.size();
25
        for(int i=0; i<size; i++){
26
            for(int j=0; j<size; j++){
27
                if(i != j){
28
                    List<Double> list2 = new ArrayList<Double>();
29
                    for(int k=0; k<size; k++){
30
                        if(k!=i && k!=j){
31
                            list2.add(list.get(k));
32
                        }
33
                    }
34
                    for(int k=0; k<4; k++){
35
                        //加法和乘法满足交换律
36
                        if(i>j && k<2){
37
                            continue;
38
                        }
39
                        double num1 = list.get(i);
40
                        double num2 = list.get(j);
41
                        if(k == 0){
42
                            list2.add(num1 + num2);
43
                        }else if(k == 1){
44
                            list2.add(num1 * num2);
45
                        }else if(k == 2){
46
                            list2.add(num1 - num2);
47
                        }else if(k == 3){
48
                            if(num2 < EPSILON){
49
                                continue;
50
                            }else{
51
                                list2.add(num1 / num2);
52
                            }
53
                        }
54
                        if(solve(list2)){
55
                            return true;
56
                        }
57
                        //回溯，进入另一个循环继续搜索
58
                        list2.remove(list2.size()-1);
59
                    }
60
                }
61
            }
62
        }
63
        return false;
64
    }
65
}

复杂度分析：

  • 时间复杂度：$O(1)$
  • 空间复杂度：$O(1)$