当前位置: 首页> 科技> 数码 > 武汉自助建站模板_app制作公司排行榜_佛山网站营销推广_无锡seo关键词排名

武汉自助建站模板_app制作公司排行榜_佛山网站营销推广_无锡seo关键词排名

时间:2025/7/11 8:04:30来源:https://blog.csdn.net/he_zhidan/article/details/142413315 浏览次数:0次
武汉自助建站模板_app制作公司排行榜_佛山网站营销推广_无锡seo关键词排名

本文涉及知识点

C++栈

LeetCode1963. 使字符串平衡的最小交换次数

给你一个字符串 s ,下标从 0 开始 ,且长度为偶数 n 。字符串 恰好 由 n / 2 个开括号 ‘[’ 和 n / 2 个闭括号 ‘]’ 组成。
只有能满足下述所有条件的字符串才能称为 平衡字符串 :
字符串是一个空字符串,或者
字符串可以记作 AB ,其中 A 和 B 都是 平衡字符串 ,或者
字符串可以写成 [C] ,其中 C 是一个 平衡字符串 。
你可以交换 任意 两个下标所对应的括号 任意 次数。
返回使 s 变成 平衡字符串 所需要的 最小 交换次数。
示例 1:
输入:s = “][][”
输出:1
解释:交换下标 0 和下标 3 对应的括号,可以使字符串变成平衡字符串。
最终字符串变成 “[[]]” 。
示例 2:
输入:s = “]]][[[”
输出:2
解释:执行下述操作可以使字符串变成平衡字符串:

  • 交换下标 0 和下标 4 对应的括号,s = “[]][][” 。
  • 交换下标 1 和下标 5 对应的括号,s = “[[][]]” 。
    最终字符串变成 “[[][]]” 。
    示例 3:
    输入:s = “[]”
    输出:0
    解释:这个字符串已经是平衡字符串。
    提示:
    n == s.length
    2 <= n <= 106
    n 为偶数
    s[i] 为’[’ 或 ‘]’
    开括号 ‘[’ 的数目为 n / 2 ,闭括号 ‘]’ 的数目也是 n / 2

C++栈

左括号权值1,右括号-1。
p[i] = s[0…i]的权值和。
合法括号 ⟺ \iff
条件一, ∀ \forall i,p[i]>=0。
条件二,p.back()等于0。本题左右括号相等,故一定成立。
i从小到大处理p[i],如果p[i] < 0,则说明s[i]是右括号,和s[i…]的左括号交换,和s[0…i-1]交换不影响p[i]。
i < x1 < x2 ,s[x1]、s[x2]都是[。和x2交换相比和x1交换,p[x1…x2-1]大1,这显然有利于条件一。故选择x2。
用栈记录]的下标,如果需要交换,和栈顶的下标交换,并出栈。

代码

核心代码

class Solution {public:int minSwaps(string s) {stack<int> indexs;for (int i = 0; i < s.length(); i++) {if ('[' == s[i]) {indexs.emplace(i);}}int cur = 0;int ret = 0;for (int i = 0; i < s.length(); i++) {if ('[' == s[i]) {cur++;}else {if (0 == cur) {swap(s[i], s[indexs.top()]);indexs.pop();cur = 1;ret++;}else {cur--;}}}return ret;}};

单元测试

	string s;TEST_METHOD(TestMethod11){s = "][][";auto res = Solution().minSwaps(s);AssertEx(1, res);}TEST_METHOD(TestMethod12){s = "]]][[[";auto res = Solution().minSwaps(s);AssertEx(2, res);}TEST_METHOD(TestMethod13){s = "[]";auto res = Solution().minSwaps(s);AssertEx(0, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

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

关键字:武汉自助建站模板_app制作公司排行榜_佛山网站营销推广_无锡seo关键词排名

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: