本课继续讲解贪心算法相关的习题:括号的平衡配对问题。
在编写计算机程序的时候,新手常犯的一个错误就是括号的配对问题,比如,在C/C++语言中,{ 需要和 } 相匹配。今天我们就来看一个与括号匹配相关的问题。
假设有一个字符串,它仅由两种字符组成:左括号 [ 和 右括号 ],并且包含N个左括号 [ 和 N个右括号 ],一共2N个字符。但是我们需要让字符串中的 [ 和 ] 排列次序达成某种平衡,也就是 [ 和 ] 的排列必须符合下面的规则:
空字符串是括号平衡的;
字符串A是括号平衡的,那么左右分别添加 [ 和 ] 后得到的新字符串 [ A ] 也是括号平衡的;
字符串A和字符串B是括号平衡的,那么合并字符串 AB 是括号平衡的,合并字符串 BA 也是括号平衡的。
例如:
[] 、[[]]、[][][]、[[][]] 等等都是括号平衡字符串。
][、[]][、][][[] 等等都不是括号平衡的。
为了使非括号平衡的字符串达到括号平衡,可以通过交换相邻的 [ 和 ] 的位置,达到括号平衡。例如:
1)交换 ][ 中第一个字符和第二个字符位置,得到的新字符串 [] 是括号平衡的
2)交换 []][ 中第三个字符和第四个字符位置,得到的新字符串 [][]是括号平衡的
3)交换 ][][[]中第一个字符和第二个字符位置,再交换第三个字符和第四个字符位置,得到的新字符串 [][][]是括号平衡的
问题来了:
给出一串由N个左括号 [ 和 N个右括号 ]组成的字符串,请计算最少需要进行多少次相邻符号的交换才能使它达到括号平衡?
【例题1】
输入 : []][][
输出 : 需要2次交换
第一次交换: 位置3和位置4,得到[][]][
第二次交换: 位置5和位置6,得到[][][]
【例题2】
输入: [[][]]
输出 : 需要0次交换
因为该输入字符串本来已经是括号平衡了.
在继续讲解算法之前,请你自己先思索一下如何解决上述问题。
思路分析
如果我们仔细观察一下括号平衡的字符串,会发现下列事实:
如果前X个字符可以形成一个括号平衡字符串A,那么A对它后面的字符串是否平衡没有影响。也就是整个字符串是否平衡将由A以后的字符串决定。例如:[][[]]][中红色部分是平衡字符串,它不影响整个字符串的平衡性,而由于][不平衡,导致了整个字符串的不平衡。
平衡字符串一定是以'['开始的。
因此,我们可以使用贪心算法来解决这个问题,并且采取如下的贪心策略:
如果前X个字符形成一个平衡字符串,我们可以忽略这些字符并继续检查后面的字符。
平衡字符串一定是以'['开始的,所以如果在需要'['之前先遇到']',那么必须开始交换字符以获得平衡字符串。
算法描述
具体的算法描述如下:
变量sum保存需要交换的次数,初始化sum = 0
设置当前字符索引 i = 0, 指向第一个字符
计数器counter 设为0
通过索引 i 和依次递增 i 的 值,从左到右遍历字符串,统计左括号 [ 的数量: 遇到左括号 [,计数器counter 就加上 1,当遇到右括号 ] 时计数器就减去1
如果计数器counter 变为负数,那么就表示遇到 ] 了,就必须开始把它与它后面的第一个 [ 交换来平衡字符串,执行下列操作:
索引 i 代表我们当前所处的位置,现在我们继续前进到下一个左括号 [ 所在的位置,假设是索引 j 的位置 。把位于j 的 左括号 [ 通过依次相邻交换到位置i, 将位置i和位置j之间的所有其他字符移到右侧,共需要交换 j-i 次,所以我们必须把 j-i 的值累加到sum中。
转步骤3)
采用上述算法计算【例题1】的过程可以用下面的动图来表示。
算法的优化
上述算法的时间复杂性为 O(N^2),因为交换字符的时候,需要搜索下一个 [,这个操作需要O(N)的复杂性。
我们可以先扫描字符串并将左括号 [ 的位置存储在向量pos中,并用p表示当前处理到的左括号在向量pos中的位置。
与原来的算法类似,计数器counter计算遇到的左括号的数量:遇到左括号 [ 增加计数,注意此时将p加1,我们遇到右括号 ] 时,减少计数。
如果计数器小于0,意味着我们必须开始交换。注意此时元素pos [p] 告诉我们下一个左括号 [ 的索引位置。计算 pos [p] - i,并将差加入到sum中,其中 i 是当前位置。 我们可以交换当前索引i指向的元素和pos [p]指向的元素,并将counter重置为0。
由于我们已经将原来算法中的O(N)步骤转换为O(1)步骤了,因此总的时间复杂度降低到了O(N)。
代码实现
我们还是使用C++的STL来简化编程。具体的代码实现如下:
//字符串的括号平衡问题
#include
#include
#include
using namespace std;
// 计算需要交换的次数
long swapCount(string s)
{
// 向量pos 记录 [ 的位置
vector pos;
for (int i = 0; i
if (s[i] == '[')
pos.push_back(i);
int counter = 0; // 存放遇到的[的个数
int p = 0; // 指向下个 [在向量pos中的位置
long sum = 0; // 记录需要交换的总次数
for (int i = 0; i
{
// 遇到[将计算器加1,并让p加1,使它指向向量pos记录的下一个[的位置
if (s[i] == '[')
{
++counter;
++p;
}
else if (s[i] == ']')
--counter;
// 遇到不平衡的括号
if (counter
{
//把需要交换的次数加入到总的次数sum中
sum += pos[p] - i;
swap(s[i], s[pos[p]]);
++p;
// 重置计数器为1
counter = 1;
}
}
return sum;
}
// 主程序
int main()
{
string s = "[]][][";
cout
s = "[[][]]";
cout
return 0;
}
领取专属 10元无门槛券
私享最新 技术干货