当前位置: 首页 > news >正文

【Leetcode】241. 为运算表达式设计优先级

241. 为运算表达式设计优先级(中等)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

解法一:分治法

对于这道题,加括号其实就是决定运算次序,所以我们可以把加括号转化为,「对于每个运算符号,先执行处理两侧的数学表达式,再处理此运算符号」。

对于一个形如 x op y 的算式而言,它的结果组合取决于 x 和 y 的结果组合数 ,而 x 和 y 又可以写成形如 x op y 的算式。

因此,该问题的子问题就是 x op y 中的 x 和 y:以运算符分隔的左右两侧算式解

对于分治算法分成三步走:

  • 分解:按照运算符分隔成左右两部分,分别求解;
  • 解决:通过递归实现,最终我们会得到只包含数字的算式,返回数字作为算式解;
  • 合并:根据运算符合并左右两部分的解,得出最终解。

代码

class Solution {
public:vector<int> diffWaysToCompute(string expression) {vector<int> ans, left, right;int flag = 0; int n = expression.size();for(int i=0; i<n; ++i){// 如果 expression[i] 是运算符号if(!isdigit(expression[i])){flag = 1; // flag=1说明string是表达式,flag=0说明string是一个数字// string s(str, begin, len):// 将字符串str中从下标begin开始、长度为len的部分作为字符串初值left = diffWaysToCompute(string(expression, 0, i));right = diffWaysToCompute(string(expression, i+1, n-i));// 遍历left和right的所有结果数for(int l : left){for(int r : right){if(expression[i] == '+') ans.push_back(l + r);if(expression[i] == '-') ans.push_back(l - r);if(expression[i] == '*') ans.push_back(l * r);}}}}if(flag == 0){// expression 只是一个数字// {int} -> vector<int>return {stoi(expression)};}return ans;}
};

解法二:分治法+记忆化

解法一中存在重复运算,比如 2*3 - 4*5 ,按照第一个 * 分割,右边部分是 3 - 4*5 ,进而计算 4*5 ,而按照 - 分割,同样会再次计算 4*5

为了减少重复运算,可以使用记忆化搜索,保存字符串区间[l,r]的运算结果,整个思路和解法一类似,不同点在于:设置一个 map 保存结果,递归的时候先在 map 中查找,如果该字符串已经计算过,那么直接返回保存的结果。

代码

class Solution {
public:unordered_map<string, vector<int>> mp;vector<int> diffWaysToCompute(string expression) {if(mp.find(expression) != mp.end()) return mp.find(expression) -> second;vector<int> ans, left, right;int flag = 0; int n = expression.size();for(int i=0; i<n; ++i){// 如果 expression[i] 是运算符号if(!isdigit(expression[i])){flag = 1; // flag=1说明string是表达式,flag=0说明string是一个数字// string s(str, begin, len):// 将字符串str中从下标begin开始、长度为len的部分作为字符串初值left = diffWaysToCompute(string(expression, 0, i));right = diffWaysToCompute(string(expression, i+1, n-i));// 遍历left和right的所有结果数for(int l : left){for(int r : right){if(expression[i] == '+') ans.push_back(l + r);if(expression[i] == '-') ans.push_back(l - r);if(expression[i] == '*') ans.push_back(l * r);}}}}if(flag == 0){// expression 只是一个数字// {int} -> vector<int>return {stoi(expression)};}mp[expression] = ans;return ans;}
};

解法三:动态规划

对于表达式 expression 需要做预处理:「把每个数字转为 int 存起来,同时运算符也存起来」。

这样子将得到两个数组,以 2 * 3 - 4 * 5 为例,存起来的数字是 numList = [2 3 4 5],存起来的运算符是 opList = [*, -, *]

状态定义

dp[i][j] 表示从第 i 个数字到第 j 个数字(从 0 开始计数)范围内表达式的所有解。

dp[1][3]表示:第 1 个数字 (3) 到 第 3 个数字(5)范围内表达式 3 - 4 * 5 的所有解。

状态转移方程

有了一个数字的所有解(初始化),就可以求出两个数字的所有解。

有了两个数字的所有解,三个数字的所有解就和解法一求法一样。

把三个数字分成两部分,将两部分的解两两组合起来即可。

对于两部分之间的运算符,因为表达式是一个数字一个运算符,所以运算符的下标就是左部分最后一个数字的下标

对于 2 * 3 - 4 * 5 ,存起来的数字是 numList = [2 3 4 5], 存起来的运算符是 opList = [*, -, *]

假设要求 dp[1][3],也就是计算 3 - 4 * 5 的解:

  • 分成 3 和 4 * 5 两部分,3 对应的下标是 1 ,对应的运算符就是 opList[1] = '-' ,也就是计算 3 - 20 = -17

  • 分成 3 - 4 和 5 两部分,4 的下标是 2 ,对应的运算符就是 opList[2] = '*'
    也就是计算 -1 * 5 = -5

  • 所以 dp[1][3] = [-17 -5]

四个、五个… 都可以分成两部分,然后通过之前的解求出来。

直到包含了所有数字的解求出来。

初始化

对范围内只有一个数字的情况进行初始化:

dp[0][0] = 2, dp[1][1] = 3, dp[2][2] = 4, dp[3][3] = 5;

返回的最终结果

最终返回第 0 个数字到最后一个数字范围内表达式的所有解,即 dp[0][n-1]

代码

class Solution {
public:vector<int> diffWaysToCompute(string expression) {vector<int>  numList;vector<char> opList;// 对 expression 预处理int num = 0;for(char ch : expression){if(!isdigit(ch)){numList.push_back(num);num = 0;opList.push_back(ch);}else{num = num * 10 + ch - '0';}}numList.push_back(num);int n = numList.size();vector<vector<vector<int>>> dp(n, vector<vector<int>>(n));// dp数组初始化for(int i=0; i<n; ++i){dp[i][i].push_back(numList[i]);}// 从2个数字遍历到n个数字for(int k=2; k<=n; ++k){// 开始遍历的下标for(int i=0; i<n; ++i){// 结束遍历的下标int j = i + k - 1;if(j >= n){// 越界break;}vector<int> ans;// 以s作为分隔点分成左右两部分遍历for(int s=i; s<j; ++s){vector<int> left = dp[i][s];vector<int> right = dp[s+1][j];// 遍历左边部分的所有结果值for(auto x : left){// 遍历右边部分的所有结果值for(auto y : right){// 根据操作符对所有结果进行组合// 操作符下标就是左边部分最后一个数字的下标char op = opList[s];if(op == '+') ans.push_back(x + y);else if(op == '-') ans.push_back(x - y);else if(op == '*') ans.push_back(x * y);}}}dp[i][j] = ans;}}return dp[0][n-1];}
};

相关文章:

【Leetcode】241. 为运算表达式设计优先级

241. 为运算表达式设计优先级&#xff08;中等&#xff09; 解法一&#xff1a;分治法 对于这道题&#xff0c;加括号其实就是决定运算次序&#xff0c;所以我们可以把加括号转化为&#xff0c;「对于每个运算符号&#xff0c;先执行处理两侧的数学表达式&#xff0c;再处理此…...

torch两个向量除法,对于分母向量中的元素为0是设置为1,避免运算错误

在gpu运行时&#xff0c;如果在进行两个向量除法的时候&#xff0c;对于分母向量中的元素为0是设置为1&#xff0c;避免运算错误。 可以使用torch的division函数以及clamp函数来解决这个问题。具体步骤如下&#xff1a; 使用division函数将分子向量除以分母向量。 使用clamp函…...

NodeJs 最近各版本特性汇总

&#xff08;预测未来最好的方法就是把它创造出来——尼葛洛庞帝&#xff09; NodeJs 官方链接 github链接 V8链接 Node.js发布于2009年5月&#xff0c;由Ryan Dahl开发&#xff0c;是一个基于Chrome V8引擎的JavaScript运行环境&#xff0c;使用了一个事件驱动、非阻塞式I/O模…...

python数据分析案例——天猫订单综合分析

前言 大家早好、午好、晚好吖 ❤ ~欢迎光临本文章 什么是数据分析 明确目的–获得数据(爬虫&#xff0c;现有&#xff0c;公开的数据)–数据预处理——数据可视化——结论 准备 环境使用&#xff1a; 在开始写我们的代码之前&#xff0c;我们要准备好运行代码的程序 Anacon…...

05- redis集群模式搭建(上) (包含云服务器[填坑])

目录 1. 准备环境: 2. 简介: -> 2.1 前言: -> 2.2 Redis集群架构实现了对redis的水平扩容 -> 2.3 redis cluster集群原理 3. 搭建后特别需要注意的问题 ->3.1 [重点]: 如果一个服务出现故障: 是否可以继续提供服务??? ---> 3.1.1 如果集群中故障re…...

【AI】YOLOV1原理详解

AI学习目录汇总 0、前言 YOLOv1~3作者是约瑟夫雷德蒙&#xff08;Joseph Chet Redmon&#xff09;&#xff0c;他的网站&#xff1a;https://pjreddie.com/ YOLOv1网站&#xff1a;https://pjreddie.com/darknet/yolov1/ YOLOv2网站&#xff1a;https://pjreddie.com/darknet…...

提高APP安全性的必备加固手段——深度解析代码混淆技术

APP 加固方式 Android APP 加固是优化 APK 安全性的一种方法&#xff0c;常见的加固方式有混淆代码、加壳、数据加密、动态加载等。下面介绍一下 Android APP 加固的具体实现方式。 混淆代码&#xff1a; 使用 ProGuard 工具可以对代码进行混淆&#xff0c;使得反编译出来的代…...

想让行车记录仪协助道路病害自动化检测?可以!

针对【RGB3DS道路表观病害信息智慧检测系统】&#xff0c;我们着重介绍过其与道路检测车做集成预装或者处理道路检测车数据的极大便利&#xff0c;其中之一便是可高效输出带有道路检测车桩号标记的病害报表&#xff0c;这是因为道路检测车数据本身具有规范性。 那么如果使用道…...

git上传大大大文件项目好折磨人

本来想把unity项目的源码上传上gitee啊&#xff0c;但是那个项目有1个多G&#xff0c;还是个半成品&#xff0c;要是写完&#xff0c;都不知道行不行 正常的上传 所用到的命令&#xff1a; 1、 git init 初始化&#xff0c;创建本地仓库 2、 git add . 添加到本地仓库 3、 git…...

java常见异常的处理方法

以下是一些常见的异常处理方法&#xff1a; 捕获和处理异常&#xff08;try-catch&#xff09;&#xff1a; 使用try-catch语句块可以捕获并处理异常。在try块中编写可能抛出异常的代码&#xff0c;然后在catch块中指定异常类型&#xff0c;以便捕获并处理异常。 try {// 可能抛…...

上传图片到阿里云服务器base64 上传

//上传图片到阿里云服务器 function upload_Ali($remoteImage){$imageData $this->n_img_base_64($remoteImage);if ($imageData ! false) {// 初始化 cURL 句柄$ch curl_init();// 设置请求 URL 和一些 cURL 选项curl_setopt($ch, CURLOPT_URL, http://dev.com/index/aja…...

【致敬未来的攻城狮计划】— 连续打卡第二十六天:瑞萨RA Cortex-M 内核RA2E1 RT-Thread BSP 启蒙知识

系列文章目录 由于一些特殊原因&#xff1a; 系列文章链接&#xff1a;&#xff08;其他系列文章&#xff0c;请点击链接&#xff0c;可以跳转到其他系列文章&#xff09;或者参考我的专栏“ 瑞萨MCU ”&#xff0c;里面是 瑞萨RA2E1 系列文章。 24.RA2E1的 DMAC——数据传输 …...

2023年5月8日-5月14日(方案C,下班UE视频教程为主)

目前&#xff0c;ue视频教程进行到了智 慧 城 市&#xff08;3.13&#xff09;&#xff0c;mysql(7.1)&#xff0c;tf1(4.11),蓝图反射(1.9)&#xff0c;moba&#xff08;1.5&#xff09;webapp&#xff08;2.4&#xff09;&#xff0c;mmoarpg(00A_04)&#xff0c;fps1_12(0:3…...

「MIAOYUN」:降本增效,赋能传统企业数字化云原生转型 | 36kr 项目精选

作为新经济综合服务平台第一品牌&#xff0c;36氪自2019年落地四川站以来&#xff0c;不断通过新锐、深度的商业报道&#xff0c;陪跑、支持四川的新经济产业。通过挖掘本土优质项目&#xff0c;36氪四川帮助企业链接更多资源&#xff0c;助力企业成长&#xff0c;促进行业发展…...

Python突破JS加密限制,进行逆向解密

前言 嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! 目录标题 前言开发环境:模块使用:逆向目标逆向过程参数 JS 加密关键代码Python 登录关键代码尾语 &#x1f49d; 开发环境: Python 3.8 Pycharm 模块使用: time >>> 时间模块&#xff0c;属于内置&#xff0c;无…...

【Linux】exec函数族

目录 1、exec函数族的介绍2、exec相关函数 1、exec函数族的介绍 2、exec相关函数 #include <unistd.h> int execl(const char *pathname, const char *arg0, ... /* (char *)0 */ ); /* - path 需要指定的执行的文件的路径或者名称&#xff0c;相对路径or绝对路径- arg …...

OSQP二次规划求解库使用说明

OSQP二次规划求解库使用说明 贺志国 2023.5.10 1. 凸二次规划的一般表达式 m i n 1 2 x T P x q T x s . t . l ≤ A x ≤ u min \quad \frac{1}{2}x^T Px q^Tx \qquad s.t. \quad l \leq Ax \leq u min21​xTPxqTxs.t.l≤Ax≤u 其中&#xff0c; P P P称为内核矩阵&#x…...

Elasticsearch(一)

Elasticsearch&#xff08;一&#xff09; 初始elasticsearch 什么是elasticsearch elasticsearch是一款非常强大的开源搜索引擎&#xff0c;可以帮助我们从海量数据中快速查找到需要的内容 elasticsearch结合kibana、Logstash、Beats&#xff0c;也就是elastic stack&…...

深入探究Java中的枚举类型:定义、特性和应用

引言&#xff1a; 在Java编程中&#xff0c;枚举类型是一种强大而灵活的工具&#xff0c;用于定义一组具名的常量。它不仅提供了代码可读性和可维护性的优势&#xff0c;还为开发人员提供了一种更安全和结构化的方式来处理固定的常量集合。本文将深入探讨Java中的枚举类型&…...

linux密码忘了?一招解决

目录 一、前言 二、进入编辑界面 三、单用户模式 四、修改密码 五、更新信息 六、退出 七、验证 一、前言 版本&#xff1a;centos7.9、VMware15.5 在我们学习linux运行级别的时候&#xff0c;面试题可能会出如何找回root密码&#xff0c;下面来详细的介绍一波&#xff…...

Neosegment库:面向七段数码管式NeoPixel的嵌入式驱动框架

1. Neosegment库概述&#xff1a;面向七段数码管式NeoPixel模块的嵌入式驱动框架Neosegment是一个专为Neosegment Digit模块设计的Arduino兼容嵌入式驱动库&#xff0c;其核心目标是将WS281x/SK6812系列智能LED的底层时序控制与七段数码管&#xff08;7-segment display&#x…...

Krita 5.3.0 与 6.0.0 发布:功能升级与技术革新

文本与工具革新&#xff0c;Krita 功能升级Krita 5.3.0 和 6.0.0 正式推出&#xff0c;带来了一系列显著的功能改进。文本工具被完全重写&#xff0c;支持在画布上进行所见即所得编辑&#xff0c;还能支持 OpenType 的所有特性以及文本置入形状&#xff0c;这大大提升了文字处理…...

从Simulink模型到神经网络:一个完整的数据驱动建模与验证实践

1. 为什么需要从Simulink模型转向神经网络&#xff1f; 在控制系统工程领域&#xff0c;Simulink模型一直是建模和仿真的黄金标准。但最近几年&#xff0c;越来越多的工程师开始尝试用神经网络来替代传统模型。这背后有几个关键原因&#xff1a; 首先&#xff0c;传统物理模型在…...

ModTheSpire模组加载器全攻略:解锁杀戮尖塔无限可能

ModTheSpire模组加载器全攻略&#xff1a;解锁杀戮尖塔无限可能 【免费下载链接】ModTheSpire External mod loader for Slay The Spire 项目地址: https://gitcode.com/gh_mirrors/mo/ModTheSpire 副标题&#xff1a;从零开始的模组探索之旅——让你的游戏体验突破边界…...

卡尔曼滤波调参实战:如何用MATLAB让MPU6050的加速度数据更‘听话’?

卡尔曼滤波调参实战&#xff1a;如何用MATLAB让MPU6050的加速度数据更‘听话’&#xff1f; 当你在MATLAB中第一次看到MPU6050的原始加速度数据时&#xff0c;那些疯狂跳动的曲线可能会让你怀疑人生。别担心&#xff0c;这不是传感器坏了&#xff0c;而是现实世界本就充满噪声…...

Qwen3.5-2B多场景教程:农业技术人员上传病虫害图→识别种类→推荐药剂

Qwen3.5-2B多场景教程&#xff1a;农业技术人员上传病虫害图→识别种类→推荐药剂 1. 引言&#xff1a;农业病虫害识别的技术痛点 在农业生产中&#xff0c;病虫害防治一直是困扰农户的核心问题。传统识别方式存在三大痛点&#xff1a; 识别门槛高&#xff1a;需要专业农技人…...

终极指南:如何使用Harepacker-resurrected打造个性化MapleStory游戏体验

终极指南&#xff1a;如何使用Harepacker-resurrected打造个性化MapleStory游戏体验 【免费下载链接】Harepacker-resurrected All in one .wz file/map editor for MapleStory game files 项目地址: https://gitcode.com/gh_mirrors/ha/Harepacker-resurrected 你是否曾…...

Ostrakon-VL-8B惊艳效果:同一界面内对比原始图/热力图/标注图三视图

Ostrakon-VL-8B惊艳效果&#xff1a;同一界面内对比原始图/热力图/标注图三视图 1. 像素特工终端&#xff1a;重新定义零售视觉分析 想象一下&#xff0c;当你走进一家零售店铺&#xff0c;能瞬间"扫描"出所有商品的位置、价格标签和货架状态。这正是Ostrakon-VL-8…...

OpenClaw语音控制之多麦克风阵列与声源定位技术的应用

7.1 麦克风阵列基础 7.1.1 阵列定义与原理 麦克风阵列是由多个麦克风按照特定几何结构排列组成的声学传感器系统。与单麦克风相比,阵列系统通过空间采样能够实现声场的时空联合处理,从而获得方向性选择能力。这种空间处理能力是语音交互系统在复杂声学环境中保持高性能的关…...

Win11更新后Wifi图标消失?别急着重装系统,先试试这个官方驱动修复法

Win11更新后Wifi图标消失&#xff1f;三步精准定位官方驱动修复方案 刚更新完Windows 11系统&#xff0c;正准备继续手头的工作&#xff0c;突然发现任务栏右下角的Wifi图标不翼而飞。尝试重启电脑、重置网络设置&#xff0c;甚至检查了各种服务状态&#xff0c;问题依旧存在。…...