24 点游戏Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。

你须遵守以下规则:

除法运算符 '/' 表示实数除法，而不是整数除法。
例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。
每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。
例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是不允许的。
你不能把数字串在一起
例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。

如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。

示例 1:

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

示例 2:

输入: cards = [1, 2, 1, 2]
输出: false

提示:

cards.length == 4
1 <= cards[i] <= 9

# 思路

dfs

# 解法


class Solution {
   
    boolean ok = false;
    public boolean dfs(ArrayList<Double> list){
        int n = list.size();
        if(n == 1){
            if(Math.abs(list.get(0)-24)<=1e-9){
                return true;
            }else{
                return false;
            }
        }
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                if(ok) break;
                double num1 = list.get(i);
                double num2 = list.get(j);
                ArrayList<Double> remain = new ArrayList<>();
                int index = 0;
                for(int k=0; k<n; k++){
                    if(k != i && k != j){
                        remain.add(list.get(k));
                    }
                }
                // 加
                remain.add(num1 + num2);
                ok |= dfs(remain);
                remain.remove(remain.size()-1);
                // 减
                remain.add(num1 - num2);
                ok |= dfs(remain);
                remain.remove(remain.size()-1);
                remain.add(num2 - num1);
                ok |= dfs(remain);
                remain.remove(remain.size()-1);
                // 乘
                remain.add(num2 * num1);
                ok |= dfs(remain);
                remain.remove(remain.size()-1);
                // 除
                if(num2 != 0.0){
                    remain.add(num1/num2);
                    ok |= dfs(remain);
                    remain.remove(remain.size()-1);
                }
                if(num1 != 0.0){
                    remain.add(num2/num1);
                    ok |= dfs(remain);
                    remain.remove(remain.size()-1);
                }
            }
        }
        return ok;
    }
    public boolean judgePoint24(int[] cards) {
        ArrayList<Double> remain = new ArrayList<>();
        for(int i=0; i<4; i++){
            remain.add(cards[i]*1.0);
        }
        dfs(remain);
        return ok;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

# 总结

分析出几种情况，然后分别对各个情况实现