? 1221. 分割平衡字符串
難度：簡單
平衡字符串 中，'L' 和 'R' 字符的數(shù)量是相同的。
給你一個平衡字符串 s，請你將它分割成盡可能多的子字符串，并滿足：
- 每個子字符串都是平衡字符串。
返回可以通過分割得到的平衡字符串的 最大數(shù)量 。
示例 1：
輸入：s = “RLRRLLRLRL”
輸出：4
解釋：s 可以分割為 “RL”、“RRLL”、“RL”、“RL” ，每個子字符串中都包含相同數(shù)量的 ‘L’ 和 ‘R’ 。
示例 2：
輸入：s = “RLRRRLLRLL”
輸出：2
解釋：s 可以分割為 “RL”、“RRRLLRLL”，每個子字符串中都包含相同數(shù)量的 ‘L’ 和 ‘R’ 。
注意，s 無法分割為 “RL”、“RR”、“RL”、“LR”、“LL” 因為第 2 個和第 5 個子字符串不是平衡字符串。
示例 3：
輸入：s = “LLLLRRRR”
輸出：1
解釋：s 只能保持原樣 “LLLLRRRR” 。
提示：
- 2 <= s.length <= 1000
-
s[i] = 'L'或'R' -
s是一個 平衡 字符串
??思路：貪心
任意平衡字符串內(nèi)的 R 和 L 數(shù)量相等：
- 定義
count記錄R的數(shù)量，當前字符是R就加1，否則減1； - 當
count = 0時，說明當前的R和L數(shù)量相等，數(shù)量ans++。
??代碼：(Java、C++)
Java
class Solution {
public int balancedStringSplit(String s) {
int count = 0, ans = 0;
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == 'R') count++;
else count--;
if(count == 0) ans++;
}
return ans;
}
}
C++
class Solution {
public:
int balancedStringSplit(string s) {
int count = 0, ans = 0;
for(char c : s){
if(c == 'R') count++;
else count--;
if(count == 0) ans++;
}
return ans;
}
};
?? 運行結(jié)果：
?? 復(fù)雜度分析：
-
時間復(fù)雜度：
O
(
n
)
O(n)
O(n)，其中
n為字符串s的長度，我們僅需遍歷s一次。 - 空間復(fù)雜度： O ( 1 ) O(1) O(1)，只需要常數(shù)的空間存放若干變量。
題目來源：力扣。文章來源：http://www.zghlxwxcb.cn/news/detail-514134.html
放棄一件事很容易，每天能堅持一件事一定很酷，一起每日一題吧！
關(guān)注我LeetCode主頁 / CSDN—力扣專欄，每日更新！文章來源地址http://www.zghlxwxcb.cn/news/detail-514134.html
注： 如有不足，歡迎指正！
到了這里，關(guān)于(貪心) 1221. 分割平衡字符串 ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
