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

leetcode301. 删除无效的括号(java)

删除无效的括号

  • leetcode301. 删除无效的括号
    • 题目描述
    • 暴力搜索 + 剪枝
    • 代码演示
  • 回溯算法

leetcode301. 删除无效的括号

难度 困难
https://leetcode.cn/problems/remove-invalid-parentheses/description/

题目描述

给你一个由若干括号和字母组成的字符串 s ,删除最小数量的无效括号,使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1:
输入:s = “()())()”
输出:[“(())()”,“()()()”]

示例 2:
输入:s = “(a)())()”
输出:[“(a())()”,“(a)()()”]

示例 3:
输入:s = “)(”
输出:[“”]

提示:
1 <= s.length <= 25
s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
s 中至多含 20 个括号

暴力搜索 + 剪枝

由于题目要求我们将所有(最长)合法方案输出,因此不可能有别的优化,只能进行「递归搜索」。

基本思路:
我们知道所有的合法方案,必然有左括号的数量与右括号数量相等。
首先我们令左括号的得分为 1;右括号的得分为 −1。则会有如下性质:
对于一个合法的方案而言,必然有最终得分为 0;
搜索过程中不会出现得分值为 负数 的情况(当且仅当子串中某个前缀中「右括号的数量」大于「左括号的数量」时,会出现负数,此时不是合法方案)。
同时我们可以预处理出「爆搜」过程的最大得分: max = min(左括号的数量, 右括号的数量)

PS.「爆搜」过程的最大得分必然是:合法左括号先全部出现在左边,之后使用最多的合法右括号进行匹配。

枚举过程中出现字符分三种情况:
左括号:如果增加当前 ( 后,仍为合法子串(即 score+1<=max) 时,我们可以选择添加该左括号,也能选择不添加;
右括号:如果增加当前 ) 后,仍为合法子串(即 score−1>=0) 时,我们可以选择添加该右括号,也能选择不添加;
普通字符:直接添加。

使用 Set 进行方案去重,lenlenlen 记录「爆搜」过程中的最大子串,然后只保留长度等于 lenlenlen 的子串。

代码演示

class Solution {HashSet<String> set = new HashSet<>();String _s;int n,max,len;/*** 删除无效括号* @param s* @return*/public List<String> removeInvalidParentheses(String s) {_s = s;n = s.length();int l = 0, r = 0;int l1 = 0,r1 = 0;for (char c : s.toCharArray()){if (c == '('){l++;l1++;} else if (c == ')') {r1++;if (l != 0){l--;}else {r++;}}}//最大长度len = s.length() - l - r;//左括号和右括号最小数量max = Math.min(l1,r1);dfs(0,"",l,r,0);return new ArrayList<>(set);}/*** 递归* @param index 当前来到的位置* @param cur 选择的字符串* @param l 左边括号 比右边多几个* @param r 右边括号 比左边多几个* @param score 选择的个数*/public void dfs(int index,String cur,int l,int r,int score){//base case 越界条件 直接返回if (l < 0 || r < 0 || score < 0 || score > max){return;}//满足条件 加入到答案中if (l == 0 && r == 0 && cur.length() == len){set.add(cur);}//base case 越界 直接返回if (index == n){return;}char c = _s.charAt(index);if (c == '('){//选择的情况dfs(index + 1,cur + String.valueOf(c),l,r,score + 1);//删除当前括号的情况dfs(index + 1,cur,l - 1,r,score);} else if (c == ')') {//选择的情况dfs(index + 1,cur + String.valueOf(c),l,r,score - 1);//删除当前括号的情况dfs(index + 1,cur,l,r - 1,score);}else {//字符直接加进去dfs(index + 1,cur + String.valueOf(c),l,r,score);}}
}

回溯算法

leetcode212. 单词搜索 II

leetcode1219. 黄金矿工

leetcode306. 累加数

相关文章:

leetcode301. 删除无效的括号(java)

删除无效的括号 leetcode301. 删除无效的括号题目描述暴力搜索 剪枝代码演示 回溯算法 leetcode301. 删除无效的括号 难度 困难 https://leetcode.cn/problems/remove-invalid-parentheses/description/ 题目描述 给你一个由若干括号和字母组成的字符串 s &#xff0c;删除最小…...

快速制作美容行业预约小程序

随着科技的不断进步&#xff0c;移动互联网的快速发展&#xff0c;小程序成为了很多行业迅速发展的利器。对于美容行业来说&#xff0c;一款美容预约小程序不仅可以方便用户进行预约&#xff0c;还可以提升美容店铺的服务质量和管理效率。下面&#xff0c;我们来介绍一下如何快…...

Golang之路---03 面向对象——结构体

结构体 结构体定义 在之前学过的数据类型中&#xff0c;数组与切片&#xff0c;只能存储同一类型的变量。若要存储多个类型的变量&#xff0c;就需要用到结构体&#xff0c;它是将多个任意类型的变量组合在一起的聚合数据类型。 每个变量都成为该结构体的成员变量。   可以理…...

【网络编程】poll

主旨思想 用一个结构体记录文件描述符集合&#xff0c;并记录用户态状态和内核态状态 函数说明 概览 #include <poll.h> struct pollfd { int fd; /* 委托内核检测的文件描述符 */ short events; /* 委托内核检测文件描述符的什么事件 */ short revents; /* 文件描述…...

配置VS Code 使其支持vue项目断点调试

起因 每个应用&#xff0c;不论大小&#xff0c;都需要理解程序是如何运行失败的。当我们写的程序没有按照自己写的逻辑走的时候&#xff0c;我们就会逐步一一排查问题。在平常开发过程中我们可能会借助 console.log 来排查,但是现在我们可以借助 VS Code 断点来调试项目。 前…...

第一百零一回 如何在组件树之间共享数据

文章目录 概念介绍使用方法示例代码 我们在上一章回中介绍了"如何实现文件存储"相关的内容&#xff0c;本章回中将介绍 如何实现组件之间共享数据。闲话休提&#xff0c;让我们一起Talk Flutter吧。 概念介绍 数据共享是程序中常用的功能&#xff0c;本章回介绍如何…...

Golang进阶学习

Golang进阶学习 视频地址&#xff1a;https://www.bilibili.com/video/BV1Pg41187AS?p35 1、包 1.1、包的引入 使用包的原因&#xff1a; 我们不可能把所有函数放在同一个源文件中&#xff0c;可以分门别类的放在不同的文件中 解决同名问题&#xff0c;同一个文件中不可以…...

【Linux】常用的基本指令

&#x1f466;个人主页&#xff1a;Weraphael ✍&#x1f3fb;作者简介&#xff1a;目前正在学习c和算法 ✈️专栏&#xff1a;Linux &#x1f40b; 希望大家多多支持&#xff0c;咱一起进步&#xff01;&#x1f601; 如果文章有啥瑕疵&#xff0c;希望大佬指点一二 如果文章对…...

栈溢出几种情况及解决方案

一、局部数组过大。当函数内部的数组过大时&#xff0c;有可能导致堆栈溢出。 二、递归调用层次太多。递归函数在运行时会执行压栈操作&#xff0c;当压栈次数太多时&#xff0c;也会导致堆栈溢出。 三、指针或数组越界。这种情况最常见&#xff0c;例如进行字符串拷贝&#…...

go 内存分配

关注 go 语言内存分配策略&#xff0c;主要是想了解 go 的性能。申请不同大小的内存&#xff0c;性能开销是有差别的&#xff0c;申请内存越大&#xff0c;耗时也越久&#xff0c;性能也越差。 内存分配 参考 Go1.17.13 版本源码&#xff0c;从内存分配大小上区分了 tiny、sm…...

Maven pom.xml文件中build,plugin标签的具体使用

<build> 标签 <build> 标签是 pom.xml 文件中一个重要的标签&#xff0c;用于配置 Maven 项目的构建过程。在 <build> 标签下&#xff0c;可以配置构建相关的设置&#xff0c;包括源代码目录、输出目录、插件配置等。 以下是 <build> 标签的详细使用方…...

批量插入数据、MVC三层分离

八、批量插入数据 1、使用Statement&#xff08;&#xff09; 2、使用PreparedStatement() 3、使用批量操作API 4、优化 九、MVC三层分离...

【IMX6ULL驱动开发学习】21.Linux驱动之PWM子系统(以SG90舵机为例)

1.设备树部分 首先在 imx6ull.dtsi 文件中已经帮我们定义好了一些pwm的设备树节点&#xff0c;这里以pwm2为例 pwm2: pwm02084000 {compatible "fsl,imx6ul-pwm", "fsl,imx27-pwm";reg <0x02084000 0x4000>;interrupts <GIC_SPI 84 IRQ_TYP…...

el-cascader级联选择器加载远程数据、默认开始加载固定条、可以根据搜索加载远程数据。

加载用户列表分页请求、默认请求20条数据。想添加远程搜索用户功能。原有的方法filter-method不能监听到输入清空数据的时候。这样搜索完无法返回默认的20条数据。直接监听级联选择的v-model绑定的值是无法检测到用户自己输入的。 解决思路&#xff1a; el-cascader 没有提供…...

大数据技术之Clickhouse---入门篇---SQL操作、副本

星光下的赶路人star的个人主页 积一勺以成江河&#xff0c;累微尘以崇峻极 文章目录 1、SQL操作1.1 Insert1.2 Update 和 Delete1.3 查询操作1.4 alter操作1.5 导出数据 2、副本2.1 副本写入流程2.2 配置步骤 1、SQL操作 基本上来说传统关系型数据库&#xff08;以 MySQL 为例…...

【Rust 基础篇】Rust Sized Trait:理解Sized Trait与动态大小类型

导言 Rust是一门以安全性和性能著称的系统级编程语言。在Rust中&#xff0c;类型大小的确定在编译期是非常重要的。然而&#xff0c;有些类型的大小在编译期是无法确定的&#xff0c;这就涉及到了Rust中的动态大小类型&#xff08;DST&#xff09;。为了保证在编译期可以确定类…...

前端框架学习-Vue(三)

目录 初识VueVue模板语法数据绑定el和data的两种写法事件的基本使用$emit在子组件中定义方法&#xff0c;执行父组件的方法 Vue中的事件修饰符&#xff1a;键盘事件计算属性监视属性条件渲染列表渲染表单数据收集过滤器 笔记内容来自&#xff1a;尚硅谷Vue2.0Vue3.0全套教程丨v…...

HTML <rt> 标签

实例 一个 ruby 注释&#xff1a; <ruby> 漢 <rt> ㄏㄢˋ </rt> </ruby>浏览器支持 元素ChromeIEFirefoxSafariOpera<rt>5.05.538.05.015.0 Internet Explorer 9, Firefox, Opera, Chrome 以及 Safari 支持 <rt> 标签。 注释&#xf…...

VMware Linux Centos 配置网络并设置为静态ip

在root用户下进行以下操作 1. 查看子网ip和网关 &#xff08;1&#xff09;进入虚拟网络编辑器 &#xff08;2&#xff09;进入NAT设置 &#xff08;3&#xff09;记录子网IP和子网掩码 2. 修改网络配置文件 &#xff08;1&#xff09;cd到网络配置文件路径下 [rootlo…...

【Leetcode 30天Pandas挑战】学习记录

这个系列难度比较低&#xff0c;一题写一篇其实没必要&#xff0c;就全部放到一篇吧 题目列表&#xff1a; 595. Big Countries1757. Recyclable and Low Fat Products 595. Big Countries 原题链接&#xff1a;595. Big Countries Table: World ---------------------- | C…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...