【力扣题解】1221. 分割平衡字符串

博主目前也在学习，有错误欢迎指正
保持热爱 奔赴星海

• • 一、题目
  • • 1、题目描述
    • 2、基础框架
    • 3、原题链接
  • 二、解题报告
  • • 1、思路分析（解法一）
    • 2、代码详解（解法一）
    • 1、思路分析（解法二）
    • 2、代码详解（解法二）

在一个 平衡字符串 中，‘L’ 和 ‘R’ 字符的数量是相同的。
给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。
返回可以通过分割得到的平衡字符串的 最大数量 。

• Java版本框架代码如下：

class Solution {
    public int balancedStringSplit(String s) {
    
    }
}

1221. 分割平衡字符串

       (1)从左向右遍历字符串，如果是L，则cnt减一，否则加一。
       (2)如果cnt的值等于零，说明L和R的数量相等，说明i左边是平衡子字符串。res++。

class Solution {
    public int balancedStringSplit(String s) {
        int res = 0;
        int cnt = 0;
        char[] tmp = s.toCharArray();
        for(int i = 0;i < tmp.length;i++) {
            cnt += tmp[i] == 'L' ? -1:1;
            if(cnt == 0) {
                res++;
            }
        }
        return res;
    }
}

       (1)定义两个双指针，若在左右指针之间的区间内是平衡字符串，res++，并且移动双指针。若不是平衡字符串，则右指针右移。
       (2)判断平衡的方法（isBalanced函数）是，先排序，再判断数组的左半部分和右半部分是否各自相等，并且左右部分不相等。

class Solution {
    public int balancedStringSplit(String s) {
        int res = 0;
        int left = 0;
        int right = 1;
        while(right < s.length()) {
            if(isBalanced(s.toCharArray(),left,right)) {
                left = right + 1;
                right = left + 1;
                res++;
            }else {
                right++;
            }

        }
        return res;
    }
    public boolean isBalanced(char[] arr,int left,int right) {
        if((right - left + 1)%2 == 1) {
            return false;
        }

        if(right - left + 1 == 2) {
            if(arr[left] == arr[right]) {
                return false;
            }else  {
                return true;
            }
        }
        Arrays.sort(arr,left,right + 1);
        int n = ((right - left) + 1)/2;
        char cur = arr[left];
        for(int i = left + 1;i < left + n;i++) {
            if(cur != arr[i]) {
                return false;
            }
        }
        if(cur == arr[left + n]) {
            return false;
        }
        cur = arr[left + n];
        for(int i = left + n + 1;i <= right;i++) {
            if(cur != arr[i]) {
                return false;
            }
        }
        return true;
    }
}