算法leetcode

【搜索难题】力扣282-给表达式添加运算符

字数统计: 1.4k字   |   阅读时长: 6分
,

摘要:

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

本文看一个复杂的搜索题。亮点在于在 DFS 的过程中维护复杂的状态信息：用类似单调栈的逻辑维护表达式符号和值。

$1 题目

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

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

示例 1:
输入: num = “123”, target = 6
输出: [“1+2+3”, “123”]
解释: “123” 和 “1+2+3” 的值都是6。

示例 2:
输入: num = “232”, target = 8
输出: [“23+2”, “2+32”]
解释: “23+2” 和 “2+32” 的值都是8。

示例 3:
输入: num = “3456237490”, target = 9191
输出: []
解释: 表达式 “3456237490” 无法得到 9191 。

提示：

1
2
3
1 <= num.length <= 10
num 仅含数字
-2^31 <= target <= 2^31 - 1

$2 题解

算法：DFS

串长为 n，共有 n - 1 个间隔可以放符号(0~n-2)，符号可以选 +,-,*，空格，空格表示不放符号。

枚举所有可以放符号的位置 pos=0~n-2，然后枚举四中可能的符号 +,-,*，空格，当 pos=n-1 时，为一种放置符号的方案，计算结果并更新答案。

状态设计

状态需要包含两个信息，一个是当前位置 pos，另一个是搜索路径 [0~pos] 上的计算结果。

难点在于不能单纯维护一个 [0, pos] 上的计算结果，考虑两种情况：

  • 第一种：当前状态在转移的时候使用的符号是乘号，而搜索路径中上一个符号是加号，因为乘法优先级比加法高，因此将整个 [0,pos] 上的计算结果参与到状态转移的计算中是错的。

为了应对第一种情况，需要维护 [0~pos] 中离 pos 最近的 +/- 以及在该 +/- 之前的计算结果 num1。

  • 第二种，当前状态在转移的时候使用的符号是空格，即不加符号，则上一个符号即使是乘号，也要记录，因为乘号后面可能有尚未参与计算的部分(称为活动数字)。

例如 “578938” 枚举到 pos = 4，此前的搜索路径是 "578*93" 若此时选择空格转移，则 [0~5] 的计算，搜索路径是 "578*938"，乘法后面的 93 是需要记录的状态，有了这个状态才能正确得到当前最右数字为 938。

状态中用两个栈维护符号和夹在符号间的值。其中一个符号栈，一个值栈。

符号栈中最多有两个值，如果上一个符号为 +/- 则栈里只有一个 +/-，如果上一个符号是 * ，则栈的 size 为 2，栈底是最近的 +/-，栈顶是最近的 * 。

值栈中最多有 3 个值，分别对饮符号栈中的符号两侧的值。

分别记这五个值为 op1, op2, num1, num2, num3。

此外还需要一个标志 zero 记录当前活动数字是否为 0，只有活动数字不为零时，状态转移的时候才能选空格，因为数字不能有前导零。

1
2
3
4
op1 = 1: 加法
op1 = 2: 减法
op2 = 1: 乘A, num3 为活动数字
op2 = 0: 无乘法, nums2 为活动数字

在 DFS 过程中可以直接带着这五个值，不用单独开栈来保存。

状态的转移

下一个符号为 op：

1
2
3
4
op为空格: 更新活动数字，递归到 pos + 1
op为乘号: 处理栈里的乘号，更新活动数字，递归到 pos + 1
op为加号: 处理栈里的乘号和加减号，更新活动数字，递归到 pos + 1
op为减号: 处理栈里的乘号和加减号，更新活动数字，递归到 pos + 1

搜索刚开始时，视为 0 + ...，即起始时的数字为 0，并且后面跟着 + 号。这样做之后，num1 始终不会是活动数字，对后续写代码有利。

代码 (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
class Solution {
public:
    vector<string> addOperators(string num, int target) {
        if(num.empty()) return vector<string>();
        vector<string> result;
        string item;
        item += num[0];
        int new_num = num[0] - '0';
        bool zero = num[0] == '0';
        dfs(num, 0, target, item, result, 0, new_num, 0, 1, 0, zero);
        return result;
    }

private:
    using ll = long long;

    void dfs(const string& num, int pos, int target, string& item, vector<string>& result,
            ll num1, ll num2, ll num3, int op1, int op2, bool zero)
    {
        // num[pos] 已经加入 item
        // op1 = 1: 加法
        // op1 = 2: 减法
        // op2 = 1: 乘A, num3 为活动数字
        // op2 = 0: 无乘法, nums2 为活动数字
        int n = num.size();
        if(pos == n - 1)
        {
            if(op2)
                num2 *= num3;
            if(op1 == 1)
                num1 += num2;
            else
                num1 -= num2;
            if(num1 == target)
                result.push_back(item);
            return;
        }

        // num[pos] 与 num[pos+1] 之间可能是 空格, +, - , *
        ++pos;
        int new_num = num[pos] - '0';
        bool new_zero = new_num == 0;
        // 1. 空格
        if(!zero) // 活动数字不为 0 , 才可以根空格
        {
            item += num[pos];
            if(op2)
                dfs(num, pos, target, item, result, num1, num2, num3 * 10 + new_num, op1, op2, zero);
            else
                dfs(num, pos, target, item, result, num1, num2 * 10 + new_num, num3, op1, op2, zero);
            item.pop_back();
        }
        // *, +, 或 -
        // 无论是*,+,-,栈里有乘号都必须先处理
        if(op2)
            num2 *= num3;
        // 2. *
        item += '*';
        item += num[pos];
        dfs(num, pos, target, item, result, num1, num2, new_num, op1, 1, new_zero);
        item.pop_back();
        item.pop_back();
        // 无论是+,-,栈里的+/-都必须先处理
        if(op1 == 1)
            num1 += num2;
        else if(op1 == 2)
            num1 -= num2;
        // 3. +
        item += '+';
        item += num[pos];
        dfs(num, pos, target, item, result, num1, new_num, 0, 1, 0, new_zero);
        item.pop_back();
        item.pop_back();
        // 4. -
        item += '-';
        item += num[pos];
        dfs(num, pos, target, item, result, num1, new_num, 0, 2, 0, new_zero);
        item.pop_back();
        item.pop_back();
    }
};
Share