【回溯 栈 代数系统 动态规划】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=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<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++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/621218.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

C++深度解析教程笔记8

C++深度解析教程笔记8

C深度解析教程笔记8 第17课 - 对象的构造&#xff08;上&#xff09;类定义中成员变量i和j的初始值&#xff1f;实验-成员变量的初始值对象初始化解决方案1实验-手动调用函数初始化对象对象初始化解决方案2&#xff1a;构造函数实验-构造函数小结 第18课 - 对象的构造&#xff…
阅读更多...
File类~路径、创建文件对象

File类~路径、创建文件对象

路径分为相对路径&#xff08;不带盘符&#xff09;&#xff0c;绝对路径&#xff08;带盘符&#xff09; 路径是可以存在的&#xff0c;也可以是不存在的 创建文件对象的三个方法&#xff1a;
阅读更多...
QT设计模式：策略模式

QT设计模式：策略模式

基本概念 策略模式&#xff08;Strategy Pattern&#xff09;是一种行为型设计模式&#xff0c;它定义了一系列方法&#xff0c;并使它们可以相互替换。策略模式使得算法可以独立于客户端而变化&#xff0c;使得客户端可以根据需要选择相应的算法。 策略模式通常由以下角色组…
阅读更多...
使用非官网购买Chatgpt的api调用

使用非官网购买Chatgpt的api调用

测试代码 from openai import OpenAI client OpenAI(api_key用户密钥) import json import os import timeclass ChatGPT:def __init__(self, user):self.user userself.messages [{"role": "system", "content": "Agent"}]def as…
阅读更多...
每周一算法：传递闭包

每周一算法：传递闭包

题目描述 不等式排序 给定 n n n个变量和 m m m个不等式。其中 n n n小于等于 26 26 26&#xff0c;变量分别用前 n n n 的大写英文字母表示。 不等式之间具有传递性&#xff0c;即若 A > B A>B A>B 且 B > C B>C B>C&#xff0c;则 A > C A>C …
阅读更多...
linux下的进程通信

linux下的进程通信

进程通信 进程为什么需要通信呢&#xff1f;进程通信的技术背景进程通信本质 进程通信分类管道匿名管道pipe匿名管道原理管道特点 命名管道创建命名管道命名管道原理 System V IPC管道与 System V的区别共享内存函数ftok()shmget() shmat()shmdt()shmctl()删除共享内存System V…
阅读更多...
【笔记】EF_PNN获取及运营商名称显示（待完善）

【笔记】EF_PNN获取及运营商名称显示（待完善）

问题背景 当设备无法成功解析EONS(PNN)的值（即SIM卡EF文件内容），则会用次优先级的NITZ去refresh了SPN。（问题代码如下，是通过Phone对象拿到plmn为空） 运营商名称一般显示优先级：Eons > NITZ > XML OPL id 0 对应的是PNN第一条 功能逻辑 （定制）当卡中的spn为空…
阅读更多...
生产制造行业推拉式生产的复合应用

生产制造行业推拉式生产的复合应用

一、案例分析&#xff08;汽配行业&#xff09; 重点&#xff1a; 1. MTO/MTS 与 PUSH/PULL 有关系但是不是充分关系 2. MTO/MTS 是公司经营策略&#xff0c;更多是对市场需求的经营策略&#xff0c;体现在生产时机上的不同&#xff0c;一个是等客户需求&#xff0c;一个是填…
阅读更多...
做国外问卷调查，一天能挣多少钱？

做国外问卷调查，一天能挣多少钱？

大家好​&#xff0c;我是汇舟问卷&#xff0c;专注于国外问卷调查项目已经五年的时间了&#xff0c;目前做的一直比较稳定。 这个项目说白了就是通过搭建国外的环境&#xff0c;登录问卷平台&#xff0c;通过参与国外企业发布的问卷调查来获取​美金奖励。 那么参与的问卷的…
阅读更多...
AI算法-高数5.2-线性代数-向量间的线性相关、无关定义和结论

AI算法-高数5.2-线性代数-向量间的线性相关、无关定义和结论

宋浩老师课程&#xff1a;3.2 向量间的线性关系&#xff08;二&#xff09;_哔哩哔哩_bilibili 线性相关、不相关结论&#xff1a; 判断线性有关\无关&#xff0c;转化成方程组&#xff1a; 判断条件> 向量线性相关、无关的本质是&#xff1a;除0外能不能找到非0的数据。
阅读更多...
交流负载箱：电力系统的智能升级

交流负载箱：电力系统的智能升级

随着科技的不断发展&#xff0c;电力系统也在不断地进行升级和改进。在这个过程中&#xff0c;交流负载箱作为一种新型的电力设备&#xff0c;为电力系统的智能升级提供了有力的支持。本文将对交流负载箱在电力系统中的应用及其优势进行简要分析。 首先&#xff0c;交流负载箱…
阅读更多...
【Qt】常用控件(一)

【Qt】常用控件(一)

文章目录 一、核心属性1、enabled代码示例: 通过按钮2 切换按钮1 的禁用状态 2、geometry代码示例: 控制按钮的位置代码示例&#xff1a;window frame 的影响代码示例: 感受 geometry 和 frameGeometry 的区别 3、windowTitle4、windowIcon代码示例: 通过 qrc 管理图片作为图标…
阅读更多...
探秘未来科技：数字化无人巡检的奇妙之旅

探秘未来科技：数字化无人巡检的奇妙之旅

嘿&#xff0c;朋友们&#xff01;下午茶时间到&#xff01;趁着这会儿咱们来聊一个超级炫酷的话题——数字化无人巡检。想象一下&#xff0c;那些曾经需要人工跋山涉水、风吹日晒的巡检工作&#xff0c;现在正被一群“智能小分队”悄悄接手&#xff0c;是不是觉得既神奇又方便…
阅读更多...
国内使用 CloudFlare 避坑指南

国内使用 CloudFlare 避坑指南

最近明月收到了不少新手使用 CloudFlare 的求助，发现很多首次使用 CloudFlare 的甚至包括已经在使用 CloudFlare 的站长们对 CloudFlare 的使用有很多的误区，再加上国内简中互联网上有关 CloudFlare 的教程良莠不齐，更是加深了新手使用 CloudFlare 入坑的概率，让一些别有用…
阅读更多...
maven .lastUpdated文件作用

maven .lastUpdated文件作用

现象 有时候我在用maven管理项目时会发现有些依赖报错&#xff0c;这时你可以看一下本地仓库中是否有.lastUpdated文件&#xff0c;也许与它有关。 原因 有这个文件就表示依赖下载过程中发生了错误导致依赖没成功下载&#xff0c;可能是网络原因&#xff0c;也有可能是远程…
阅读更多...
汽车灯罩材料使用PMMA（亚克力）具有哪些优势？汽车车灯的灯罩如果破损破裂破洞了要怎么修复？

汽车灯罩材料使用PMMA（亚克力）具有哪些优势？汽车车灯的灯罩如果破损破裂破洞了要怎么修复？

汽车灯罩材料使用PMMA&#xff08;亚克力&#xff09;具有哪些优势 首先&#xff0c;PMMA具有高透明度&#xff0c;其透光率可达92%以上&#xff0c;使得光线能够均匀、清晰地透过灯罩&#xff0c;为驾驶者提供明亮且均匀的照明效果&#xff0c;确保行车安全。 其次&#xff…
阅读更多...
618洗地机怎么选？热门洗地机选购指南，拒绝踩雷

618洗地机怎么选？热门洗地机选购指南，拒绝踩雷

洗地机是一种智能化的清洁工具&#xff0c;具有超强的清洁能力&#xff0c;能轻松应对各种地面污渍&#xff0c;无论是干污还是湿污。其一键操作设计简便易上手&#xff0c;省去了传统清洁方式的繁琐步骤&#xff0c;节省了时间和精力。高端型号更配备智能感应功能&#xff0c;…
阅读更多...
产品设计中的“注册”说明

产品设计中的“注册”说明

​在使用网站或应用的时候必不可少的就是账号系统&#xff0c;账号系统有些人可能觉得简单&#xff0c;无非就是账号密码。真的是这样吗&#xff1f; 一个完整的账号系统通常大家会分成四部分&#xff1a; 1.注册&#xff08;手机号、邮箱、用户名/密码限制/验证码&#xff09;…
阅读更多...
C++进阶：AVL树详解及模拟实现（图示讲解旋转过程）

C++进阶：AVL树详解及模拟实现（图示讲解旋转过程）

C进阶&#xff1a;AVL树详解及模拟实现&#xff08;图示讲解旋转过程&#xff09; 之前在搜索二叉树最后早就埋下伏笔&#xff0c;来介绍AVL树和红黑树&#xff0c;今天就先来第一个吧 文章目录 1.AVL树介绍1.1概念介绍1.2核心性质 2.项目文件规划3.整体框架&#xff08;节点和…
阅读更多...
植物ATAC-seq文献集锦（一）——基因组篇

植物ATAC-seq文献集锦（一）——基因组篇

ATAC-seq&#xff08;Assay for Transposase-Accessible Chromatin with high-throughput Sequencing&#xff09;是一种用于探究染色质开放性区域的技术&#xff0c;该技术利用Tn5转座酶接近核小体疏松区域切割暴露的DNA&#xff0c;获得开放的染色质区段(Open Chromatin)&…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站