C++算法：给表达式添加运算符

题目

给定一个仅包含数字 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 。

2023年5月版

class Solution {
 public:
 vector 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 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+23 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 (preMulllNewEnd)
 //直接连接
 //1+234 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;
 };

扩展阅读

相关下载

想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版

之。 |
|如果程序是一条龙，那算法就是他的是睛|

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17