Luobuyu's Blog

0%

282.给表达式添加运算符

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.8k 阅读时长 ≈ 2 分钟
枚举接下来的数字长度，同时注意乘号的处理方法。

282.给表达式添加运算符

题目描述：

给出一个仅包含数字 $ 0-9 $ 的字符串 $ num $ 和一个目标值 $ target $ ，在 $ num $ 的数字之间添加二元运算符 $ +,-,* $ ，返回所有能够得到 $ target $ 的表达式。

注意，返回表达式中的操作数不应该包含前导零。

数据范围：
$ 1\le n \le 10,-2^{31}\le target \le 2^{31} - 1 $

题解：

首先容易想到，需要从 $ step $ 枚举下一个数字的长度。乘法最难处理，如果没有乘法，那么很容易就可以写出类似如下代码。

1
2
3
4
5
6
7
8
9
10
int val = 0;
for(int i = step; i < n; ++i)
{
    val = val * 10 + num[i] - '0';
    // 加号
    dfs(i + 1, cur_sum + val);
    // 减号
    dfs(i + 1, cur_sum - val);
    if(num[i] == '0' && i == step) break;
}

由于乘法的运算优先级比较高，需要先撤销上次的运算，也就是先减去，后加上相乘的结果。

设计函数

1
dfs(int step, ll cur_sum, ll last_sum, string &cur)

记录上一次运算的结果，如果遇到的是乘号

1
cur_sum - last_sum + last_sum * val

同时需要特别注意，如果枚举长度时遇到了 $ 0 $ ，如果 $ step=i \land num[i]=0 $ 处理完这一位之后直接退出。如果是连续的 $ 0 $ ，通过这样处理变成了多个单个的 $ 0 $ 。

类似表达式得到目标值题目：

[HNOI2003]24点游戏

代码：

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
class Solution
{
public:
#ifndef ll
#define ll long long
#endif
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    vector<string> ans;
    string op = "+-*";
    void dfs(int step, ll cur_sum, ll last_sum, string &cur, int &target, string &num)
    {
        if (step == num.length())
        {
            if (cur_sum == target)
                ans.emplace_back(cur);
            return;
        }
        int len = cur.size();
        if (step > 0)
            cur.push_back('+');
        int index = cur.size() - 1;
        ll val = 0;
        for (int i = step; i < num.size(); ++i)
        {
            val = val * 10 + (num[i] - '0');
            cur.push_back(num[i]);
            if (step == 0)
            {
                dfs(i + 1, cur_sum + val, val, cur, target, num);
            }
            else
            {
                cur[index] = '+';
                dfs(i + 1, cur_sum + val, val, cur, target, num);
                cur[index] = '-';
                dfs(i + 1, cur_sum - val, -val, cur, target, num);
                cur[index] = '*';
                dfs(i + 1, cur_sum - last_sum + last_sum * val, last_sum * val, cur, target, num);
            }
            if (i == step && num[i] == '0')
            {
                while (step + 1 < num.size() && num[step + 1] == num[step])
                    step++;
                break;
            }
        }
        cur.resize(len);
    }
    vector<string> addOperators(string num, int target)
    {
        string cur;
        dfs(0, 0, 0, cur, target, num);
        return ans;
    }
};