NC217. 给表达式添加运算符
描述
示例1
输入:
"123",6
输出:
["1+2+3","1*2*3"]
示例2
输入:
"00",0
输出:
["0+0","0*0","0-0"]
C++ 解法, 执行用时: 3ms, 内存消耗: 384KB, 提交时间: 2022-01-08
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num string字符串
* @param target int整型
* @return string字符串vector
*/
vector<string> addOpt(string num, int target) {
vector<string> ans;
for(auto [opstr,fn]: vector<pair<string,function<int(int,int)> > > {
{"+", [] (int x, int y) { return x + y; }},
{"-", [] (int x, int y) { return x - y; }},
{"*", [] (int x, int y) { return x * y; }},
}){
string s = num.substr(0,1); // 运算字符串
int v = num[0]-'0'; // 运算结果
for(int i = 1;i<num.length();i++){
v = fn(v,num[i]-'0');
s+= opstr + num.substr(i,1);
}
if(v == target)ans.push_back(s);
}
return ans;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2022-01-31
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num string字符串
* @param target int整型
* @return string字符串vector
*/
vector<string> addOpt(string num, int target) {
// write code here
vector<string> res;
string add,sub,mul;
int len=num.size();
if(len<=1){
return res;
}
int tmp = 0;
add_func(num, res, add, tmp, target, 0, '+');
tmp = 0;
add_func(num, res, mul, tmp, target, 0, '*');
tmp = 0;
add_func(num, res, sub, tmp, target, 0, '-');
return res;
}
void add_func(string num,vector<string>& res,string& str,int& cal,int target,int index,char symbol){
if(index==0){
cal=num[index]-'0';
str+=num[index];
index++;
add_func(num, res, str, cal, target, index, symbol);
return;
}
if(index==num.size()){
if(cal==target){
res.push_back(str);
}
return;
}
switch(symbol){
case '+':
cal+=num[index]-'0';
break;
case '*':
cal*=num[index]-'0';
case '-':
cal-=num[index]-'0';
default:
break;
}
str+=symbol;
str+=num[index];
index++;
add_func(num, res, str, cal, target, index, symbol);
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-05-08
class Solution {
public:
vector<string> addOpt(string num, int target) {
vector<string> a;
for (auto [b, c] : vector<pair<string, function<int(int, int)> > > {
{"+", [] (int x, int y) {
return x + y;
}
},
{"-", [] (int x, int y) {
return x - y;
}
},
{"*", [] (int x, int y) {
return x * y;
}
},
}) {
string s = num.substr(0, 1);
int v = num[0] - '0';
for (int i = 1; i < num.length(); i++) {
v = c(v, num[i] - '0');
s += b + num.substr(i, 1);
}
if (v == target)
a.push_back(s);
}
return a;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-01-26
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num string字符串
* @param target int整型
* @return string字符串vector
*/
vector<string> addOpt(string num, int target) {
vector<string> ans;
string s = num.substr(0,1); // 加法字符串
int v = num[0]-'0'; // 加法结果
for(int i = 1;i<num.length();i++){
v+=num[i]-'0';
s+="+"+num.substr(i,1);
}
if(v == target)ans.push_back(s); // 对比结果
s = num.substr(0,1); // 乘法字符串
v = num[0]-'0'; // 乘法结果
for(int i = 1;i<num.length();i++){
v*=num[i]-'0';
s+="*"+num.substr(i,1);
}
if(v == target)ans.push_back(s); // 对比结果
s = num.substr(0,1); // 减法字符串
v = num[0]-'0'; // 减法结果
for(int i = 1;i<num.length();i++){
v-=num[i]-'0';
s+="-"+num.substr(i,1);
}
if(v == target)ans.push_back(s); // 对比结果
return ans;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 400KB, 提交时间: 2022-05-25
class Solution {
public:
vector<string> addOpt(string num, int target) {
// write code here
vector<string> res;
string add,sub,mul;
int len =num.length();
if(len<=1) return res;
fun(num, target,res,0, 0, add,'+');
fun(num, target,res,0, 0, add,'-');
fun(num, target,res,0, 0, add,'*');
return res;
}
void fun(string num, int target,vector<string>& res,int cal,int index,string str,char symbol)
{
if(index ==0)
{
cal =num[index]-'0';
str += num[index];
index++;
fun(num, target, res, cal, index, str, symbol);
return;
}
if(index ==num.size())
{
if(cal ==target) res.push_back(str);
return;
}
switch(symbol)
{
case '+':
cal += num[index]-'0';
case '*':
cal *= num[index]-'0';
case '-':
cal -= num[index]-'0';
default:
break;
}
str += symbol;
str += num[index];
index++;
fun(num, target, res, cal, index, str, symbol);
}
};