【C++ 算法进阶】算法提升八
复杂计算 (括号问题相关递归套路 重要)
题目
给定一个字符串str str表示一个公式 公式里面可能有整数 + - * / 符号以及左右括号 返回最终计算的结果
题目分析
本题的难点主要在于可能会有很多的括号 而我们直接模拟现实中的算法的话code会难写 要考虑的情况很多
那么我们首先写出加入没有括号应该怎么计算呢
我们这里只需要首先计算乘法和除法 再计算加法和减法
代码
int process(string& s1) {// s1 表示计算的公式stack<string> st;int cur = 0;for (int i = 0; i < s1.size(); i++) {if (s1[i] < '0' || s1[i] > '9'){if (!st.empty()) {string test = st.top();if (test == "*" || test == "/") {string op = st.top();st.pop();int left = stoi(st.top());st.pop();int right = cur;if (op == "*") {cur = left * right;}else{cur = left / right;}}}st.push(to_string(cur));string ops = string(1, s1[i]);st.push(ops);cur = 0;}else{cur = cur * 10 + (s1[i] - '0');}}string test = st.top();if (test == "*" || test == "/") {string op = st.top();st.pop();int left = stoi(st.top());st.pop();int right = cur;if (op == "*") {cur = left * right;}else{cur = left / right;}}st.push(to_string(cur));stack<string> st2;while (!st.empty()){st2.push(st.top());st.pop();}// 最后我们按照顺序计算栈里面的结果while (st2.size() != 1){int left = stoi(st2.top());st2.pop();string op = st2.top();st2.pop();int right = stoi(st2.top());st2.pop();if (op == "+") {st2.push(to_string(left + right));}else{st2.push(to_string(left - right));}}return stoi(st2.top());
}
如果遇到括号怎么办呢

比如说我们现在计算到* 之后 遇到了一个 (
此时我们不进行继续的计算 而是使用递归 将这个括号里的内容传递给下个函数进行计算 我们只需要知道返回值即可
当然只知道返回值是不够的 因为我们还需要知道递归函数返回之后需要从哪一个位置开始计算
所以说递归函数的返回值要返回一个数组 数组里面存储着括号内计算的数值以及指针走到的位置
vector<int> process(string& s1 , int n ) {// s1代表字符串int i = n;int cur = 0;stack<string> st;while (i < s1.size() && s1[i] != ')'){if ((s1[i] < '0' || s1[i] > '9' ) && s1[i] != '('){if (!st.empty()) {string test = st.top();if (test == "*" || test == "/") {string op = st.top();st.pop();int left = stoi(st.top());st.pop();int right = cur;if (op == "*") {cur = left * right;}else{cur = left / right;}}}st.push(to_string(cur));string ops = string(1, s1[i]);st.push(ops);cur = 0;i++;}else if (s1[i] >= '0' && s1[i] <= '9'){cur = cur * 10 + (s1[i] - '0');i++;}else{vector<int> ans = process(s1 , i + 1);i = ans[1];cur = ans[0];}}// 走到这里说明碰到了边界了string test = st.top();if (test == "*" || test == "/") {string op = st.top();st.pop();int left = stoi(st.top());st.pop();int right = cur;if (op == "*") {cur = left * right;}else{cur = left / right;}}st.push(to_string(cur));stack<string> st2;while (!st.empty()){st2.push(st.top());st.pop();}// 最后我们按照顺序计算栈里面的结果while (st2.size() != 1){int left = stoi(st2.top());st2.pop();string op = st2.top();st2.pop();int right = stoi(st2.top());st2.pop();if (op == "+") {st2.push(to_string(left + right));}else{st2.push(to_string(left - right));}}return { stoi(st2.top()), i + 1 };
}
我们只需要在遇到左括号的时候将计算的任务丢给递归函数 也就是调用下面这段代码
else{vector<int> ans = process(s1 , i + 1);i = ans[1];cur = ans[0];}
即可
装最多水的容器 (贪心)
题目
本题为LC原题 题目如下

题目分析
装水的容积由两个部分决定
- 两块板子之间的宽度
- 两块板子中较小的那块板子的高度
所以说 只要我们找出每个宽度的最大值 最后对比一下 我们就能得出最终答案
所以说我们一开始自然是用最左和最右边的板子装水
之后宽度-- 那么我们要想得到最大值是不是要在高度上花心思
我们肯定要舍弃掉较为短的一块板子
之后用代码实现上述内容即可
代码
class Solution {
public:int maxArea(vector<int>& height) {int left = 0;int right = height.size() - 1;int ans = 0;while (left < right) {int h = min(height[left] , height[right]);int w = right - left;ans = max(w * h , ans);if (height[left] < height[right]) {left++;}else {right--;}}return ans;}
};
蛇走格子问题 (动态规划)
题目
假设现在有一个二维数组 每个位置存放着一个整数 (可以为负)
现在有一条蛇要从这个数组的最左边开始找出一条整数相加为最大值的路径
蛇只能往右上 右 右下走
如果叠加到负数则蛇立刻死亡(之前成绩归为-1)
蛇有一种能力 只能发动一次 可以让格子的值变成相反数
题目分析
这是一道经典的动态规划问题 我们可以设计一个如下的函数
// 数组arr上返回i j位置的info信息
// info信息 使用了能力和没有使用能力返回的最大值
info process(vector<vector<int>>& arr, int i, int j) {
}
之后只要跟着递归三部走
- 找终止条件
- 找可能性
- 返回最终结果
即可
终止条件为 当J == 0的时候 我们只有此时用不用能力这两种选择
可能性就有很多了 总体可以分为两类
- 没用能力
- 用了能力
当然 用了能力还要区分 是不是这次用的
之后如果前面的结果有-1 我们则要将其排除出可能性(即答案设置为-1)
代码
// 数组arr上返回i j位置的info信息
// info信息 使用了能力和没有使用能力返回的最大值
info* process(vector<vector<int>>& arr, int i, int j) {if (j == 0){// 不使用能力 -1表示可能达到int no = arr[i][j] >= 0 ? arr[i][j] : -1;int yes = -arr[i][j] >= 0 ? -arr[i][j] : -1;return new info(no, yes);}// 真正的可能性// 首先肯定有左边int preno = -1;int preyes = -1;auto info1 = process(arr, i, j);preno = max(info1->_no, preno);preyes = max(info1->_yes, preyes);if (i > 0){auto info1 = process(arr, i - 1, j - 1);preno = max(info1->_no, preno);preyes = max(info1->_yes, preyes);}if (i < arr.size() - 1){auto info1 = process(arr, i + 1, j - 1);preno = max(info1->_no, preno);preyes = max(info1->_yes, preyes);}// 列可能性int p1 = preno + arr[i][j];if (p1 < 0){p1 = -1;}if (preno = -1){p1 = -1;}int p2 = preyes + arr[i][j];int p3 = preno - arr[i][j];p2 = max(p2, p3);if (p2 < 0){p2 = -1;}if (preyes = -1){p2 = -1;}if (preno = -1){p3 = -1;}return new info(p1, p2);
}int _process(vector<vector<int>>& arr) {int ans = 0;for (int i = 0; i < arr.size(); i++) {for (int j = 0; j < arr[0].size(); j++){auto res = process(arr, i, j);ans = max(ans, max(res->_no, res->_yes));}}return ans;
}
路径问题 (动态规划)
题目
给定你一个二维数组 二维数组中存放着a~z的二十六个字符 再给你一个字符串str
现在请问 从这个二维数组中的任意一个位置开始找 是否能找到一条路径能组成字符串str
- 如果路径可以重复是否可以组成
- 如果路径不能重复是否可以组成
题目分析
凡是动态规划的题目我们首先来想思路 因为题目中是一个二维数组 所以我们肯定要使用两个变量来标识唯一一个位置
此外对于字符串str 我们也需要一个变量来确定位置
// 这个函数的意义是从i j位置开始 arr中的字符能不能组成包括str[K]位置及其往后所有位置
bool process(vector<vector<char>>& arr, int i, int j, int k) {
}
我们验证当前字符是否符合之后 只需要调用递归函数查看下一个函数是否符合即可
// 这个函数的意义是从i j位置开始 arr中的字符能不能组成包括str[K]位置及其往后所有位置
bool process(vector<vector<char>>& arr, string& str,int i, int j, int k) {if (k == str.size()){return true;}if (i < 0 || i > arr.size() - 1 || j < 0 || j > arr[0].size() - 1 || arr[i][j] != str[k]){return false;}bool ans = false;// 可能性 走到这里说明前面都符合if (process(arr, str, i + 1, j + 1, k + 1) || process(arr, str, i + 1, j - 1, k + 1) || process(arr, str, i - 1, j + 1, k + 1)|| process(arr, str, i - 1, j - 1, k + 1)){ans = true;}return ans;
}
如果不允许路径重复呢?
这个问题的难点实际在于我们如何标记之前走过的路径
这里推荐使用回溯法
我们每次走过一个路径的之后将当前格子标0
之后验证完毕之后再将格子改回去就行
bool process(vector<vector<char>>& arr, string& str,int i, int j, int k) {if (k == str.size()){return true;}if (i < 0 || i > arr.size() - 1 || j < 0 || j > arr[0].size() - 1 || arr[i][j] != str[k]){return false;}arr[i][j] = 0;bool ans = false;// 可能性 走到这里说明前面都符合if (process(arr, str, i + 1, j + 1, k + 1) || process(arr, str, i + 1, j - 1, k + 1) || process(arr, str, i - 1, j + 1, k + 1)|| process(arr, str, i - 1, j - 1, k + 1)){ans = true;}arr[i][j] = str[k];return ans;
}
相关文章:
【C++ 算法进阶】算法提升八
复杂计算 (括号问题相关递归套路 重要) 题目 给定一个字符串str str表示一个公式 公式里面可能有整数 - * / 符号以及左右括号 返回最终计算的结果 题目分析 本题的难点主要在于可能会有很多的括号 而我们直接模拟现实中的算法的话code会难写 要考虑…...
阿里云实时数据仓库HologresFlink
1. 实时数仓Hologres特点 专注实时场景:数据实时写入、实时更新,写入即可见,与Flink原生集成,支持高吞吐、低延时、有模型的实时数仓开发,满足业务洞察实时性需求。 亚秒级交互式分析:支持海量数据亚秒级交…...
生成式语言模型的文本生成评价指标(从传统的基于统计到现在的基于语义)
文本生成评价指标 以 BLEU 为代表的基于统计的文本评价指标基于 BERT 等预训练模型的文本评价指标 1.以 BLEU 为代表的基于统计的文本评价指标 1.BLEU(Bilingual Evaluation Understudy, 双语评估辅助工具) 所有评价指标的鼻祖,核心思想是比较 候选译文 和 参考…...
【网安案例学习】暴力破解攻击(Brute Force Attack)
### 案例与影响 暴力破解攻击在历史上曾导致多次重大安全事件,特别是在用户数据泄露和账户被盗的案例中。随着计算能力的提升和密码管理技术的进步,暴力破解的威胁虽然有所减弱,但仍需警惕,特别是在面对高价值目标时。 【故事一…...
时间序列预测(十八)——实现配置管理和扩展命令行参数解析器
如图,这是一个main,py文件,在此代码中,最开始定义了许多模型参数,为了使项目更加灵活和可扩展,便于根据不同的需求调整参数和配置,可以根据实际需要扩展参数和配置项。 下面是如何实现配置管理和扩展命令行…...
Vue问题汇总解决
作者:fyupeng 技术专栏:☞ https://github.com/fyupeng 项目地址:☞ https://github.com/fyupeng/distributed-blog-system-api 留给读者 我们经常在使用Vue开发遇到一些棘手的问题,解决后通常要进行总结,避免下次重复…...
Spark学习
Spark简介 1.Spark是什么 首先spark是一个计算引擎,而不是存储工具,计算引擎有很多: 第一代:MapReduce廉价机器实现分布式大数据处理 第二代:Tez基于MR优化了DAG,性能比MR快一些 第三代:Spark…...
一些小细节代码笔记汇总
Python cv2抓取摄像头图片保存到本地 import cv2 import datetime, ossavePath "E:/Image/"if not os.path.exists(savePath):os.makedirs(savePath)cap cv2.VideoCapture(0) capture Falseif not cap.isOpened():print("无法打开摄像头")exit()while…...
L4.【LeetCode笔记】链表题的VS平台调试代码
不用调用87.【C语言】数据结构之链表的头插和尾插文章提到的头插函数 记下这个模板代码,可用于在Visual Studio上调试出问题的测试用例 如创建链表[1,2,3,4,5] #include <stdilb.h> // Definition for singly-linked list.struct ListNode {int val;struct ListNode *…...
JavaCV 之高斯滤波:图像降噪与细节保留的魔法
🧑 博主简介:CSDN博客专家,历代文学网(PC端可以访问:https://literature.sinhy.com/#/literature?__c=1000,移动端可微信小程序搜索“历代文学”)总架构师,15年工作经验,精通Java编程,高并发设计,Springboot和微服务,熟悉Linux,ESXI虚拟化以及云原生Docker和K8s…...
VsCode显示空格
ctrl shift p选择Preferences: Open User Settings (JSON) 加上"editor.renderWhitespace": "all" {"cmake.configureOnOpen": true,"files.encoding": "gb2312","editor.fontVariations": false,"edito…...
.Net C# 基于EFCore的DBFirst和CodeFirst
DBFirst和CodeFirst 1 概念介绍 1.1 DBFirst(数据库优先) 含义:这种模式是先创建数据库架构,包括表、视图、存储过程等数据库对象。然后通过实体框架(Entity Framework)等工具,根据已有的数据…...
w012基于springboot的社区团购系统设计
🙊作者简介:拥有多年开发工作经验,分享技术代码帮助学生学习,独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。🌹赠送计算机毕业设计600个选题excel文件,帮助大学选题。赠送开题报告模板ÿ…...
笔记本降频超鬼锁屏0.39电脑卡到不行解决办法实操记录
1、最开始没发现cpu问题,我发现我电脑突然异常的卡顿,最开始我怀疑是不是微软win用久了或者自动更新导致的问题,于是自己重装了操作系统 发现问题依然存在 2、我怀疑难道我的 cpu 内存 固态硬盘 其中一个有点问题?心想要是硬盘的…...
优选算法第四讲:前缀和模块
优选算法第四讲:前缀和模块 1.[模板]前缀和2.【模板】二维前缀和3.寻找数组的中心下标4.除自身以外数组的乘积5.和为k的子数组6.和可被k整除的子数组7.连续数组8.矩阵区域和 1.[模板]前缀和 链接: link #include <iostream> #include <vector> using…...
ubuntu20.04 加固方案-设置限制su命令用户组
一、编辑/etc/pam.d/su配置文件 打开终端。 使用文本编辑器(如vim)编辑/etc/pam.d/su文件。 vim /etc/pam.d/su 二、添加配置参数 在打开的配置文件的中,添加以下参数: auth required pam_wheel.so 创建 wheel 组 并添加用户 …...
TDengine数据备份与恢复
TDengine数据备份与恢复 一、数据备份和恢复介绍二、基于 taosdump 进行数据备份恢复三、基于 taosExplorer 进行数据备份恢复3.1 taosExplorer 的安装与配置3.2 使用taosExplorer 进行数据备份 一、数据备份和恢复介绍 官网地址:TDengine - 数据备份和恢复 为了防止…...
2024最新的开源博客系统:vue3.x+SpringBoot 3.x 前后端分离
本文转载自:https://fangcaicoding.cn/article/54 大家好!我是方才,目前是8人后端研发团队的负责人,拥有6年后端经验&3年团队管理经验,截止目前面试过近200位候选人,主导过单表上10亿、累计上100亿数据…...
研究中的“异质性”、“异质性结果”是指?
“异质性”这个词在统计学和研究中指的是数据、现象或群体之间的差异,即不同个体、组别、区域或时间点的表现或特征并不相同。相对的概念是“同质性”,即所有个体或组别在某一方面表现相同或接近。 异质性(Heterogeneity)的含义 …...
Springboot整合AOP和redis
aop pom.xml <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-aop</artifactId> </dependency> 开启自动代理 注意:在完成了引入AOP依赖包后,一般来说并不需要去做其他…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...
