[[422180]]

本文轉(zhuǎn)載自微信公眾號(hào)「程序員小熊」，作者Dine 。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序員小熊公眾號(hào)。

前言

大家好，我是來自于華為的程序員小熊。今天給大家?guī)硪坏雷址嚓P(guān)的題目，這道題也是今天的力扣每日一題，同時(shí)也是華為、蘋果、谷歌和雅虎等大廠的面試題，即力扣上的第1221題-分割平衡字符串。

本文主要介紹貪心+棧的策略來解答此題，供大家參考，希望對(duì)大家有所幫助。

分割平衡字符串

在一個(gè)平衡字符串中，'L' 和 'R' 字符的數(shù)量是相同的。

給你一個(gè)平衡字符串 s，請(qǐng)你將它分割成盡可能多的平衡字符串。

注意：分割得到的每個(gè)字符串都必須是平衡字符串。

返回可以通過分割得到的平衡字符串的最大數(shù)量 。

示例

示例及提示

解題思路

要求分割得到平衡字符串的最大數(shù)量，很容易想到暴力法，只要遍歷一遍字符串，統(tǒng)計(jì)字符 'L' 和 'R' 的數(shù)量，即可計(jì)算出題目要求的結(jié)果。

方法一：暴力法

遍歷字符串，統(tǒng)計(jì) 'L' 和 'R' 的數(shù)量，當(dāng)其數(shù)量相同時(shí)，則表明可以當(dāng)前遍歷到的字符可跟之前的遍歷的那些字符構(gòu)成平衡字符串，此時(shí)統(tǒng)計(jì)平衡字符串的個(gè)數(shù)，并將 'L' 和 'R' 的數(shù)量全部置 0，然后繼續(xù)遍歷并統(tǒng)計(jì)平衡字符串的個(gè)數(shù)，直至遍歷完整個(gè)字符串即可。

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ù)雜度分析

時(shí)間復(fù)雜度：O(n)，其中 n 為字符串的長度，需要遍歷一遍字符串。

空間復(fù)雜度：O(1)，未開辟額外的存儲(chǔ)空間。

方法二：貪心 + 棧

本題也可以采用貪心的思想，遍歷字符串時(shí)，遇到一個(gè)個(gè)平衡字符串時(shí)，將其分割出來，再繼續(xù)遍歷剩余的子字符串。

同時(shí)可以采用棧的思想，在遍歷字符串時(shí)，如果遇到字符 'R' 時(shí)，讓其入棧，棧內(nèi)的字符個(gè)數(shù)加一;遇到字符 'L' 時(shí)，讓字符 'R' 出棧，棧內(nèi)的字符個(gè)數(shù)減一。

遍歷的同時(shí)判斷棧中的字符個(gè)數(shù)是否為 0，若為 0，則代表已遍歷的字符已構(gòu)成平衡字符串，統(tǒng)計(jì)平衡字符串的個(gè)數(shù)，直至遍歷結(jié)束。

舉例

以字符串 s = "RLLLRRLR" 為例。

例子

在遍歷到 s 的某一字符時(shí)，用兩個(gè)變量 cnt 和 res 分別記錄字符 'R' 和 'L' 之差以及平衡字符串的數(shù)量;

設(shè)置兩個(gè)變量，邊遍歷邊統(tǒng)計(jì)平衡字符串個(gè)數(shù)

計(jì)算 cnt 和 res 的大小;

遍歷到 'R' 時(shí)，cnt 加 1

遍歷到 'L'時(shí)，cnt 減 1 并計(jì)算 res

完整的計(jì)算過程，如下動(dòng)圖示：

計(jì)算平衡字符串的完整過程動(dòng)圖

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ù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，其中 n 為字符串的長度，需要遍歷一遍字符串。
• 空間復(fù)雜度：O(1)，未開辟額外的存儲(chǔ)空間。