24 Game

week5

难度：Hard

题目链接

题目描述

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example1:


Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

Example2:


Input: [1, 2, 1, 2]
Output: False

Note:

1.The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

题目分析

  这道题目的意思很明显，就是要解决24点的问题，随机给出4个数，仅能用四则运算，若得到24点则输出正确，否则输出错误。

解题思路

  解决这道题一开始是使用穷举法，将所有的可能都列举出来，然后进行判断，但每一次运算只能减少一个数，而一开始有4个数，4个运算法则，而四则运算中，乘和加是和两个数顺序无关的，那么结果有$$C2_4*6*C2_36C^2_2*6 = 3888$$
种可能，有点多，不可能用代码都列出来。
  所以接下来考虑利用递归的方式，将每一种方法都遍历一遍，类似于深度搜索的方法，构成一棵树，根为4个数，每个分支代表一次运算，其子节点数的个数-1，因此树的高度为4，用深度遍历的原因是我们只需要把这个24点有无解输出就可以了，不需要输出解甚至所有的解，所以每次遍历都要达到高度4，以便最快得到一个解。
  采用递归的方式能够更好的遍历，当一个解不符合时，马上退回上一个状态，寻找下一个解，这里使用vector存储得到的解，当不符合时，弹出得到的运算数，回到上一状态。

代码

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
class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        vector<double> dnums;
        for(int val:nums)
        {
            dnums.push_back((double)val);
        }
        return dfs(dnums);
    }

    bool dfs(vector<double>& nums)
    {
        if(nums.size() == 0)
        {
            return false;
        }
        else if(nums.size() == 1)
        {
            return abs(nums[0] - 24) < 1e-6;
        }

        int size = nums.size();
        for(int i = 0; i < size; i++)
        {
            for(int j = 0; j < size; j++)
            {
                if(i == j)
                {
                    continue;
                }

                vector<double>card;
                for(int k = 0;k < size; k++)
                {
                    if(k != i && k != j)
                    {
                        card.push_back(nums[k]);
                    }
                }

                for(int l = 0; l < 4; l++)
                {
                    if(l == 0)
                    {
                        card.push_back(nums[i]+nums[j]);
                    }
                    else if(l == 1)
                    {
                        card.push_back(nums[i]*nums[j]);
                    }
                    else if(l == 2)
                    {
                        card.push_back(nums[i]-nums[j]);
                    }
                    else if(l == 3 && nums[j]!= 0)
                    {
                        card.push_back(nums[i]/nums[j]);
                    }

                    if(dfs(card))
                    {
                        return true;
                    }

                    card.pop_back();
                }
            }
        }
        return false;
    }
};

Note

  1. 因为所给的数的类型是int，因此在运算时要将其转成double类型方便进行乘除运算，否则会出现较大误差，并且判断是否为24点时因计算机的运算可能存在误差，所以要根据其和24点的误差小于一定值来判断。

  2. 因为在加减乘除中，加和乘对于数作为被加/乘数和加/乘数的结果是无影响的，因此，可以跳过2次运算，这样相当于每个节点原本8个子节点缩减为6个子节点，大大减少其分支，一开始以为没少多少，但是由于树高为4，算出的解能少3/4，极大减少时间。

  3. 加减乘除的顺序可以调转，也可以是先做加运算一直做到头，再做其它运算，也是可以的，但是个人觉得运算混搭可能会加快得到解的速度，即得到解的概率会大一些，单一进行运算很难得到24点。又由于其运算结果个数并不多，所以感觉使用启发式搜索并没有太大改进，判断时间可能使搜索时间变得更多。

总结

  思路主要是来源于题目写了一个tag为“depth-first search”让我有了一点思路，做这一些判断等题目，若是要进行所有结果的遍历，那么最好的方法就是进行搜索，搜索主要就是用到了树的遍历，即遍历状态。如果状态数过多，那么使用启发式搜索要比盲目搜索更好，而盲目搜索也要根据目的来确定，启发式搜索的难点就在于调参，确定一个搜索方向，而这道题因方向难以确定，而状态数不多，因此才采用深度搜索。