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

日志| 编辑距离 | 最长有效括号 |

力扣

局部截取_20250926_173631

解题思路

动态规划核心思想 :初始化 + 填充

第一次提交
1状态转移:
左上到cur 是 替换(相同则继承左上)
上到cur 是 删除
左到cur 是 添加

2初始化:
第一行=空字符变成目标字符串的次数
第一列=原字符串变成空字符串的次数
3填充:
若 两字符相等 cur等于左上角
若 两字符不相等 cur等于(左上或者左或者上的最小值)+1

局部截取_20250926_185905
第二次提交
二维数组变成一维数组,每次只需要覆盖上一行的数组。
一层迭代需要记住 当前行的 左上角left_up左边的第一个dp[0]
二层迭代需要记住 当前的dp[j] 是 下一个数的左上角
局部截取_20250926_194344

优化:
第一种方法空间复杂度度O(m * n)
第二种方法空间复杂度O(n)
局部截取_20250926_200022

解题思路

第一次提交
1创建boolean数组存储每个符号对应的TRUE OR FASLE
2遍历
若是左括号索引入栈
若是右括号检查更新bool数组
3算一下最大长度
局部截取_20250926_201415

点击查看代码
class Solution {public int longestValidParentheses(String s) {if(s.length() == 0) return 0;int n = s.length();Stack<Integer> stack = new Stack<>();boolean[] test = new boolean[n];for(int i = 0 ; i < n ; i++){char cur = s.charAt(i);if(cur == '('){stack.push(i);}else{if(!stack.isEmpty()){int a = stack.pop();test[a] = true;test[i] = true;}}}int maxLen = 0;int curmax = 0;for(int i = 0 ; i < n ; i++){if(test[i] == true){curmax += 1;}else{maxLen = Math.max(maxLen,curmax);curmax = 0;}}maxLen = Math.max(maxLen, curmax);//易错点:如果有小括号在末尾,会不更新最大值return maxLen;}
}
http://www.hskmm.com/?act=detail&tid=18316

相关文章:

  • day5
  • 《etcd库——键值存储系统》 - 教程
  • 有一个函数只会返回0和1,且返回0和返回1的概率不等。要求只能通过这个函数生成一个等概率返回0和1的函数
  • AI智能体开发实战:17种核心架构模式详解与Python代码实现
  • 代码随想录算法训练营第十天 | 232. 用栈实现队列、225. 用队列实现栈、20. 有效的括号、删除字符串中的所有相邻重复项
  • 2025.9.26总结 - A
  • MySQL性能优化
  • 关于“悬荡悟空”决策机制的简要技术说明
  • 最小二乘问题详解1:线性最小二乘
  • 9月26日
  • 工程监理行业多模态视觉​​​​​​​大模型系统,打造工地行业全场景的监理智能生态
  • 完整教程:【鸿蒙心迹】摸蓝图,打地基
  • 正则表达式
  • LuatOS Air780EPM 实现 HTTP 通信:从原理到代码实践
  • 搜维尔科技:Senseglove Nova 2触觉手套:虚拟训练、VR/AR模拟和研究中的触觉反馈
  • 深入解析:盟接之桥EDI软件:中国制造全球化进程中的连接挑战与路径探索
  • 【STM32H7】基于CubeMX从零开始搭建的HAL库工程模板(包含串口重定向和DSP库)
  • 在Windows架构中安装Miniforge及python环境变量配置
  • 搜维尔科技:Force Dimension Omega力反馈设备遥操作工业机器人
  • 3. Ollama 安装,流式输出,多模态,思考模型 - Rainbow
  • C++程序练习(部分未完全完成)
  • C#性能优化基础:垃圾回收机制
  • 实验报告1
  • 2025.9.26——1蓝
  • 根号
  • 【A】杂题选将
  • 有一个[1,5]的等概率随机函数fx(),在不改变fx()函数的情况下,利用fx()函数做出一个[1,7]的等概率随机函数。
  • WSL2 磁盘清理
  • 质因数分解
  • 关于OneBot的QQ机器人探索2