【LeetCode-282】给表达式添加运算符 [难度:困难]

2023-10-17 15:01

本文主要是介绍【LeetCode-282】给表达式添加运算符 [难度:困难],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原题

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

注意,返回表达式中的操作数 不应该 包含前导零。

  • 来源:力扣(LeetCode)
  • 难度:困难
  • 链接:https://leetcode.cn/problems/expression-add-operators/description/

解法

设字符串 num 的长度为 n,为构建表达式,我们可以往 num中间的 n−1 个空隙添加 + 号、- 号或 * 号,或者不添加符号。

我们可以用「回溯法」来模拟这个过程。从左向右构建表达式,并实时计算表达式的结果。由于乘法运算优先级高于加法和减法运算,我们还需要保存最后一个连乘串(如 2*3*4)的运算结果。

定义递归函数 backtrack(expr,i,res,mul):

  • expr 为当前构建出的表达式;
  • i 表示当前的枚举到了 num 的第 i 个数字;
  • res 为当前表达式的计算结果;
  • mul为表达式最后一个连乘串的计算结果。

因此会出现两种情况:

  1. 如果 i=n,说明表达式已经构造完成,若此时有 res=target,则找到了一个可行解,我们将 expr放入答案数组中,递归结束;
  2. 如果 i<n,需要枚举当前表达式末尾要添加的符号(+号、- 号或 * 号),以及该符号之后需要截取多少位数字。设该符号之后的数字为 val,按符号分类讨论:
    (1)若添加 +号,则 res 增加 val,且 val 单独组成表达式最后一个连乘串;
    (2)若添加 -号,则 res减少 val,且 −val单独组成表达式最后一个连乘串;
    (3)若添加 * 号,由于乘法运算优先级高于加法和减法运算,我们需要对 res撤销之前 mul的计算结果,并添加新的连乘结果mul∗val,也就是将 res减少 mul并增加 mul∗val。
 /*回溯*/
class Solution {int n;String num;int target;List<String> ans;public List<String> addOperators(String num, int target) {// 回溯this.n = num.length(); //num的长度this.num = num;this.target = target;this.ans = new ArrayList<String>(); // 存放符合条件的表达式StringBuffer expr = new StringBuffer();//存取 当前构建出的表达式backtrack(expr,0,0,0); //递归函数return ans; }/**expr:当前构建的表达式i:num的第i个数字res:当前表达式的计算结果mul:表达式最后一个连乘串结果*/public void backtrack(StringBuffer expr, int i , long res, long mul){// 如果i=n,则表达式构建完成,此时有res=target,则该表达式符合条件,放入ans中;if(i == n){if(res == target){ans.add(expr.toString());}return;}int signIndex = expr.length();//记录表达式最后的位置,也就是要插入符号的位置if(i>0){ //表达式开头不能添加符号,expr.append(0); //占位,下面用来填充符号}long val =0;//枚举截取的数字长度(取多少位),注意数字可以是单个 0 ,但不能有前导零for(int j = i;j<n && (j == i || num.charAt(i)!='0');++j){val = val*10 +num.charAt(j)-'0';//符号之后的数字expr.append(num.charAt(j));//该数填入表达式里,此时该数前面是占位的0if(i ==0){ //表达式开头不能添加符号backtrack(expr,j+1,val,val);}else{     // 枚举符号expr.setCharAt(signIndex,'+');backtrack(expr,j+1,res+val,val);expr.setCharAt(signIndex,'-');backtrack(expr,j+1,res-val,-val);expr.setCharAt(signIndex,'*');backtrack(expr,j+1,res-mul+mul*val,mul*val);}}expr.setLength(signIndex);}
}

这篇关于【LeetCode-282】给表达式添加运算符 [难度:困难]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/226179

相关文章

SpringBoot @Scheduled Cron表达式使用方式

《SpringBoot@ScheduledCron表达式使用方式》:本文主要介绍SpringBoot@ScheduledCron表达式使用方式,具有很好的参考价值,希望对大家有所帮助,如有... 目录Cron 表达式详解1. 表达式格式‌2. 特殊字符解析3. 常用示例‌4. 重点规则5. 动态与复杂场景‌

Spring Boot 集成 Quartz 使用Cron 表达式实现定时任务

《SpringBoot集成Quartz使用Cron表达式实现定时任务》本文介绍了如何在SpringBoot项目中集成Quartz并使用Cron表达式进行任务调度,通过添加Quartz依赖、创... 目录前言1. 添加 Quartz 依赖2. 创建 Quartz 任务3. 配置 Quartz 任务调度4. 启

Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

《SpringBoot中定时任务Cron表达式的终极指南最佳实践记录》本文详细介绍了SpringBoot中定时任务的实现方法,特别是Cron表达式的使用技巧和高级用法,从基础语法到复杂场景,从快速启... 目录一、Cron表达式基础1.1 Cron表达式结构1.2 核心语法规则二、Spring Boot中定

Java逻辑运算符之&&、|| 与&、 |的区别及应用

《Java逻辑运算符之&&、||与&、|的区别及应用》:本文主要介绍Java逻辑运算符之&&、||与&、|的区别及应用的相关资料,分别是&&、||与&、|,并探讨了它们在不同应用场景中... 目录前言一、基本概念与运算符介绍二、短路与与非短路与:&& 与 & 的区别1. &&:短路与(AND)2. &:非短

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

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

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

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

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

06 C++Lambda表达式

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

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L