【回溯 栈 代数系统 动态规划】282. 给表达式添加运算符

2024-05-13 19:12
文章标签 动态 规划 系统 表达式 运算符 代数 282 回溯

本文主要是介绍【回溯 栈 代数系统 动态规划】282. 给表达式添加运算符，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文涉及知识点

回溯 栈 代数系统 动态规划

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−1​Forx:∈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;}
};

测试用例

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);}}

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;}};

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=2long 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<string> m_vRet;

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。

这篇关于【回溯 栈 代数系统 动态规划】282. 给表达式添加运算符的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/986583。

相关文章

Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
基于人工智能的图像分类系统

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务，目标是自动识别图像中的对象类别。通过卷积神经网络（CNN）等深度学习技术，我们可以构建高效的图像分类系统，广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统，包括环境
阅读更多...
水位雨量在线监测系统概述及应用介绍

水位雨量在线监测系统概述及应用介绍

在当今社会，随着科技的飞速发展，各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中，水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术，其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成，形成了一个完整的闭环系统。 数据采集单元：这是系统的“眼睛”，
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
嵌入式QT开发：构建高效智能的嵌入式系统

嵌入式QT开发：构建高效智能的嵌入式系统

摘要： 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发，详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程，包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发，涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用，以及嵌入式 QT 与硬件设备的交互，包括输入输出设
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2