Leetcode刷题100天—1221. 分割平衡字符串( 双指针或贪心)—day31

向右看齐 2022-09-12 13:48 162阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

### 代码一:双指针 ###

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56We55qE5a2p5a2Q6YO95Zyo5q2M5ZSx_size_16_color_FFFFFF_t_70_g_se_x_16]

### 代码二:贪心算法 ###

![image-20210907111529064][]

#### [1221. 分割平衡字符串][1221.] ####

难度简单126收藏分享切换为英文接收动态反馈

在一个 **平衡字符串** 中，`'L'` 和 `'R'` 字符的数量是相同的。

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

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

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

**示例 1：**

输入：s = "RLRRLLRLRL"
    输出：4
    解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

**示例 2：**

输入：s = "RLLLLRRRLR"
    输出：3
    解释：s 可以分割为 "RL"、"LLLRRR"、"LR" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

**示例 3：**

输入：s = "LLLLRRRR"
    输出：1
    解释：s 只能保持原样 "LLLLRRRR".

**示例 4：**

输入：s = "RLRRRLLRLL"
    输出：2
    解释：s 可以分割为 "RL"、"RRRLLRLL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

**提示：**

*  `1 <= s.length <= 1000`
 *  `s[i] = 'L' 或 'R'`
 *  `s` 是一个 **平衡** 字符串

package 字符串;
    
    /* * https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/ */
    public class _1221_分割平衡字符串 { 
    // 解法1双指针
        public int balancedStringSplit(String s) { 
    // 由于他给的字符串是平衡字符串，所以我们可以通过双指针直接判断
        	int ans=0;
    // 定义双指针
        	int left=0,right=1;
        	
        	int sum=0;
    // 由于最后面会出现RL情况，所以right要等于s.leng
        	while(right<=s.length()) { 
    // 如果sum等于-1,说明有前面一个平衡字符
        		if (sum==-1) { 
    				ans++;
    				left=right;
    				sum=0;
    // 如果两个数等于，那么right就加加
    			}else if(s.charAt(left)==s.charAt(right)){ 
    				sum++;
    			}else { //否则sum减减
    				sum--;
    			}
        		right++;
        	}
        	return ans;
        }
        
        
    // 解法2贪心
        public int balancedStringSplit2(String s) { 
    // 由于自由R和L两个字符,设定一个变量，如果是R就++，是L就--,如果是零就增加一个平衡字符
        	int ans=0,L=0;
    // for循环遍历字符
        	for(int i=0;i<s.length();i++) { 
        		char c=s.charAt(i);
        		if (c=='L') { 
    				L++;
    			}else { 
    				L--;
    			}
        		if (L==0) { 
    				ans++;
    			}
        	}
        	return ans;
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA56We55qE5a2p5a2Q6YO95Zyo5q2M5ZSx_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/1d3181ff005a40ad8785f688b61f107e.png
[image-20210907111529064]: /images/20220828/0a024926ab7749a9b483c1b67dd3a4b0.png
[1221.]: https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/