贪心

贪心算法

贪心算法是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解

leetcode 1221. 分割平衡字符串

在一个 平衡字符串 中,’L’ 和 ‘R’ 字符的数量是相同的。

给你一个平衡字符串 s,请你将它分割成尽可能多的平衡字符串。

注意:分割得到的每个字符串都必须是平衡字符串。

返回可以通过分割得到的平衡字符串的 最大数量

来源:力扣(LeetCode)

示例

输入:s = “RLRRLLRLRL”

输出:4

解释:s 可以分割为 “RL”、”RRLL”、”RL”、”RL” ,每个子字符串中都包含相同数量的 ‘L’ 和

解法

根据题意,对于一个平衡字符串 ss,若 ss 能从中间某处分割成左右两个子串,若其中一个是平衡字符串,则另一个的 L 和 R 字符的数量必然是相同的,所以也一定是平衡字符串。

为了最大化分割数量,我们可以不断循环,每次从 ss 中分割出一个最短的平衡前缀,由于剩余部分也是平衡字符串,我们可以将其当作 ss 继续分割,直至 ss 为空时,结束循环。

代码实现中,可以在遍历 ss 时用一个字典记录 维护 L 和 R 字符的数量,当 数量相等时就说明找到了一个平衡字符串,将答案加一。

python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def balancedStringSplit(self, s):
"""
:type s: str
:rtype: int
"""
cnt = 0
num = {"R": 0, "L": 0}
subs = ""
for c in s:
num[c] += 1
subs += c
if num["R"] == num["L"]:
cnt += 1
subs = ""
return cnt