贪心算法:1221. 分割平衡字符串(简单)

在一个 平衡字符串 中,'L' 和 'R' 字符的数量是相同的。给你一个平衡字符串 s,请你将它分割成尽可能多的平衡字符串。

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

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

示例 :

        输入:s = "RLRRRLLRLL"

        输出:2

        解释:s 可以分割为 "RL"、"RRRLLRLL" ,每个子字符串中都包含相同数量的 'L' 和 'R' 。

解题思路:贪心算法,i从左到右循环,定义一个平衡变量j,当index=i时得到一个R时,将平衡变量j增加1,否则将它减少1。当平衡变量j为0时,我们就把答案num加一。

public int balancedStringSplit(String s) {

        int m = s.length();

        int i = 0;

        int j = 0;

        int num = 0;

        while(i<m) {

            if(s.charAt(i) == 'R') {

                j++; //当index=i时得到一个R时,将平衡变量j增加1

            } else {

                j--; //否则将它减少1

            }

            if(j == 0) {

                num += 1; //当平衡变量j为0时,我们就把答案num加一

            }

            i++;

        }

        return num;

    }

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 夜莺2517阅读 127,782评论 1 9
  • 版本:ios 1.2.1 亮点: 1.app角标可以实时更新天气温度或选择空气质量,建议处女座就不要选了,不然老想...
    我就是沉沉阅读 11,828评论 1 6
  • 我是黑夜里大雨纷飞的人啊 1 “又到一年六月,有人笑有人哭,有人欢乐有人忧愁,有人惊喜有人失落,有的觉得收获满满有...
    陌忘宇阅读 12,717评论 28 53
  • 兔子虽然是枚小硕 但学校的硕士四人寝不够 就被分到了博士楼里 两人一间 在学校的最西边 靠山 兔子的室友身体不好 ...
    待业的兔子阅读 7,486评论 2 9