贪心
贪心算法
贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解
leetcode 1221. 分割平衡字符串
在一个 平衡字符串 中,’L’ 和 ‘R’ 字符的数量是相同的。
给你一个平衡字符串 s,请你将它分割成尽可能多的平衡字符串。
注意:分割得到的每个字符串都必须是平衡字符串。
返回可以通过分割得到的平衡字符串的 最大数量 。
示例
输入:s = “RLRRLLRLRL”
输出:4
解释:s 可以分割为 “RL”、”RRLL”、”RL”、”RL” ,每个子字符串中都包含相同数量的 ‘L’ 和
解法
根据题意,对于一个平衡字符串 ss,若 ss 能从中间某处分割成左右两个子串,若其中一个是平衡字符串,则另一个的 L 和 R 字符的数量必然是相同的,所以也一定是平衡字符串。
为了最大化分割数量,我们可以不断循环,每次从 ss 中分割出一个最短的平衡前缀,由于剩余部分也是平衡字符串,我们可以将其当作 ss 继续分割,直至 ss 为空时,结束循环。
代码实现中,可以在遍历 ss 时用一个字典记录 维护 L 和 R 字符的数量,当 数量相等时就说明找到了一个平衡字符串,将答案加一。
python代码
1 | class Solution(object): |