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

每天算法刷题Day53:7.25:leetcode 栈5道题,用时1h35min

3. 1021. 删除最外层的括号(简单)

1021. 删除最外层的括号 - 力扣(LeetCode)

思想

1.有效括号字符串为空 """(" + A + ")" 或 A + B ,其中 A 和 B 都是有效的括号字符串,+ 代表字符串的连接。

  • 例如,"""()""(())()" 和 "(()(()))" 都是有效的括号字符串。
    如果有效字符串 s 非空,且不存在将其拆分为 s = A + B 的方法,我们称其为原语(primitive),其中 A 和 B 都是非空有效括号字符串。
    给出一个非空有效字符串 s,考虑将其进行原语化分解,使得:s = P_1 + P_2 + ... + P_k,其中 P_i 是有效括号字符串原语。
    对 s 进行原语化分解,删除分解中每个原语字符串的最外层括号,返回 s 。
    2.简单来说就是从左向右不停地的获取满足左右括号完全匹配的原语,然后去掉最外层括号,放入答案中,可以利用分值有效性方法,左右括号完全匹配,即score=0,记录最外层左括号括号的位置pre,当前最外层右括号位置i,然后把[pre+1,i)插入到res中即可
代码
class Solution {
public:string removeOuterParentheses(string s) {int n = s.size();int score = 0;string res;int pre = 0;for (int i = 0; i < n; ++i) {if (s[i] == '(')++score;else--score;if (score == 0) {// [pre+1,i)res.insert(res.end(), s.begin() + pre + 1, s.begin() + i);pre = i + 1;}}return res;}
};
4. 1614. 括号的最大嵌套深度(简单)

1614. 括号的最大嵌套深度 - 力扣(LeetCode)

思想

1.给定 有效括号字符串 s,返回 s 的 嵌套深度。嵌套深度是嵌套括号的 最大 数量。
2.嵌套深度即有效性分值score的绝对值的最大值

代码
class Solution {
public:int maxDepth(string s) {int n = s.size();int res = 0;int score = 0;for (int i = 0; i < n; ++i) {if (s[i] == '(')++score;else if (s[i] == ')')--score;res = max(res, abs(score));}return res;}
};
5. 1190. 反转每对括号间的子串(中等)

1190. 反转每对括号间的子串 - 力扣(LeetCode)

思想

1.给出一个字符串 s(仅含有小写英文字母和括号)。
请你按照从括号内到外的顺序,逐层反转每对匹配括号中的字符串,并返回最终的结果。
注意,您的结果中 不应 包含任何括号。
2.因为括号具有对称性,所以想到先将这一层连同括号一起反转,所以要记录这一层左括号的下标,用栈维护,然后直接原地反转字符串s,最后删除左右括号即可

代码
class Solution {
public:string reverseParentheses(string s) {int n = s.size();vector<int> stk;for (int i = 0; i < n; ++i) {if (s[i] == '(')stk.push_back(i);else if (s[i] == ')') {int pre = stk.back();// 反转[pre,i]reverse(s.begin() + pre, s.begin() + i + 1);stk.pop_back();}}s.erase(remove(s.begin(), s.end(), '('), s.end());s.erase(remove(s.begin(), s.end(), ')'), s.end());return s;}
};
6. 856. 括号的分数(中等,学习)

856. 括号的分数 - 力扣(LeetCode)

思想

1.给定一个平衡括号字符串 S,按下述规则计算该字符串的分数:

  • () 得 1 分。
  • AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。
  • (A) 得 2 * A 分,其中 A 是平衡括号字符串。
    2.初始化将答案 0 放入栈中(后面逻辑决定的),从前往后处理整个 s,当遇到(则存入一个占位数值 0,遇到 ) 取出栈顶元素 cur,根据栈顶元素数值分情况讨论:
  • 栈顶元素 cur=0,即当前的 ) 的前一元素就是 ( ,根据 () 得一分的规则可知,我们本次操作得到的分值为 1;
  • 栈顶元素 cur!=0,即当前 ) 与其匹配的 ( 中间相隔了其他字符,根据 (A) 的得分规则,此时可知得分为 cur×2
    将两者结合可统一为 max(cur×2,1)
    由于我们每次遇到 ) 时,都将最近一次操作计算出来。而再前面无论是 ) 还是 ( 我们都可以归结到 X() 的相邻项累加规则,将其新得分累加到栈顶元素上,其中 ( 仍采用累加规则,则利用我们将 ( 定义为 0 的设定。
代码
class Solution {
public:int scoreOfParentheses(string s) {int n = s.size();vector<int> stk;stk.push_back(0);for (int i = 0; i < n; ++i) {if (s[i] == '(')stk.push_back(0);else {int cur = max(stk.back() * 2, 1);stk.pop_back();stk.back() += cur;}}return stk.back();}
};
7. 1249. 移除无效的括号(中等)

1249. 移除无效的括号 - 力扣(LeetCode)

思想

1.给你一个由 '('')' 和小写字母组成的字符串 s
你需要从字符串中删除最少数目的 '(' 或者 ')' (可以删除任意位置的括号),使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求:

  • 空字符串或只包含小写字母的字符串
  • 可以被写作 ABA 连接 B)的字符串,其中 A 和 B 都是有效「括号字符串」
  • 可以被写作 (A) 的字符串,其中 A 是一个有效的「括号字符串」
    2,我采用了边遍历边删除的方法,首先删除一个字符的方法为s.erase(pos,1),然后边遍历边删除会面临2个问题:
  • 遍历退出条件为s.size(),不能再写n,因为在动态变化
  • 从前往后删除完i--i,然后++i,保证i为下一个遍历元素,否则会跳过一个
    然后还要考虑只剩左括号的也要删除,但因为栈是后入先出,相当于从后往前删,不会影响i,不用--i
    3.也可以用一个数组来记录要不要删除,然后再将s迁移到答案中
代码
class Solution {
public:string minRemoveToMakeValid(string s) {int n = s.size();vector<int> stk;// 动态删除s,则遍历条件为s.size(),不能写nfor (int i = 0; i < s.size(); ++i) {if (s[i] == '(') {stk.push_back(i);} else if (s[i] == ')') {if (stk.empty()) {s.erase(i, 1);// 删除完要遍历下一个元素,先回退一个,然后会有++i--i;} else {stk.pop_back();}}}while (!stk.empty()) {int i = stk.back();s.erase(i, 1);stk.pop_back();}return s;}
};
http://www.lryc.cn/news/599344.html

相关文章:

  • [C#] Winform - 加载动画效果
  • 【blender小技巧】使用blender实现图转换为3D模型,并进行模型网格优化减面操作
  • 【C#学习Day12笔记】抽象类、密封类与子类构造(继承)
  • Welcome to the world of Go language
  • blender基本操作
  • gem5和Spike区别
  • 设计模式在Java中的实际应用:单例、工厂与观察者模式详解
  • AVL树和红黑树的特性以及模拟实现
  • 【开发杂谈】用AI玩AI聊天游戏:使用 Electron 和 Python 开发大模型语音聊天软件
  • golang怎么实现每秒100万个请求(QPS),相关系统架构设计详解
  • MyBatis 之缓存机制核心解析
  • “磁”力全开:钕铁硼重塑现代科技生活
  • 求职招聘小程序源码招聘小程序开发定制
  • 解密国密 SSL 证书:SM2、SM3、SM4 算法的协同安全效应
  • Spring Boot 接口安全设计:接口限流、防重放攻击、签名验证
  • SEC_FirePower 第二天作业
  • 软件异常读写威胁硬盘安全:从过往案例到防护之道
  • Linux运维新人自用笔记(Rsync远程传输备份,服务端、邮箱和客户端配置、脚本)
  • 网络资源模板--基于Android Studio 实现的天气预报App
  • Inception网络架构:深度学习视觉模型的里程碑
  • Java-Properties类和properties文件详解
  • android app适配Android 15可以在Android studio自带的模拟器上进行吗,还是说必须在真机上进行
  • 【Android Studio】安装Trae插件后Android Studio 启动崩溃问题处理
  • AR眼镜重塑外科手术导航:精准“透视”新突破
  • 深入理解 TCP 协议:从原理到实践的技术解析
  • 机器学习之knn算法保姆级教学
  • 扣子平台之提示词生成
  • 双指针算法介绍及使用(下)
  • 进阶向:基于Python的局域网聊天工具(端对端加密)
  • Amazon Bedrock中的Stability AI文本转图像模型:技术原理、应用实践与未来趋势