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

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

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 …...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

Canal环境搭建并实现和ES数据同步

作者&#xff1a;田超凡 日期&#xff1a;2025年6月7日 Canal安装&#xff0c;启动端口11111、8082&#xff1a; 安装canal-deployer服务端&#xff1a; https://github.com/alibaba/canal/releases/1.1.7/canal.deployer-1.1.7.tar.gz cd /opt/homebrew/etc mkdir canal…...

Python环境安装与虚拟环境配置详解

本文档旨在为Python开发者提供一站式的环境安装与虚拟环境配置指南&#xff0c;适用于Windows、macOS和Linux系统。无论你是初学者还是有经验的开发者&#xff0c;都能在此找到适合自己的环境搭建方法和常见问题的解决方案。 快速开始 一分钟快速安装与虚拟环境配置 # macOS/…...

React父子组件通信:Props怎么用?如何从父组件向子组件传递数据?

系列回顾&#xff1a; 在上一篇《React核心概念&#xff1a;State是什么&#xff1f;》中&#xff0c;我们学习了如何使用useState让一个组件拥有自己的内部数据&#xff08;State&#xff09;&#xff0c;并通过一个计数器案例&#xff0c;实现了组件的自我更新。这很棒&#…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架

文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理&#xff1a;检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目&#xff1a;RankRAG&#xff1a;Unifying Context Ranking…...