当前位置: 首页 > 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->项目输出->主输出…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

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

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

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...