贪心

Posted on

贪心算法

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

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