1221.分割平衡字符串
1221.1 题目
平衡字符串中，’L’ 和 ‘R’ 字符的数量是相同的。
给你一个平衡字符串 s，请你将它分割成尽可能多的子字符串，并满足：
每个子字符串都是平衡字符串。
返回可以通过分割得到的平衡字符串的最大数量。
示例 1：
输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 “RL”、”RRLL”、”RL”、”RL” ，每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’ 。
示例 2：
输入：s = "RLRRRLLRLL"
输出：2
解释：s 可以分割为 “RL”、”RRRLLRLL”，每个子字符串中都包含相同数量的 ‘L’ 和 ‘R’。
注意，s 无法分割为 “RL”、”RR”、”RL”、”LR”、”LL” 因为第 2 个和第 5 个子字符串不是平衡字符串。
示例 3：
输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 “LLLLRRRR” 。
提示：
2 <= s.length <= 1000s[i] = 'L'或s[i] = 'R's是一个平衡字符串
1221.2 题解
贪心法
// 方法一：贪心法
// 用一个变量记录平衡差
static int BalancedStringSplit1(string s)
{
int count = 0; // 记录平衡字符串的数量
int balance = 0; // 记录 'L' 和 'R' 的平衡差
// 遍历输入字符串的每个字符
foreach (char c in s)
{
// 如果当前字符是 'L'，增加平衡差；否则，减少平衡差
if (c == 'L')
balance++;
else
balance--;
// 当平衡差为零时，说明找到一个平衡字符串，增加计数
if (balance == 0)
count++;
}
// 返回最终平衡字符串的数量
return count;
}
栈
// 方法二：栈
// 栈为空或发现下一元素和当前元素相同就入栈，否则出栈，栈为空就记录
static int BalancedStringSplit2(string s)
{
int count = 0; // 记录平衡字符串的数量
Stack<char> stack = new Stack<char>();
// 遍历输入字符串的每个字符
foreach (char c in s)
{
// 如果栈为空或者栈顶字符与当前字符相同，将当前字符入栈
if (stack.Count == 0 || stack.Peek() == c)
stack.Push(c);
else
stack.Pop(); // 如果栈顶字符与当前字符不同，弹出栈顶字符
// 当栈为空时，说明找到一个平衡字符串，增加计数
if (stack.Count == 0)
count++;
}
// 返回最终平衡字符串的数量
return count;
}
1221.3 代码
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
#region 题目
// 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。
// 给你一个平衡字符串 s，请你将它分割成尽可能多的子字符串，并满足：
// 每个子字符串都是平衡字符串。
// 返回可以通过分割得到的平衡字符串的 最大数量 。
// 示例 1：
// 输入：s = "RLRRLLRLRL"
// 输出：4
// 解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。
// 示例 2：
// 输入：s = "RLRRRLLRLL"
// 输出：2
// 解释：s 可以分割为 "RL"、"RRRLLRLL"，每个子字符串中都包含相同数量的 'L' 和 'R' 。
// 注意，s 无法分割为 "RL"、"RR"、"RL"、"LR"、"LL" 因为第 2 个和第 5 个子字符串不是平衡字符串。
// 示例 3：
// 输入：s = "LLLLRRRR"
// 输出：1
// 解释：s 只能保持原样 "LLLLRRRR" 。
#endregion
#region 测试
// 示例 1
string str1 = "RLRRLLRLRL";
int result1 = BalancedStringSplit1(str1);
Console.WriteLine($"示例1 方法1 输出：{result1}");
int result1_2 = BalancedStringSplit2(str1);
Console.WriteLine($"示例1 方法2 输出：{result1_2}");
// 示例 2
string str2 = "RLRRRLLRLL";
int result2 = BalancedStringSplit1(str2);
Console.WriteLine($"示例2 方法1 输出：{result2}");
int result2_2 = BalancedStringSplit2(str2);
Console.WriteLine($"示例2 方法2 输出：{result2_2}");
// 示例 3
string str3 = "LLLLRRRR";
int result3 = BalancedStringSplit1(str3);
Console.WriteLine($"示例3 方法1 输出：{result3}");
int result3_2 = BalancedStringSplit2(str3);
Console.WriteLine($"示例3 方法2 输出：{result3_2}");
#endregion
}
#region 答案
// 方法一：贪心法
// 用一个变量记录平衡差
static int BalancedStringSplit1(string s)
{
int count = 0; // 记录平衡字符串的数量
int balance = 0; // 记录 'L' 和 'R' 的平衡差
// 遍历输入字符串的每个字符
foreach (char c in s)
{
// 如果当前字符是 'L'，增加平衡差；否则，减少平衡差
if (c == 'L')
balance++;
else
balance--;
// 当平衡差为零时，说明找到一个平衡字符串，增加计数
if (balance == 0)
count++;
}
// 返回最终平衡字符串的数量
return count;
}
// 方法二：栈
// 栈为空或发现下一元素和当前元素相同就入栈，否则出栈，栈为空就记录
static int BalancedStringSplit2(string s)
{
int count = 0; // 记录平衡字符串的数量
Stack<char> stack = new Stack<char>();
// 遍历输入字符串的每个字符
foreach (char c in s)
{
// 如果栈为空或者栈顶字符与当前字符相同，将当前字符入栈
if (stack.Count == 0 || stack.Peek() == c)
stack.Push(c);
else
stack.Pop(); // 如果栈顶字符与当前字符不同，弹出栈顶字符
// 当栈为空时，说明找到一个平衡字符串，增加计数
if (stack.Count == 0)
count++;
}
// 返回最终平衡字符串的数量
return count;
}
#endregion
}
1221.4 运行结果
示例1 方法1 输出：4
示例1 方法2 输出：4
示例2 方法1 输出：2
示例2 方法2 输出：2
示例3 方法1 输出：1
示例3 方法2 输出：1
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
