首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

贪心算法:括号的平衡配对问题

本课继续讲解贪心算法相关的习题:括号的平衡配对问题。

在编写计算机程序的时候,新手常犯的一个错误就是括号的配对问题,比如,在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;

}

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190216G087P300?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券