算法leetcode

【搜索难题】力扣679-24点游戏

字数统计: 2.7k字   |   阅读时长: 11分
,

摘要: 最经典的 24 点判定问题。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，1024 快到了，各公司的程序员的活动也都出来了，力扣也不例外，出了一个参与感还挺强的活动。不过活动说明可能需要仔细看看，我也是看了很久才看懂在说什么。

活动页面中，首先讲了一个马尔可夫链的故事，然后展开了游戏的规则。先介绍马尔可夫链的原因是游戏规则与马尔可夫链的【未来只依赖于现在，而与过去无关】性质有关。

下面我们看一下游戏规则：

  • 用 7 张牌进行 3 次运算，其中每次运算需使用 2 张 数字牌 和 1 张 运算符号牌。
  • 每次运算后都将根据上一次的运算结果生成一张数字牌。最后一次运算结果刚好等于 1024 时记为「成功」。
  • 需要注意的是，在完成 3 次运算前，每次运算操作都是不可撤销的。

简单来说就是你有 10 张牌，其中 7 张数字牌，3 张符号牌，然后判定这一组牌能否在三次运算完成后得到 1024，这三次运算刚好对应你手上的 3 张符号牌。

为了完成这个任务，我们要做的是写一个程序，输入当前的手牌，判断能否得到 1024，如果能得到 1024，就返回运算步骤。然后一边攒牌一边判定，直到判定成功。

因此我们要解决两件事，第一件事是攒牌，第二件事是写一个判定程序。获得牌的规则如下：

  • 你可以通过每日做题 AC，随机获得 1 张 「数字牌」，通过此方法每天最多可以获得 3 张 数字牌。
  • 以登录状态访问活动页面，可以随机获得 1 张 「运算符号牌」，通过此方法每天最多可以获得 1 张 运算符号牌。
  • 访问其他人的卡牌分享链接，可以获得对应被分享卡牌牌面的卡牌，通过此方法每天最多可以获得 3 张任意类型卡牌。需要注意的是，每张被分享的卡牌最多可以领取 3 次，先到先得。

攒牌这块简单来说就是每天以登录状态访问一下活动页面，拿一张符号牌，通过一道题，拿一张数字牌即可。下图是我目前的牌。

理解完题意，我们发现很多人都已经计算成功了，前十名如下图，我们看一下他们的合成步骤参考一下。

下面就剩下了判定程序怎么写，本文我们先看一个简化版的问题，力扣 679 题，24 点判定。这个问题的设定是手上有 4 张数字牌，符号牌有 +, -, * , / ，并且符号牌不限量。

$1 题目

题目链接

679. 24 点游戏

题目描述

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

样例

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

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

1
2
3
4
5
注意:

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

$2 题解

算法: DFS

整体的算法流程是枚举 4 个数字所有的排列，枚举 3 个缝隙所有的符号排列，枚举 3 个缝隙的计算顺序。然后判断所得是否为 24。

枚举数字排列

对于 C++ 来说，我们可以先把 nums 排序，然后执行一次 next_permutation 即可完成一次枚举。代码如下：

1
2
3
4
5
sort(nums.begin(), nums.end());
do{
    // 在一定的数字排列下，完成后续枚举
}
while(next_permutation(nums.begin(), nums.end()));

枚举符号排列

由于符号不限量，所以对 3 个位置都枚举所有的符号即可。代码如下：

1
2
3
4
5
for(int op = 1; op <= 4; ++op)
{
    ops[pos] = op;
    // 在一定的数字排列、符号排列下，完成后续枚举
}

其中 ops 是 3 维的数组，代表 3 个符号位置。对于位置 pos，ops[pos] 有 1~4 这 4 种取值，每种取值代表一种符号。

枚举计算顺序

数字排列、符号排列都有了，下一步就要枚举计算顺序。由于数字不多，我们可以手动把所有可能的计算顺序先记录下来，如下：

1
2
3
4
5
6
7
int order[5][3] = {
    {0, 1, 2},
    {0, 2, 1},
    {1, 0, 2},
    {1, 2, 0},
    {2, 1, 0}
};

例如 0, 1, 2 表示先执行第 0 个符号代表的运算，再执行第 0 个符号代表的运算，最后执行第 2 个符号代表的运算。

注意 0, 2, 1 和 2, 0, 1 是一样的，这里优化掉了，因此总共有五种顺序。

然后我们枚举 order，即可得到代表当前枚举到的顺序。代码如下，ord 为当前的计算顺序。

1
2
3
4
5
6
7
for(int i = 0; i < 5; ++i)
{
    int ord[3];
    for(int j = 0; j < 3; ++j)
        ord[j] = order[i][j];
    // 在一定的数字排列、符号排列、计算顺序下，执行计算
}

执行计算

计算过程就是枚举步骤，这里就是枚举 0 到 2。

对于每一步计算，先取出当前步骤要计算的符号，符号左边的数字，符号右边的数字。然后判断一下是否是除以零。然后完成当前步的计算。

具体见下面的代码，其中 fracs 是按当前枚举到的数字顺序排列的数字数组，ops 为按当前枚举到的符号顺序排列的符号数组。pos = ord[i] 为第 i 步要执行的运算符号在 ops 中的下标，同时也是左操作数在 fracs 中的下标，pos + 1 为右操作数在 fracs 中的下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(int i = 0; i < 3; ++i)
{
    int pos = ord[i];
    int op = ops[pos];
    Frac left = fracs[pos];
    Frac right = fracs[pos + 1];
    if(op == 4 && right() == 0)
        continue;
    Frac middle = calc(left, right, op);
    fracs[pos] = middle;
    fracs.erase(fracs.begin() + pos + 1);
    ops.erase(ops.begin() + pos);
    for(int j = i + 1; j < 3; ++j)
        if(ord[j] > ord[i])
            --ord[j];
}

其中 calc 为完成具体的一步计算的函数。

完成当前步的计算后，将数字更新回 fracs，在 fracs，ops 中删除已完成计算的符号，以及右操作数。然后将 ord 数组中的数字减 1，使的 pos=ord[i] 可以定位到 fracs, ops 更新之前的元素

判定

在一定的数字排列、符号排列和计算顺序下完成计算后，判定是否为 24 时，除法需要是保留小数的，例如 4 / (1 - 2/3) 的结果应该是 12。

有两种办法实现：

  1. 实现分数类并重载 +, -, *, /，作为中间结果的类型
  2. 将所有中间结果直接用 double 维护，最后所得在一定精度下为 24 则命中

这里我们采用第一种方法，实现分数类，每个数字都用一个分子和分母表示，然后重载所需要的运算符。此外重载 ()，将分数转换为整数除法的结果。

1
2
3
4
5
6
7
8
9
10
struct Frac
{
    int a, b;
    Frac(int a=0, int b=1):a(a),b(b){}
    int operator()() {}
    Frac operator+(const Frac& f) const {}
    Frac operator-(const Frac& f) const {}
    Frac operator*(const Frac& f) const {}
    Frac operator/(const Frac& f) const {}
};

具体的一次计算

在具体的一次计算中，根据 op 的值，对 left 和 right 两个数做相应的计算即可。

1
2
3
4
5
6
7
8
9
10
11
12
Frac calc(Frac left, Frac right, int op)
{
    // 执行具体的一次计算
    if(op == 1)
        return left + right;
    else if(op == 2)
        return left - right;
    else if(op == 3)
        return left * right;
    else
        return left / right;
}

代码 (C++)

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
struct Frac
{
    // a / b
    // 使用方要保证 b != 0
    int a, b;
    int operator()()
    {
        if(b == 0) return -1;
        if(a == 0) return 0;
        if(a % b != 0) return -1;
        return a / b;
    }
    Frac(int a=0, int b=1):a(a),b(b){}
    Frac operator+(const Frac& f) const
    {
        Frac res(a, b);
        if(b == f.b)
            res.a += f.a;
        else
        {
            res.b *= f.b;
            res.a *= f.b;
            res.a += f.a * b;
        }
        return res;
    }
    Frac operator-(const Frac& f) const
    {
        Frac res(a, b);
        if(b == f.b)
            res.a -= f.a;
        else
        {
            res.b *= f.b;
            res.a *= f.b;
            res.a -= f.a * b;
        }
        return res;
    }
    Frac operator*(const Frac& f) const
    {
        Frac res(a, b);
        res.a = a * f.a;
        res.b = b * f.b;
        return res;
    }
    Frac operator/(const Frac& f) const
    {
        Frac res(a, b);
        res.a = a * f.b;
        res.b = b * f.a;
        return res;
    }
};

class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        vector<int> ops(3, -1);
        // 3 个符号位置，每个位置上可能有 4 中选择，ops[i] :
        // 1: +
        // 2: -
        // 3: *
        // 4: /
        sort(nums.begin(), nums.end());
        do{
            // 枚举数字排列
            if(dfs(nums, 0, ops))
                return true;
        }
        while(next_permutation(nums.begin(), nums.end()));
        return false;
    }

private:
    int order[5][3] = {
        {0, 1, 2},
        {0, 2, 1},
        {1, 0, 2},
        {1, 2, 0},
        {2, 1, 0}
    };

    bool dfs(const vector<int>& nums, int pos, vector<int>& ops)
    {
        int n = nums.size();
        if(pos == n - 1)
        {
            return check(nums, ops);
        }
        // 在一定的数字顺序下，枚举符号排列
        for(int op = 1; op <= 4; ++op)
        {
            ops[pos] = op;
            if(dfs(nums, pos + 1, ops))
                return true;
        }
        return false;
    }

    bool check(const vector<int>& nums, const vector<int>& ops)
    {
        vector<Frac> fracs;
        for(int i: nums)
            fracs.push_back(Frac(i, 1));
        // 在一定的数字排列和符号排列下，枚举计算顺序
        for(int i = 0; i < 5; ++i)
        {
            int ord[3];
            for(int j = 0; j < 3; ++j)
                ord[j] = order[i][j];
            if(_check(fracs, ops, ord))
                return true;
        }
        return false;
    }

    bool _check(vector<Frac> fracs, vector<int> ops, int ord[])
    {
        // 在一定的数字排列、符号排列，计算顺序下，执行计算
        for(int i = 0; i < 3; ++i)
        {
            int pos = ord[i];
            int op = ops[pos];
            Frac left = fracs[pos];
            Frac right = fracs[pos + 1];
            if(op == 4 && right() == 0)
                continue;
            Frac middle = calc(left, right, op);
            fracs[pos] = middle;
            fracs.erase(fracs.begin() + pos + 1);
            ops.erase(ops.begin() + pos);
            for(int j = i + 1; j < 3; ++j)
                if(ord[j] > ord[i])
                    --ord[j];
        }
        int ans = fracs[0]();
        return ans == 24;
    }

    Frac calc(Frac left, Frac right, int op)
    {
        // 执行具体的一次计算
        if(op == 1)
            return left + right;
        else if(op == 2)
            return left - right;
        else if(op == 3)
            return left * right;
        else
            return left / right;
    }
};
Share