leetcode.679.24点游戏

679. 24 点游戏

给定一个长度为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
1
2
3

示例 2:

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

提示:

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

思路与代码

游戏的第一步是挑出两个数，算出一个新数替代这两个数。

然后，在三个数中玩 24 点，再挑出两个数，算出一个数替代它们。

然后，在两个数中玩 24 点……

很明显的递归思路。每次递归都会挑出两个数，我们尝试挑出不同的两数组合：

挑 1、2，基于它，继续递归。
挑 1、3，基于它，继续递归。
挑 ……
即通过两层 for 循环，枚举所有的两数组合，展开出不同选择所对应的递归分支。

java代码

    //回溯枚举 + 部分剪枝优化
    static final int TARGET = 24;
    //误差
    static final double EPSILON = 1e-6;
    //加、乘、减、除
    static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;

    public boolean judgePoint24(int[] nums) {
        //4个数入list
        List<Double> list = new ArrayList<Double>();
        for (int num : nums) {
            list.add((double) num);
        }
        return solve(list);
    }

    public boolean solve(List<Double> list) {
        if (list.size() == 0) {
            return false;
        }
        //算完后只剩一个数，即结果，误差在可接受范围内判true
        if (list.size() == 1) {
            return Math.abs(list.get(0) - TARGET) < EPSILON;
        }
        int size = list.size();
        //list里挑出一个数
        for (int i = 0; i < size; i++) {
            //再挑一个，做运算
            for (int j = 0; j < size; j++) {
                //不能挑一样的
                if (i != j) {
                    //没被挑到的扔进list2
                    List<Double> list2 = new ArrayList<Double>();
                    for (int k = 0; k < size; k++) {
                        if (k != i && k != j) {
                            list2.add(list.get(k));
                        }
                    }
                    //四种运算挑一个，算完的结果加到list2里做第三个数
                    for (int k = 0; k < 4; k++) {
                        //k < 2是指，所挑运算为加或乘
                        //i > j是为了判定交换律的成立，如果i < j,说明是第一次做加或乘运算
                        //eg: i = 0, j = 1, k = 1 → 挑第一个和第二个数，两数相乘
                        //    i = 1, j = 0, k = 1 → 挑第二个和第一个数，两数相乘  →  无效的重复计算
                        if (k < 2 && i > j) {
                            continue;
                        }
                        //加
                        if (k == ADD) {
                            list2.add(list.get(i) + list.get(j));
                            //乘
                        } else if (k == MULTIPLY) {
                            list2.add(list.get(i) * list.get(j));
                            //减
                        } else if (k == SUBTRACT) {
                            list2.add(list.get(i) - list.get(j));
                            //除
                        } else if (k == DIVIDE) {
                            //如果除数等于0，直接判这次所挑选的运算为false，跳出此次循环
                            if (Math.abs(list.get(j)) < EPSILON) {
                                continue;
                            } else {
                                list2.add(list.get(i) / list.get(j));
                            }
                        }
                        //至此已经由4→3，进入下一层由3→2的过程，依次类推
                        if (solve(list2)) {
                            return true;
                        }
                        //没凑成24就把加到list2末尾的结果数删掉，考虑下种运算可能
                        list2.remove(list2.size() - 1);
                    }
                }
            }
        }
        return false;
    }
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
65
66
67
68
69
70
71
72
73
74
75
76
77

cpp代码

//每次随机取两个数计算（+-*/）放回，直到剩一个结果
class Solution {
public:
    bool judgePoint24(vector<int>& cards) {
        vector<double> tmp(cards.begin(),cards.end());  //转double
        return fun(tmp);
    }
    bool fun(vector<double>& cards){
        if(cards.size()==1) {
            return abs(cards[0]-24)<0.000001;           //double不能和整数直接比较，小数在计算机里有误差  
        }
        for(int i=0;i<cards.size();i++){                //随机选取两个数字；
            for(int j=0;j<cards.size();j++){
                if(i==j) continue;
                vector<double> vec;
                for(int k=0;k<cards.size();k++){        //加入除了i、j以外的元素
                    if(k!=i && k!=j) vec.push_back(cards[k]);
                }
                vec.push_back(cards[i]+cards[j]);       //加
                if(fun(vec)) return true;
                vec.pop_back();

                vec.push_back(cards[i]-cards[j]);       //减
                if(fun(vec)) return true;
                vec.pop_back();

                vec.push_back(cards[i]*cards[j]);       //乘
                if(fun(vec)) return true;
                vec.pop_back();

                vec.push_back(cards[i]/cards[j]);       //除
                if(fun(vec)) return true;
            }
        }
        return false;
    }
};
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

cpp代码2

class Solution {
public:
vector<double> cards;
bool helper(vector<double> cards){
    int N = cards.size();
    if(N==1&&abs(cards[0]-24)>10e-6) return false;
    if(N==1&&abs(cards[0]-24)<=10e-6) return true;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(i==j)continue; //选两个不同的数
            double a = cards[i];
            double b = cards[j];
            vector<double> newcards;
            for(int k=0;k<N;k++){
                if(k==i||k==j) continue;//将未选数推入新数组。
                newcards.push_back(cards[k]);
            }

			//加、乘、减、除
            double sum = a + b;
            double sub = a - b;
            double mul = a * b;
            double div = a / b;//四则运算
            double newcard[4]={sum,sub,mul,div};
            for(int m=0;m<4;m++){            
                newcards.push_back(newcard[m]);
                if(helper(newcards)) return true;
                newcards.pop_back();
            }
        }
    }
    return false;


}

    bool judgePoint24(vector<int>& _cards) {
        for(int i=0;i<_cards.size();i++){
            cards.push_back(_cards[i]*1.0);
        }
        return helper(cards);
    }
    
};
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

参考

24点游戏