当前位置: 首页> 科技> 能源 > 微信在线客服系统网页_莱芜网络推广公司哪里有_搜索引擎关键词优化技巧_深圳网络营销运营

微信在线客服系统网页_莱芜网络推广公司哪里有_搜索引擎关键词优化技巧_深圳网络营销运营

时间:2025/7/29 21:55:34来源:https://blog.csdn.net/sjsjs11/article/details/143515782 浏览次数:0次
微信在线客服系统网页_莱芜网络推广公司哪里有_搜索引擎关键词优化技巧_深圳网络营销运营

给你一个字符串 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
解释:这个字符串已经是平衡字符串。

数学归纳法

class Solution {
public:int minSwaps(string s) {int cnt = 0;for(char c : s){if(c == ']'){if(cnt > 0){cnt--;}}else{cnt++;}}return cnt % 2 + cnt/2;}
};

时间复杂度:O(n)
空间复杂度:O(1)

这题的关键在于能够总结出规律,才能写出最优解。
把匹配的全都消了,剩下的必然是 k 个 ] 加 k 个 [,k 为偶数时,交换 k/2 次就能组成 k/2 个 [],k 为奇数时,把左右两端交换后剩下 k-1 个 ] 加 k-1 个 [,再按照偶数来算,最后交换 1 + (k-1)/ 2 次组成 [[][]…[][]]。

关键字:微信在线客服系统网页_莱芜网络推广公司哪里有_搜索引擎关键词优化技巧_深圳网络营销运营

版权声明:

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

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

责任编辑: