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

【递归 回溯】LeetCode-301. 删除无效的括号

301. 删除无效的括号。

给你一个由若干括号和字母组成的字符串 s ,删除最小数量的无效括号,使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1:

输入:s = "()())()"
输出:["(())()","()()()"]

示例 2:

输入:s = "(a)())()"
输出:["(a())()","(a)()()"]

示例 3:

输入:s = ")("
输出:[""]

提示:

1 <= s.length <= 25
s 由小写英文字母以及括号 '(' 和 ')' 组成
s 中至多含 20 个括号
算法分析

解题思路
满足有效括号序列的性质

  • 1、前缀序列中左括号的数量>=右括号的数量
  • 2、左括号的数量=右括号的数量
    DFS
class Solution {List<String> res;public List<String> removeInvalidParentheses(String s) {res = new ArrayList<>();int l = 0;int r = 0;for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '(') {l++;}if (s.charAt(i) == ')') {if (l > 0) {l--;} else {r++;}}}dfs(s, 0, 0, l, r, "");return res;}public void dfs(String s, int u, int cnt, int l, int r, String path) {if (u == s.length()) {if (cnt == 0) {res.add(path);}return;}if (s.charAt(u) != '(' && s.charAt(u) != ')') {dfs(s, u + 1, cnt, l, r, path + s.charAt(u));} else {if (s.charAt(u) == '(') {int k = u;while (k < s.length() && s.charAt(k) == '(') {k++;}l -= k - u;for (int i = k - u; i >= 0; i--) {if (l >= 0) {dfs(s, k, cnt, l, r, path);}path += '(';l++;cnt++;}}if (s.charAt(u) == ')') {int k = u;while (k < s.length() && s.charAt(k) == ')') {k++;}r -= k - u;for (int i = k - u; i >= 0; i--) {if (cnt >= 0 && r >= 0) {dfs(s, k, cnt, l, r, path);}path += ')';r++;cnt--;}}}}
}

复杂性分析

时间复杂度:O(2^n * n)
空间复杂度:O(n)

相关文章:

【递归 回溯】LeetCode-301. 删除无效的括号

301. 删除无效的括号。 给你一个由若干括号和字母组成的字符串 s &#xff0c;删除最小数量的无效括号&#xff0c;使得输入的字符串有效。 返回所有可能的结果。答案可以按 任意顺序 返回。 示例 1&#xff1a; 输入&#xff1a;s "()())()" 输出&#xff1a;[…...

C++ 基本的输入输出

C 标准库提供了一组丰富的输入/输出功能&#xff0c;我们将在后续的章节进行介绍。本章将讨论 C 编程中最基本和最常见的 I/O 操作。 C 的 I/O 发生在流中&#xff0c;流是字节序列。如果字节流是从设备&#xff08;如键盘、磁盘驱动器、网络连接等&#xff09;流向内存&#…...

vue3老项目如何引入vite

vue3老项目如何引入vite 安装 npm install vite vitejs/plugin-vue --save-dev Vite官方中文文档修改package.json文件 在 npm scripts 中使用 vite 执行文件 "scripts": {"serve": "vite","build": "vite build","pr…...

javaEE -19(9000 字 JavaScript入门 - 4)

一&#xff1a; jQuery jQuery是一个快速、小巧且功能丰富的JavaScript库。它旨在简化HTML文档遍历、事件处理、动画效果以及与后端服务器的交互等操作。通过使用jQuery&#xff0c;开发者可以以更简洁、更高效的方式来编写JavaScript代码。 jQuery提供了许多易于使用的方法和…...

二叉树的非递归遍历|前中后序遍历

二叉树的非递归遍历 文章目录 二叉树的非递归遍历前序遍历-栈层序遍历-队列中序遍历-栈后序遍历-栈 前序遍历-栈 首先我们应该创建一个Stack 用来存放节点&#xff0c;首先我们想要打印根节点的数据&#xff0c;此时Stack里面的内容为空&#xff0c;所以我们优先将头结点加入S…...

开源minio-AWS-S3存储的部署及go操作详细

介绍 MinIO是一个开源的分布式对象存储服务&#xff0c;它允许用户在私有云或公有云环境中构建自己的对象存储基础设施。MinIO旨在提供高性能、高可用性的对象存储&#xff0c;并且与Amazon S3兼容&#xff0c;这意味着可以使用S3客户端工具和库直接与MinIO交互&#xff0c;而…...

【Web2D/3D】Canvas(第三篇)

1. 前言 <canvas>是HTML5新增元素&#xff0c;它是一个画板&#xff0c;开发人员基于它的2D上下文或webgl上下文&#xff0c;使用JS脚本绘制简单的动画、可交互画面&#xff0c;甚至进行视频渲染。 本篇介绍基于canvas的2D上下文绘制2D画面的一些方法和属性。 2. canvas…...

紫光展锐T820与飞桨完成I级兼容性测试 助推端侧AI融合创新

近日&#xff0c;紫光展锐高性能5G SoC T820与百度飞桨完成I级兼容性测试&#xff08;基于Paddle Lite工具&#xff09;。测试结果显示&#xff0c;双方兼容性表现良好&#xff0c;整体运行稳定。这是紫光展锐加入百度“硬件生态共创计划”后的阶段性成果。 本次I级兼容性测试完…...

3DV 2024 Oral | SlimmeRF:可动态压缩辐射场,实现模型大小和建模精度的灵活权衡

目前大多数NeRF模型要么通过使用大型模型来实现高精度&#xff0c;要么通过牺牲精度来节省内存资源。这使得任何单一模型的适用范围受到局限&#xff0c;因为高精度模型可能无法适应低内存设备&#xff0c;而内存高效模型可能无法满足高质量要求。为此&#xff0c;本文研究者提…...

【unity学习笔记】4.场景切换

创建空物体→创建脚本挂载在空物体上→打开脚本 1.创建所需要的场景 assets中点击创建场景 2.文件→生成设置 3.将需要的场景拖入 4.场景跳转 创建空对象&#xff0c;将脚本放在空对象上。 注意两个类&#xff1a;场景类、场景管理类 void Start(){//场景跳转SceneManager.Lo…...

LeetCode75| 滑动窗口

目录 643 子数组最大平均数 | 1456 定长子串中元音的最大数目 1004 最大连续1的个数 ||| 1493 删掉一个元素以后全为1的最长子数组 643 子数组最大平均数 | class Solution { public:double findMaxAverage(vector<int>& nums, int k) {double sum 0;double re…...

gulimall-002 分布式基础概念

1、微服务概念 微服务是一种非常流行的架构风格。 拒绝大型单体应用&#xff0c;基于业务边界进行服务微化拆分&#xff0c;各个服务独立部署运行。 每个服务运行在自己的单个进程使用轻量级机制通信可以使用不同的编程语言编写以及不同的数据存储技术 2、集群&分布式&…...

K8s之声明式APIs

大家好&#xff0c;我是升仔 引言 Kubernetes&#xff08;K8s&#xff09;是一个开源的容器编排系统&#xff0c;用于自动化部署、扩展和管理容器化应用。在K8s中&#xff0c;声明式APIs&#xff08;Application Programming Interfaces&#xff09;是一种核心概念&#xff0…...

Hive执行计划

Hive提供了explain命令来展示一个查询的执行计划&#xff0c;这个执行计划对于我们了解底层原理&#xff0c;Hive 调优&#xff0c;排查数据倾斜等很有帮助。 使用语法如下&#xff1a; explain query;在 hive cli 中输入以下命令(hive 2.3.7)&#xff1a; explain select s…...

Leetcode—62.不同路径【中等】

2023每日刷题&#xff08;七十二&#xff09; Leetcode—62.不同路径 超时dfs代码 class Solution { public:int uniquePaths(int m, int n) {int starti 1, startj 1;int ans 0;function<void(int, int)> dfs [&](int i, int j) {if(i m && j n) {a…...

【汇编笔记】初识汇编-内存读写

汇编语言的由来&#xff1a; CPU是计算机的核心&#xff0c;由于计算机只认识二进制&#xff0c;所以CPU执行的指令是二进制。 我们要想让CPU工作&#xff0c;就得给他提供它认识的指令&#xff0c;这一系列的指令的集合&#xff0c;称之为指令集。 指令集&#xff1a; 不同的体…...

Shell脚本通过渗透测试检测服务器安全!

以下是一个简单的 Shell 脚本通过渗透测试来发现服务器漏洞的例子&#xff1a; #!/bin/bash # 设置变量 server_url"http://example.com" server_port"80" script_path"/path/to/script.脚本" # 创建并打开 Web 服务器 web_server$(curl -s $se…...

数据结构--查找

目录 1. 查找的基本概念 2. 线性表的查找 3. 树表的查找 3.1 二叉排序树 3.1.1 定义: 3.1.2 存储结构&#xff1a; 3.1.3 二叉排序树的查找 3.1.4 二叉排序树的插入 3.1.5 二叉排序树删除 3.2 平衡二叉树&#xff08;AVL 3.2.1 为什么要有平衡二叉树 3.2.2 定义 3.3 B-树 3.3.1…...

IntelliJ IDEA Apache Dubbo,IDEA 官方插件正式发布!

作者&#xff1a;刘军 最受欢迎的 Java 集成开发环境 IntelliJ IDEA 与开源微服务框架 Apache Dubbo 社区强强合作&#xff0c;给广大微服务开发者带来了福音。与 IntelliJ IDEA 2023.2 版本一起&#xff0c;Jetbrains 官方发布了一款全新插件 - Apache Dubbo in Spring Frame…...

使用Visual Studio 2022 winform项目打包成安装程序.exe

winform项目打包 1.安装扩展插件 Microsoft Visual Studio Installer Projects 20222.在解决方案上新建一个setup project 项目3.新建成功如下图&#xff0c;之后添加你的winform程序生成之后的debug下的文件4.在Application Folder上点击右键->Add->项目输出->主输出…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

CSS3相关知识点

CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...