建站
咨詢
售后
建站咨詢
新聞中心
本文轉(zhuǎn)載自微信公眾號「程序員小熊」，作者Dine 。轉(zhuǎn)載本文請聯(lián)系程序員小熊公眾號。
讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項目有：申請域名、網(wǎng)站空間、營銷軟件、網(wǎng)站建設(shè)、沂水網(wǎng)站維護、網(wǎng)站推廣。
前言
大家好，我是來自于華為的程序員小熊。今天給大家?guī)硪坏雷址嚓P(guān)的題目，這道題也是今天的力扣每日一題，同時也是華為、蘋果、谷歌和雅虎等大廠的面試題，即力扣上的第1221題-分割平衡字符串。
本文主要介紹貪心+棧的策略來解答此題，供大家參考，希望對大家有所幫助。
分割平衡字符串
在一個平衡字符串中，'L' 和 'R' 字符的數(shù)量是相同的。
給你一個平衡字符串 s，請你將它分割成盡可能多的平衡字符串。
注意：分割得到的每個字符串都必須是平衡字符串。
返回可以通過分割得到的平衡字符串的最大數(shù)量 。
示例
示例及提示
解題思路
要求分割得到平衡字符串的最大數(shù)量，很容易想到暴力法，只要遍歷一遍字符串，統(tǒng)計字符 'L' 和 'R' 的數(shù)量，即可計算出題目要求的結(jié)果。
方法一：暴力法
遍歷字符串，統(tǒng)計 'L' 和 'R' 的數(shù)量，當(dāng)其數(shù)量相同時，則表明可以當(dāng)前遍歷到的字符可跟之前的遍歷的那些字符構(gòu)成平衡字符串，此時統(tǒng)計平衡字符串的個數(shù)，并將 'L' 和 'R' 的數(shù)量全部置 0，然后繼續(xù)遍歷并統(tǒng)計平衡字符串的個數(shù)，直至遍歷完整個字符串即可。
Show me the Code
「C」
- int balancedStringSplit(char * s) {
- int numR = 0, numL = 0, res = 0;
- for (int i = 0; s[i] != '\0'; ++i) {
- if (s[i] == 'L') {
- numL++;
- } else {
- numR++;
- }
- if (numL == numR) {
- res++;
- numL = 0;
- numR = 0;
- }
- }
- return res;
- }
復(fù)雜度分析
時間復(fù)雜度：O(n)，其中 n 為字符串的長度，需要遍歷一遍字符串。
空間復(fù)雜度：O(1)，未開辟額外的存儲空間。
方法二：貪心 + 棧
本題也可以采用貪心的思想，遍歷字符串時，遇到一個個平衡字符串時，將其分割出來，再繼續(xù)遍歷剩余的子字符串。
同時可以采用棧的思想，在遍歷字符串時，如果遇到字符 'R' 時，讓其入棧，棧內(nèi)的字符個數(shù)加一;遇到字符 'L' 時，讓字符 'R' 出棧，棧內(nèi)的字符個數(shù)減一。
遍歷的同時判斷棧中的字符個數(shù)是否為 0，若為 0，則代表已遍歷的字符已構(gòu)成平衡字符串，統(tǒng)計平衡字符串的個數(shù)，直至遍歷結(jié)束。
舉例
以字符串 s = "RLLLRRLR" 為例。
例子
在遍歷到 s 的某一字符時，用兩個變量 cnt 和 res 分別記錄字符 'R' 和 'L' 之差以及平衡字符串的數(shù)量;
設(shè)置兩個變量，邊遍歷邊統(tǒng)計平衡字符串個數(shù)
計算 cnt 和 res 的大小;
遍歷到 'R' 時，cnt 加 1
遍歷到 'L'時，cnt 減 1 并計算 res
完整的計算過程，如下動圖示：
計算平衡字符串的完整過程動圖
Show me the Code
「C」
- int balancedStringSplit(char * s) {
- int cnt = 0, res = 0;
- for (int i = 0; s[i] != '\0'; ++i) {
- cnt += s[i] == 'R' ? 1 : -1;
- if (cnt == 0) {
- res++;
- }
- }
- return res;
- }
「C++」
- int balancedStringSplit(string s) {
- int res = 0, cnt = 0;
- for (auto a : s) {
- cnt += a == 'R' ? 1 : -1;
- if (cnt == 0) {
- res += 1;
- }
- }
- return res;
- }
「Java」
- int balancedStringSplit(String s) {
- int res = 0, cnt = 0;
- for (int i = 0; i < s.length(); i++) {
- cnt += s.charAt(i) == 'R' ? 1 : -1;
- if (cnt == 0) {
- res += 1;
- }
- }
- return res;
- }
「Python3」
- def balancedStringSplit(self, s: str) -> int:
- res, cnt = 0, 0
- for c in s:
- cnt += 1 if c == 'R' else -1
- if cnt == 0:
- res += 1
- return res
「Golang」
- func balancedStringSplit(s string) int {
- cnt, res := 0, 0
- for _, ch := range s {
- if ch == 'R' {
- cnt++
- } else {
- cnt--
- }
- if cnt == 0 {
- res++
- }
- }
- return res
- }
復(fù)雜度分析
- 時間復(fù)雜度：O(n)，其中 n 為字符串的長度，需要遍歷一遍字符串。
- 空間復(fù)雜度：O(1)，未開辟額外的存儲空間。
網(wǎng)站標題：貪心讓你分割更多平衡字符串
網(wǎng)站鏈接：http://www.dlmjj.cn/article/djpdjec.html
