我要招人

去企业版

首页 > 试题广场 >

给表达式添加运算符

[编程题]给表达式添加运算符

热度指数：1157 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个仅包含数字的字符串 num 和一个目标值 target，在 num 的数字之间添加二元运算符 "+" , "-" 或 "*" ,返回所有能够得到目标值的表达式。

数据范围：字符串长度满足 $1 \le n \le 10 \$ ， nums 中仅包含数字， $|target| \le 10^9 \$

示例1

输入

"123",6

输出

["1+2+3","1*2*3"]

示例2

输入

"00",0

输出

["0+0","0*0","0-0"]

算法知识视频讲解

讨啄的白菜

刷牛客以来遇到的最离谱的一题，这也能过？

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param num string字符串 
 * @param target int整型 
 * @return string字符串一维数组
 * @return int* returnSize 返回数组行数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
char** addOpt(char* num, int target, int* returnSize ) {
    // write code here
    return NULL;
}

发表于 2022-08-28 21:48:02 回复(0)

唐氏综合征

这道题应该算 '较难' 才比较合理，思路如下

1. 从第一个数字字符开始，进行递归，然后在尝试前两个，以此类推...

2. 每次递归都尝试三种运算符

3. 每次递归的时候都要记录上次合并到结果前的元素的值，这是因为遇到 * 时，* 的优先级，需要先回退到合并结果前，再进行 * 计算，再合并结果，才能获得正确结果

4. 注意对 '0' 开头的子串的处理，如果以 '0' 开头，只能处理一次，当第二次循环时，当前的值就是 '0X' 这种结构，是非法的，因此直接退出循环

5. 初始化处理，当 pos =0 时，需要将第一个元素加入，触发整个递归回溯过程

  public static String[] addOpt(String num, int target) {
        List<String> result = new ArrayList<>();
        if (num == null || num.length() == 0) 
            return new String[0];
        String first = num.substring(0, 1);
        backtrack(result, first, num, target, 1, Long.parseLong(first), Long.parseLong(first));
        return result.toArray(new String[0]);
    }

    private static void backtrack(List<String> result, String path, String num, int target, int pos, long eval, long lastVal) {
        if (pos == num.length()) {
            if (target == eval)
                result.add(path);
            return;
        }

        for (int i = pos; i < num.length(); i++) {
            if (i > pos && num.charAt(pos) == '0') break;
            long cur = Long.parseLong(num.substring(pos, i + 1));
            backtrack(result, path + "+" + cur, num, target, i + 1, eval + cur, cur);
            backtrack(result, path + "-" + cur, num, target, i + 1, eval - cur, -cur);
            backtrack(result, path + "*" + cur, num, target, i + 1, eval - lastVal + lastVal * cur, lastVal * cur);
        }
    }

发表于 2024-05-15 14:05:03 回复(0)

Java

牛客148901号

import java.util.*;


public class Solution {
    public String[] addOpt(String num, int target) {
        List<String> result = new ArrayList<>();
        backtrack(result, num, target, "", 0, 0, 0);
        return result.toArray(new String[0]);
    }

    public void backtrack(List<String> result, String num, int target, String expr,
                          int index, long eval, long multed) {
        if (index == num.length()) {
            if (eval == target) {
                result.add(expr);
            }
            return;
        }
        for (int i = index; i < num.length(); i++) {
            if (i != index && num.charAt(index) == '0') {
                break;
            }
            long curr = Long.parseLong(num.substring(index, i + 1));
            if (index == 0) {
                backtrack(result, num, target, expr + curr, i + 1, curr, curr);
            } else {
                backtrack(result, num, target, expr + "+" + curr, i + 1, eval + curr, curr);
                backtrack(result, num, target, expr + "-" + curr, i + 1, eval - curr, -curr);
                backtrack(result, num, target, expr + "*" + curr, i + 1,
                          eval - multed + multed * curr, multed * curr);
            }
        }
    }
}

发表于 2024-05-02 18:58:07 回复(0)

JavaScript Node

牛客760497705号

function addOpt( num , target ) {
const nums = [...num]
const res = []
let str = nums[0]

const fn = (s, index) => {

    if (index >= nums.length) {

        if (eval(s) == target) {

            res.push(s)

        }

        return

    }

    fn(`${s}+${nums[index]}`, index + 1)

    fn(`${s}-${nums[index]}`, index + 1)

    fn(`${s}*${nums[index]}`, index + 1)

}

fn(str, 1)

return res

}

发表于 2023-03-30 09:26:45 回复(0)

小谷围做题家

package main

import "strconv"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param num string字符串 
 * @param target int整型 
 * @return string字符串一维数组
*/
func addOpt( num string ,  target int ) []string {
    ans:=[]string{}
    var dfs func(string,int,int)
    dfs=func(s string,sum int,idx int){
        if idx==len(num){
            if sum==target{
                ans=append(ans,s)
            }
            return
        }
        str:=string(num[idx])
        x,_:=strconv.Atoi(str)
        dfs(s+"+"+str,sum+x,idx+1)
        dfs(s+"-"+str,sum-x,idx+1)
        dfs(s+"*"+str,sum*x,idx+1)
    }
    str:=string(num[0])
    x,_:=strconv.Atoi(str)
    dfs(str,x,1)
    return ans
}

发表于 2023-03-17 09:18:24 回复(0)

Python3

E-Doz

class Solution:
    def addOpt(self , num: str, target: int) -> List[str]:
        # write code here
        def dfs(num, target,stack, cur, ret):
            if not num:
                if sum(stack) == target:
                    ret.append(cur)
                return
            for i in range(len(num)):
                if i > 0 and num[i] == "0":
                    return
                n = int(num[:i+1])
                dfs(num[i+1:], target, stack+[n], cur+"+"+str(n), ret)
                dfs(num[i+1:], target, stack+[-n], cur+"-"+str(n), ret)
                temp = stack[-1]
                dfs(num[i+1:], target, stack[:-1]+[temp*n],cur+"*"+str(n),ret)
        ret = []
        s = ""
        for i in range(len(num)):
            if i > 0 and num[i] == "0":
                break
            n = int(num[:i+1])
            dfs(num[i+1:], target, [n], str(n), ret)
        return ret

发表于 2022-10-03 20:51:42 回复(0)

C++

AsherChi

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;
        int a = num[0] - '0';
        string s = "";
        s+= num[0];
        for(int i=1; i<num.length(); i++)
        {
            a += num[i] - '0';
            s += '+';
            s += num[i];
        }
        if(a == target)
            res.push_back(s);
        a = num[0] - '0';
        s = "";
        s += num[0];
        for(int i=1; i<num.length(); i++)
        {
            a *= num[i] - '0';
            s += '*';
            s += num[i];
        }
        if(a == target)
            res.push_back(s);
        a = num[0] - '0';
        s = "";
        s += num[0];
        for(int i=1; i<num.length(); i++)
        {
            a -= num[i] - '0';
            s += '-';
            s += num[i];
        }
        if(a == target)
            res.push_back(s);
        return res;
    }
};

发表于 2022-09-08 11:44:39 回复(0)