编辑:我试图解决 spoj 问题。这是问题的链接: http://spoj.pl/problems/BRCKTS
我可以想到两种可能的数据结构来解决问题，一种使用线段树，另一种使用 BIT。 我已经使用线段树实现了该解决方案。我读过有关 BIT 的内容，但我不知道如何用它做某件事(我在下面提到过)
我正在尝试检查仅包含 ('s 或 ) 的给定字符串中的括号是否平衡。
我正在使用 BIT(二进制索引树)来解决这个问题。
我遵循的程序如下:
我正在获取一个大小等于字符串中字符数的数组。
我将 ) 指定为 -1，将 ( 指定为 1。
仅当满足以下两个条件时，字符串中的括号才会平衡。
- 整个数组的累加和为零。
- 最小累积和为非负数。 即数组中所有前缀的累加和的最小值为非负数。
使用 BIT 检查条件 1 很简单。 我在检查条件 2 时遇到问题。
最佳答案
这是关于二元索引树的非常好的教程:http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees这是更直接但不太全面的:http://programmersdream.com/data-structure/binary-indexed-tree/
关于algorithm - 使用 BIT 进行括号匹配，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2348912/