CTF of Z2BNS
0%

分割平衡字符串

发表于 更新于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 513 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

在一个「平衡字符串」中，’L’ 和 ‘R’ 字符的数量是相同的。

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

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

示例1：

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

示例2：

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

示例3：

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

提示：

  • 1 <= s.length <= 1000
  • s[i] = 'L' 或 'R'
  • 分割得到的每个字符串都必须是平衡字符串。
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

利用STL模板库中的栈stack容器，两个字符一个入栈一个出栈，如果栈空（非初始状态）则得到一个平衡字符串

c++代码：(执行用时0ms，击败100.00%，内存消耗6.4M，击败9.17%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int balancedStringSplit(string s) {
        stack<char> ss;
        int result=0;
        for(int i=0;i<s.length();++i){
            //一个入栈一个出栈
            //栈空或者与栈中字符相同则入栈
            if(ss.empty() || ss.top()==s[i]){
                ss.push(s[i]);
            }else{
                //与栈中字符不同则出栈
                ss.pop();
                //出栈后栈为空说明是一个平衡字符串（L和R数量相同）
                if(ss.empty()){
                    ++result;
                }
            }
        }
        return result;
    }
};
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

没有官方题解，主要是使用了容器stack的思想，挺好的，散会😪

------------- THE END! THANKS! -------------