【字符串】【括号匹配】【广度优先】301. 删除无效的括号

作者推荐

【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素

本文涉及知识点

字符串 括号匹配 广度优先

LeetCode301 删除无效的括号

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = “()())()”
输出：[“(())()”,“()()()”]
示例 2：
输入：s = “(a)())()”
输出：[“(a())()”,“(a)()()”]
示例 3：
输入：s = “)(”
输出：[“”]
提示：
1 <= s.length <= 25
s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
s 中至多含 20 个括号

预备知识

合法括号的定义：
一，()是合法括号。
二,A和B是合法括号。则AB也是合法括号。A=() B = () 则()()是合法括号。
三，(A)是合法括号。A=()()，则(()())是合法括号。
性质：
num=0,从左到右解析括号，遇到(++，遇到)–。性质一：num任何时候都不能为负。性质二：num最终必须为0。
定义是性质的充分条件容易证明，下面来证明必要条件。
令num1[i]是s[0,i]的num之和。
n u m 1 [ i ] 是合法括号 → i 一定不为 0 因为 n u m 1 [ 0 ] 只能是 1 或 − 1 n u m 1 [ i − 1 ] > = 0 , 所以 s [ i ] 只能是 ) ，否则 n u m 1 [ i ] > = 0 + 1 s [ 0 ] 一定是 ( ，否则 n u m 1 [ 0 ] 为 − 1 { 将其拆分 s [ 0 , j ] 和 s ( j , i ] 仍然符合性质 存在 j ≠ i 且 n u m 1 [ j ] = = 0 删除最左的 ( ，最右的 ) ，变成 n u m s [ 1 , i ) o t h e r num1[i]是合法括号 \rightarrow i一定不为0 因为num1[0]只能是1或-1\\ num1[i-1] >=0 ,所以s[i]只能是)，否则num1[i] >= 0+1 \\ s[0]一定是(，否则num1[0] 为-1 \\ \begin{cases} 将其拆分s[0,j] 和s(j,i] 仍然符合性质 & 存在j\neq i 且 num1[j]==0 \\ 删除最左的(，最右的)，变成nums[1,i) & other \\ \end{cases} num1[i]是合法括号→i一定不为0因为num1[0]只能是1或−1num1[i−1]>=0,所以s[i]只能是)，否则num1[i]>=0+1s[0]一定是(，否则num1[0]为−1{将其拆分s[0,j]和s(j,i]仍然符合性质删除最左的(，最右的)，变成nums[1,i)​存在j=i且num1[j]==0other​
num1[j]不为0且大于等于0 → \rightarrow → num1[j]大于等于1
移除（后，nums1[j]全部-- 任然符合性质一
s[i]合法 → \rightarrow → num1[i]==0 → \rightarrow → num1[i-1]为1
移除(后，变成0，符合性质二。
不断拆分，知道s的长度为2为止。

广度优先

初始字符为空。
hasAdd 记录增加了多少字符。
num 记录字符的权值和，(为1，)为-1。
{ p r e 各字符串，尝试删除 ) n u m < 0 增加字符 h a s A d d < s . l e n g t h 结束 n u m = 0 删除 ( o t h e r \begin{cases} pre各字符串，尝试删除) & num < 0 \\ 增加字符 & hasAdd < s.length \\ 结束 & num = 0 \\ 删除( & other \end{cases} ⎩ ⎨ ⎧​pre各字符串，尝试删除)增加字符结束删除(​num<0hasAdd<s.lengthnum=0other​
删除）时，无需判断，因为只会让其它)的num变大或不变。
删除)时，需要判断，因为可能让某个)的num变成负数。

代码

核心代码

class Solution {
public:
	vector<string> removeInvalidParentheses(string s) {
		int num = 0;
		unordered_set<string> pre = { "" };
		int iDelLeft=0,iDelRight = 0;
		for (int i = 0; ; i++)
		{
			unordered_set<string> dp;
			const int hasAdd = i - iDelLeft -iDelRight;
			if (num < 0)
			{//删除一个右括号
				iDelRight++;
				num++;
				for (const string& str : pre)
				{
					for (int j = 0; j < str.length(); j++)
					{
						if (')' == str[j])
						{
							dp.emplace(str.substr(0, j) + str.substr(j + 1));
						}
					}
				}
			}
			else if (hasAdd < s.length())
			{
				if ('(' == s[hasAdd])
				{
					num++;
				}
				else if (')' == s[hasAdd])
				{
					num--;
				}
				for (const string& str : pre)
				{
					dp.emplace(str + s[hasAdd]);
				}
			}
			else 
			{
				if (num > 0)
				{//删除一个左括号
					num--;
					iDelLeft++;
					for (const string& str : pre)
					{
						for (int j = 0; j < str.length(); j++)
						{
							if ('(' == str[j])
							{
								dp.emplace(str.substr(0, j) + str.substr(j + 1));
							}
						}
					}
				}
				else
				{
					break;
				}
			}
			dp.swap(pre);
		}
		vector<string> vRet;
		for (const string& str : pre)
		{
			if (IsVilid(str))
			{
				vRet.emplace_back(str);
			}
		}
		return vRet;
	}
	bool IsVilid(const string& str)
	{
		int num = 0;
		for (const auto& ch : str)
		{
			if ('(' == ch)
			{
				num++;
			}
			else if (')' == ch)
			{
				num--;
			}
			if (num < 0)
			{
				return false;
			}
		}
		return 0 == num;
	}
};

测试用例


template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	string s;
	{
		Solution sln;
		s = ")()(";
		auto res = sln.removeInvalidParentheses(s);
		Assert({ "()" }, res);
	}
	{
		Solution sln;
		s = ")(";
		auto res = sln.removeInvalidParentheses(s);
		Assert({ "" }, res);
	}
	{
		Solution sln;
		s = "()())()";
		auto res = sln.removeInvalidParentheses(s);
		Assert({ "(())()", "()()()" }, res);
	}
	
	{
		Solution sln;
		s = "(a)())()";
		auto res = sln.removeInvalidParentheses(s);
		Assert({ "(a())()","(a)()()" }, res);
	}

	
}

简洁版

class CBracket
{
public:
	static int ToInt(const char& ch)
	{
		if ('(' == ch)
		{
			return 1;
		}
		return (')' == ch) ? -1 : 0;
	}
	static bool IsVilid(const string& str)
	{
		int num = 0;
		for (const auto& ch : str)
		{
			num += ToInt(ch);
			if (num < 0)
			{
				return false;
			}
		}
		return 0 == num;
	}
};
class Solution {
public:	
	vector<string> removeInvalidParentheses(string s) {
		int num = 0;
		unordered_set<string> pre = { "" };
		int iHasAdd = 0;
		while(true)
		{
			unordered_set<string> dp;	
			auto Del = [&pre,&dp](char ch)
			{
				for (const string& str : pre)
				{
					for (int j = 0; j < str.length(); j++)
					{
						if (ch == str[j])
						{
							dp.emplace(str.substr(0, j) + str.substr(j + 1));
						}
					}
				}
			};
			if (num < 0)
			{//删除一个右括号
				num++;
				Del(')');
			}
			else if (iHasAdd < s.length())
			{
				num += CBracket::ToInt(s[iHasAdd]);
				for (const string& str : pre)
				{
					dp.emplace(str + s[iHasAdd]);
				}
				iHasAdd++;
			}
			else 
			{
				if (num > 0)
				{//删除一个左括号
					num--;	
					Del('(');
				}
				else
				{
					break;
				}
			}
			dp.swap(pre);
		}
		vector<string> vRet;
		for (const string& str : pre)
		{
			if (CBracket::IsVilid(str))
			{
				vRet.emplace_back(str);
			}
		}
		return vRet;
	}
	
};

2023年4月版

class Solution {
public:
vector removeInvalidParentheses(string s) {
int iNeedDelLeft = 0, iNeedDelRight = 0;
{
for (int i = 0; i < s.length(); i++)
{
const char& ch = s[i];
if ((‘(’ == ch) || (‘)’ == ch))
{
vRangeIndexs.emplace_back(i);
}
if (‘(’ == ch)
{
iNeedDelLeft++;
}
if (‘)’ == ch)
{
if (iNeedDelLeft > 0)
{
iNeedDelLeft–;
}
else
{
iNeedDelRight++;
}
}
}
}
m_iMaskNum = 1 << vRangeIndexs.size();
auto Is = [&](const int iMask)
{
int iNum = 0;
for (int j = 0; j < vRangeIndexs.size(); j++)
{
if (iMask & (1 << j))
{//此位置删除
continue;
}
const char& ch = s[vRangeIndexs[j]];
if (‘(’ == ch)
{
iNum++;
}
if (‘)’ == ch)
{
iNum–;
}
if (iNum < 0)
{
return false;
}
}
return 0 == iNum;
};
std::unordered_set setRet;
for (int iMask = 0; iMask < m_iMaskNum; iMask++)
{
if (bitcount(iMask) != (iNeedDelLeft + iNeedDelRight))
{
continue;
}
if (!Is(iMask))
{
continue;
}
std::vector indexs,subIndexs;
for (int i = 0; i < s.length(); i++)
{
indexs.emplace_back(i);
}
for (int j = 0; j < vRangeIndexs.size(); j++)
{
if (iMask & (1 << j))
{//此位置删除
subIndexs.emplace_back(vRangeIndexs[j]);
}
}
vector v;
string str;
std::set_difference(indexs.begin(), indexs.end(), subIndexs.begin(), subIndexs.end(), std::back_inserter(v));
for (const auto& tmp : v)
{
str += s[tmp];
}
setRet.emplace(str);
}
return vector(setRet.begin(), setRet.end());
}
int m_iMaskNum;
vector vRangeIndexs;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/432191.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux Watchdog 机制是什么

Linux Watchdog 机制是什么

当涉及到Linux操作系统的稳定性和可靠性时&#xff0c;Linux Watchdog机制是一个至关重要的议题。该机制旨在监控系统状态&#xff0c;确保在出现问题时采取适当的措施以维持系统的正常运行。本文将深入探讨Linux Watchdog机制的工作原理、应用范围以及如何配置和使用该机制来提…
阅读更多...
2023年全国职业院校技能大赛 GZ073网络系统管理赛项 模块A：网络构建

2023年全国职业院校技能大赛 GZ073网络系统管理赛项 模块A：网络构建

2023年全国职业院校技能大赛 GZ073网络系统管理赛项 模块A：网络构建 卷II 一. 拓扑图 二.有线网络配置 三.无线网络配置 四.出口网络配置 二、有线配置 S1.txt S1#show running-config Building configuration... Current configuration : 5008 bytes! version RGOS 10…
阅读更多...
html标签之表格标签，想学web开发

html标签之表格标签，想学web开发

html 1&#xff0c;浏览器存储的方式有哪些 2&#xff0c;如何解决跨域的&#xff1f; 3&#xff0c;浏览器 cookie 和 session 的认识。 4&#xff0c;输入URL发生什么&#xff1f; 5&#xff0c;浏览器渲染的步骤 6&#xff0c;页面渲染优化 7&#xff0c;强制缓存和协商缓存…
阅读更多...
蓝桥杯刷题（一）

蓝桥杯刷题（一）

一、 import os import sys def dps(s):dp [0] * len(s)dp[0] ord(s[0]) - 96if len(s) 1:return dp[-1]dp[1] max(ord(s[0]) - 96, ord(s[1]) - 96)for i in range(2, len(s)):dp[i] max(dp[i - 1], dp[i - 2] (ord(s[i])) - 96)return dp[-1] s input() print(dps(s))…
阅读更多...
App前端开发跨平台框架比较：React Native、Flutter、Xamarin等

App前端开发跨平台框架比较：React Native、Flutter、Xamarin等

引言 移动应用开发领域的跨平台框架正在不断演进&#xff0c;为开发者提供更多选择。在本文中&#xff0c;我们将比较几个流行的跨平台框架&#xff1a;React Native、Flutter和Xamarin等。讨论它们的优缺点、适用场景以及开发体验。 第一部分 React Native: 优缺点、适用场景…
阅读更多...
gRPC-第二代rpc服务

gRPC-第二代rpc服务

在如今云原生技术的大环境下&#xff0c;rpc服务作为最重要的互联网技术&#xff0c;蓬勃发展&#xff0c;诞生了许多知名基于rpc协议的框架&#xff0c;其中就有本文的主角gRPC技术。 一款高性能、开源的通用rpc框架 作者作为一名在JD实习的Cpper&#xff0c;经过一段时间的学…
阅读更多...
【Python】深度学习基础知识——梯度下降详解和示例

【Python】深度学习基础知识——梯度下降详解和示例

尽管梯度下降&#xff08;gradient descent&#xff09;很少直接用于深度学习&#xff0c;但它是随机梯度下降算法的基础&#xff0c;也是很多问题的来源&#xff0c;如由于学习率过大&#xff0c;优化问题可能会发散&#xff0c;这种现象早已在梯度下降中出现。本文通过原理和…
阅读更多...
【控制台警告】npm WARN EBADENGINE Unsupported engine

【控制台警告】npm WARN EBADENGINE Unsupported engine

今天用webpack下载几个loader依赖&#xff0c;爆出了三个警告&#xff0c;大概的意思就是本地安装的node和npm的版本不是很匹配&#xff1f; 我的解决思路是&#xff1a; 先检查node和npm版本 然后去官网查找版本的对应 靠&#xff0c;官网404 Node.js (nodejs.org) 就找到…
阅读更多...
第十二篇：学习python数据清洗

第十二篇：学习python数据清洗

文章目录 一、啥是数据清洗二、将表格数据导入pandas中1. 准备工作2. 引入csv文件2.1 引入pandas库2.2 读取文件/修改名称3.2 快速浏览数据2.4 修改名字2.5 查找缺失值2.6 删除缺失值 3. 引入Excel文件3.1 引入pandas库3.2 读取Excel文件的人均GDP数据3.3 查看数据类型和non-nu…
阅读更多...
【鸿蒙 HarmonyOS 4.0】弹性布局（Flex）

【鸿蒙 HarmonyOS 4.0】弹性布局（Flex）

一、介绍 弹性布局&#xff08;Flex&#xff09;提供更加有效的方式对容器中的子元素进行排列、对齐和分配剩余空间。容器默认存在主轴与交叉轴&#xff0c;子元素默认沿主轴排列&#xff0c;子元素在主轴方向的尺寸称为主轴尺寸&#xff0c;在交叉轴方向的尺寸称为交叉轴尺寸…
阅读更多...
六、软考-系统架构设计师笔记-软件工程基础知识

六、软考-系统架构设计师笔记-软件工程基础知识

1、软件工程 软件工程是将系统化的、严格约束的、可量化的方法应用于软件的开发、运行和维护&#xff0c;即将工程化应用于软件并对上述方法的研究。 软件要经历从需求分析、软件设计、软件开发、运行维护&#xff0c;直至被淘汰这样的全过程&#xff0c;这个过程称为软件的生…
阅读更多...
什么是聚簇索引与非聚集索引和区别?

什么是聚簇索引与非聚集索引和区别?

什么是聚簇索引与非聚集索引和区别? 按物理存储分类:InnoDB的存储方式是聚集索引&#xff0c;MVISAM的存储方式是非聚集索引 test innodb.frm 测试 innodb.ibd Frame表结构 数据表索引数据 test myisam.frm ---->Frame表结构test myisam.MYD_---数据表数据test_myisam.MYl-…
阅读更多...
HTML实体字符列表，必看

HTML实体字符列表，必看

HTML、CSS、JS三大部分都起什么作用&#xff1f; HTML内容层&#xff0c;它的作用是表示一个HTML标签在页面里是个什么角色&#xff1b;CSS样式层&#xff0c;它的作用是表示一块内容以什么样的样式&#xff08;字体、大小、颜色、宽高等&#xff09;显示&#xff1b;JS行为层…
阅读更多...
【论文笔记】Language Models are Unsupervised Multitask Learners

【论文笔记】Language Models are Unsupervised Multitask Learners

Language Models are Unsupervised Multitask Learners 回顾一下第一代 GPT-1 &#xff1a; 设计思路是 “海量无标记文本进行无监督预训练少量有标签文本有监督微调” 范式&#xff1b;模型架构是基于 Transformer 的叠加解码器&#xff08;掩码自注意力机制、残差、Layernorm…
阅读更多...
【Unity】ABB CRB 15000 外部引导运动

【Unity】ABB CRB 15000 外部引导运动

一、RobotStudio控制器的文件系统和配置参数 HOME&#xff1a;控制器文件系统的根目录或起始点。配置&#xff1a;机器人控制器的配置设置和参数。外件信息&#xff1a;连接到机器人的外部组件的信息。I/O 系统&#xff1a;输入/输出系统&#xff0c;管理机器人和外部设备之间的…
阅读更多...
.[[backup@waifu.club]].wis最近多发，数据库被加密了能恢复吗？

.[[backup@waifu.club]].wis最近多发，数据库被加密了能恢复吗？

Wis勒索病毒是怎样加密文件的&#xff1f; WIS勒索病毒加密文件的过程主要依赖于强大的加密算法&#xff0c;通常是RSA或AES等对称或非对称加密算法。这些算法可以非常快速地将用户的文件加密&#xff0c;使得文件在没有正确密钥的情况下无法被正常读取或打开。技术服务号&…
阅读更多...
C#与欧姆龙PLC实现CIP通讯

C#与欧姆龙PLC实现CIP通讯

参考文档&#xff1a; 欧姆龙PLC使用-CSDN博客 CIP通讯介绍&#xff08;欧姆龙PLC&#xff09;-CSDN博客 使用NuGet添加引用&#xff1a;CIPCompolet 基础参考我的CIP协议介绍&#xff0c;默认TCP端口为&#xff1a;44818 类NXCompolet 类的功能可以在安装PLC开发软件后帮…
阅读更多...
Mol2文件处理-拆分、合并、提取名称、计数与格式转换

Mol2文件处理-拆分、合并、提取名称、计数与格式转换

欢迎浏览我的CSND博客&#xff01; Blockbuater_drug …点击进入 文章目录 前言一、Mol2文件合并二、Mol2文件拆分为含有单个分子的文件三、Mol2文件分子名称修改与提取3.1 分子名称修改去除空格3.2 文件名称提取 四、Mol2文件包含分子计数4.1 Mol2文件中分子计数4.2 分子计数传…
阅读更多...
Pytorch学习 day03（Tensorboard、Transforms）

Pytorch学习 day03（Tensorboard、Transforms）

Tensorboard Tensorboard能够可视化loss的变化过程&#xff0c;便于我们查看模型的训练状态&#xff0c;也能查看模型当前的输入和输出结果 在Pycharm中&#xff0c;可以通过按住ctrl&#xff0c;并左键点击某个库来进入源文件查看该库的使用方法SummaryWriter是用来向log_dir…
阅读更多...
工具函数模板题（蓝桥杯 C++ 代码 注解）

工具函数模板题（蓝桥杯 C++ 代码 注解）

目录 一、Vector容器&#xff1a; 二、Queue队列 三、Map映射 四、题目&#xff08;快递分拣 vector&#xff09;&#xff1a; 代码&#xff1a; 五、题目&#xff08;CLZ银行问题 queue&#xff09;&#xff1a; 代码&#xff1a; 六、题目&#xff08;费里的语言 map&…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站