本文涉及知识点
回溯 栈 代数系统 动态规划
LeetCode 282. 给表达式添加运算符
给定一个仅包含数字 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 <= num.length <= 10
num 仅含数字
-231 <= target <= 231 - 1
分析
n = num.length,
∀
i
∈
[
0
,
n
−
1
)
有四种可能：
+
−
∗
任何都不加
\forall i \in [0,n-1) 有四种可能：+ - * 任何都不加
∀i∈[0,n−1)有四种可能：+−∗任何都不加，比如：12，有以下四种可能:1+2 1
×
\times
× 2 1-2 12。
可能数为：O(4n-1)由于n-1最多为9，所以< 4 9
≈
\approx
≈ 410/4
n等于10时，会超过int的表示范围，所以需要long long。
回溯 + 栈
通过回溯枚举所有的可能，然后利用栈计算表达式。
代数系统
nums[0…i]的某种状态的结果为：{ch,ll1,ll2,ll3}
ch ：最后一个运算符，+ -
×
\times
× 空格表示没有运算符。
ll1是这种状态的结果。
ll2只对乘法有效果，和最和一个数相乘的积。
ll3为最后一个数。
如：1 +2
×
\times
× 3
×
\times
× 4 的 结果为{*,25,6,4}
ch为空格
新运算为ch1，nums[i+1]为x
| 空格 | {‘ ’，ll1*10+x,0,0} |
| + | {‘+’,ll1+x,0,x} |
| - | {‘-’,ll1-x,0,x} |
| * | {'',ll1x,ll1,x} |
情况太复杂，懒的枚举。其本质上是利用了实数集 S 和运算符 +（- 的本质也是 +）和 * 能够组成代数系统。利用代数系统 (S,+,∗)，我们可以确保运算过程中的任意一个中间结果，都能使用形如 a + b
×
\times
× c 的形式进行表示，因此我们只需要多维护一个后缀串结果即可。
下面来证明：
初始状态为合法的代数系统：{0,1,nums[0]}。
令nums[0…i]的某合法状态为{a,b,c}，则以下四种操作，都是合法状态：
直接拼接：{a,b,c*10+x}
加法：{a+b
×
\times
×c,1,x}
减法：{a+b
×
\times
×c,-1,x}
乘法：{a,b
×
\times
× c,x}
不能有前导0，如果nums[i]为0，则nums[i]和nums[i+1]无法拼接。
区间动态规划
动态规划的状态表示
dp[i][j] 记录nums[i…j]所有可能的结果。
动态规划的状态方程
dp[i][j] +=
F
o
r
k
=
i
j
−
1
F
o
r
x
:
∈
d
p
[
i
]
[
k
]
F
o
r
y
:
∈
d
p
[
k
+
1
]
[
j
]
D
o
(
x
,
y
)
\Large For_{k=i}^{j-1}For_{x:\in dp[i][k]}For_{y:\in dp[k+1][j]}Do(x,y)
Fork=ij−1Forx:∈dp[i][k]Fory:∈dp[k+1][j]Do(x,y)
Do(x,y)包括：
x$\times$10len(y)+y
x+y
x-y
x
×
\times
×y
动态规划的初始值
dp[i][i] = {nums[i]}
动态规划的填表顺序
长度(j-i+1) 2 → \rightarrow → n，i:0 → \rightarrow →i-1。
动态规划的返回值
dp[0][n-1].count(target)
注意：
还需要记录各值的计算过程，同一个值可能有多个计算方法。
代数系统代码
核心代码
class Solution {
public:
vector<string> addOperators(string num, int target) {
vector<char> ope;
vector<string> vRet;
std::function<void(long long, long long, long long)> BackTrack = [&](long long a, long long b, long long c) {
if (ope.size() + 1 == num.length()) {
long long res = a + b * c;
if (target == res) {
string cur;
for (int i = 0; i < ope.size(); i++) {
cur += num[i];
if (0 != ope[i]) { cur += ope[i]; }
}
cur += num.back();
vRet.emplace_back(cur);
}
return;
}
long long x = num[ope.size() + 1]-'0';
ope.emplace_back('*');
BackTrack(a, b * c, x);
ope.pop_back();
ope.emplace_back('+');
BackTrack(a+b*c, 1, x);
ope.pop_back();
ope.emplace_back('-');
BackTrack(a + b * c, -1, x);
ope.pop_back();
if(0 != c ){
ope.emplace_back('\0');
BackTrack(a,b,c*10+x);
ope.pop_back();
}
};
BackTrack(0, 1, num[0]-'0');
return vRet;
}
};
- 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
测试用例
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}
template<class T>
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
int main()
{
string num;
int target;
{
Solution slu;
num = "00", target = 0;
auto res = slu.addOperators(num, target);
Assert({ "0*0","0+0","0-0" }, res);
}
{
Solution slu;
num = "123", target = 6;
auto res = slu.addOperators(num, target);
Assert({"1*2*3", "1+2+3" }, res);
}
{
Solution slu;
num = "232", target = 8;
auto res = slu.addOperators(num, target);
Assert({ "2*3+2", "2+3*2" }, res);
}
{
Solution slu;
num = "3456237490", target = 9191;
auto res = slu.addOperators(num, target);
Assert({ }, res);
}
{
Solution slu;
num = "010", target = 0;
auto res = slu.addOperators(num, target);
Assert({ "0*1*0","0*1+0","0*1-0","0*10","0+1*0","0-1*0" }, res);
}
}
- 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
2023年5月版也是代数系统
class Solution {
public:
vector<string> addOperators(string num, int target) {
std::unordered_map < string, std::tuple< long long, long long, long long >> preValueMulValue;
preValueMulValue.emplace(std::string("") + num[0], std::make_tuple(num[0] - '0', num[0] - '0', num[0] - '0'));
for (int i = 1; i < num.size(); i++)
{
const char& ch = num[i];
const int iBit = num[i] - '0';
std::unordered_map < string, std::tuple< long long, long long, long long >> valueMulValue;
for (const auto& it1 : preValueMulValue)
{
const long long& iValue = std::get<0>(it1.second);
const long long& iMul = std::get<1>(it1.second);
const long long& iEnd = std::get<2>(it1.second);
const long long iMulPre = (0 == iEnd) ? 0 : iMul / iEnd;
//不加符号
if ((0 != iEnd) )
{
valueMulValue.emplace(it1.first + ch, std::make_tuple(iValue + iMulPre * (iEnd * 9 + iBit), iMulPre * (iEnd * 10 + iBit), iEnd * 10 + iBit));
}
//增加加号
valueMulValue.emplace(it1.first + '+' + ch, std::make_tuple(iValue + iBit,iBit,iBit));
//增加减号
valueMulValue.emplace(it1.first + '-' + ch, std::make_tuple(iValue - iBit, -iBit, iBit));
//增加乘号
valueMulValue.emplace(it1.first + '*' + ch, std::make_tuple(iValue + iMul*(iBit - 1), iMul*iBit,iBit));
}
preValueMulValue.swap(valueMulValue);
}
vector<string> vRet;
for (const auto& it1 : preValueMulValue)
{
if (target == std::get<0>( it1.second))
{
vRet.emplace_back(it1.first);
}
}
return vRet;
}
};
- 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
2023年8月版 也是代数系统
class Solution {
public:
vector addOperators(string num, int target) {
m_strNum = num;
m_iTarget = target;
const auto& iBit = num.front() - ‘0’;
dfs(num.substr(0, 1),1, iBit, iBit, iBit);
return m_vRet;
}
void dfs(string exp, int hasDo,const long long llValue, long long endMulValue,long long endValue)
{
if (hasDo == m_strNum.length())
{
if (llValue == m_iTarget)
{
m_vRet.emplace_back(exp);
}
return ;
}
const auto& chBit = m_strNum[hasDo] ;
const auto& iBit = chBit - ‘0’;
//1+2*3 llValue=7 endMulValue=6 endValue=3 exincludeEnd=1 preMul=2
long long exincludeEnd = llValue - endMulValue;
long long preMul = (0== endValue)? 0 : endMulValue / endValue;
#define NEW_END_MUL (preMul*llNewEnd)
//直接连接
//1+2*34 llValue=69 endMulValue=68 endValue=34 exincludeEnd=1 preMul=2
long long llNewEnd = endValue * 10 + ((endValue<0) ? -iBit : iBit);
if (0 != endValue )
{
dfs(exp + chBit, hasDo + 1, exincludeEnd + NEW_END_MUL, NEW_END_MUL, llNewEnd);
}
//乘以
llNewEnd = iBit;
preMul = endMulValue;
dfs(exp + '*'+ chBit, hasDo + 1, exincludeEnd + NEW_END_MUL, NEW_END_MUL, llNewEnd);
preMul = 1;
exincludeEnd = llValue;
dfs(exp + '+' + chBit, hasDo + 1, exincludeEnd + NEW_END_MUL, NEW_END_MUL, llNewEnd);
llNewEnd = -iBit;
dfs(exp + '-' + chBit, hasDo + 1, exincludeEnd + NEW_END_MUL, NEW_END_MUL, llNewEnd);
}
string m_strNum;
int m_iTarget;
vector m_vRet;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 《喜缺全书算法册》以原理、正确性证明、总结为主。 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
QQ群名片
评论记录：
回复评论：