贪心让你分割更多平衡字符串

本文转载自微信公众号「程序员小熊」，作者Dine 。转载本文请联系程序员小熊公众号。

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：申请域名、网站空间、营销软件、网站建设、沂水网站维护、网站推广。

前言

大家好，我是来自于华为的程序员小熊。今天给大家带来一道字符串相关的题目，这道题也是今天的力扣每日一题，同时也是华为、苹果、谷歌和雅虎等大厂的面试题，即力扣上的第1221题-分割平衡字符串。

本文主要介绍贪心+栈的策略来解答此题，供大家参考，希望对大家有所帮助。

分割平衡字符串

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

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

注意：分割得到的每个字符串都必须是平衡字符串。

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

示例

示例及提示

解题思路

要求分割得到平衡字符串的最大数量，很容易想到暴力法，只要遍历一遍字符串，统计字符 'L' 和 'R' 的数量，即可计算出题目要求的结果。

方法一：暴力法

遍历字符串，统计 'L' 和 'R' 的数量，当其数量相同时，则表明可以当前遍历到的字符可跟之前的遍历的那些字符构成平衡字符串，此时统计平衡字符串的个数，并将 'L' 和 'R' 的数量全部置 0，然后继续遍历并统计平衡字符串的个数，直至遍历完整个字符串即可。

Show me the Code

「C」

 
 
 
 
    
  
  
  
  
  1. int balancedStringSplit(char * s) { 
    2.   
  
  
  
  2.     int numR = 0, numL = 0, res = 0; 
    3.   
  
  
  
  3.     for (int i = 0; s[i] != '\0'; ++i) { 
    4.   
  
  
  
  4.         if (s[i] == 'L') { 
    5.   
  
  
  
  5.             numL++; 
    6.   
  
  
  
  6.         } else { 
    7.   
  
  
  
  7.             numR++; 
    8.   
  
  
  
  8.         } 
    9.   
  
  
  
  9.  
    10.   
  
  
  
  10.         if (numL == numR) { 
    11.   
  
  
  
  11.             res++; 
    12.   
  
  
  
  12.             numL = 0; 
    13.   
  
  
  
  13.             numR = 0; 
    14.   
  
  
  
  14.         } 
    15.   
  
  
  
  15.     } 
    16.   
  
  
  
  16.  
    17.   
  
  
  
  17.     return res;  
    18.   
  
  
  
  18. } 
    19.

复杂度分析

时间复杂度：O(n)，其中 n 为字符串的长度，需要遍历一遍字符串。

空间复杂度：O(1)，未开辟额外的存储空间。

方法二：贪心 + 栈

本题也可以采用贪心的思想，遍历字符串时，遇到一个个平衡字符串时，将其分割出来，再继续遍历剩余的子字符串。

同时可以采用栈的思想，在遍历字符串时，如果遇到字符 'R' 时，让其入栈，栈内的字符个数加一;遇到字符 'L' 时，让字符 'R' 出栈，栈内的字符个数减一。

遍历的同时判断栈中的字符个数是否为 0，若为 0，则代表已遍历的字符已构成平衡字符串，统计平衡字符串的个数，直至遍历结束。

举例

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

例子

在遍历到 s 的某一字符时，用两个变量 cnt 和 res 分别记录字符 'R' 和 'L' 之差以及平衡字符串的数量;

设置两个变量，边遍历边统计平衡字符串个数

计算 cnt 和 res 的大小;

遍历到 'R' 时，cnt 加 1

遍历到 'L'时，cnt 减 1 并计算 res

完整的计算过程，如下动图示：

计算平衡字符串的完整过程动图

Show me the Code

「C」

 
 
 
 
    
  
  
  
  
  1. int balancedStringSplit(char * s) { 
    2.   
  
  
  
  2.     int cnt = 0, res = 0; 
    3.   
  
  
  
  3.     for (int i = 0; s[i] != '\0'; ++i) { 
    4.   
  
  
  
  4.         cnt += s[i] == 'R' ? 1 : -1; 
    5.   
  
  
  
  5.         if (cnt == 0) { 
    6.   
  
  
  
  6.             res++; 
    7.   
  
  
  
  7.         } 
    8.   
  
  
  
  8.     } 
    9.   
  
  
  
  9.  
    10.   
  
  
  
  10.     return res;  
    11.   
  
  
  
  11. } 
    12.

「C++」

 
 
 
 
    
  
  
  
  
  1. int balancedStringSplit(string s) { 
    2.   
  
  
  
  2.     int res = 0, cnt = 0; 
    3.   
  
  
  
  3.     for (auto a : s) { 
    4.   
  
  
  
  4.         cnt += a == 'R' ? 1 : -1; 
    5.   
  
  
  
  5.         if (cnt == 0) { 
    6.   
  
  
  
  6.             res += 1; 
    7.   
  
  
  
  7.         } 
    8.   
  
  
  
  8.     } 
    9.   
  
  
  
  9.  
    10.   
  
  
  
  10.     return res; 
    11.   
  
  
  
  11. } 
    12.

「Java」

 
 
 
 
    
  
  
  
  
  1. int balancedStringSplit(String s) { 
    2.   
  
  
  
  2.     int res = 0, cnt = 0; 
    3.   
  
  
  
  3.     for (int i = 0; i < s.length(); i++) { 
    4.   
  
  
  
  4.         cnt += s.charAt(i) == 'R' ? 1 : -1; 
    5.   
  
  
  
  5.         if (cnt == 0) { 
    6.   
  
  
  
  6.             res += 1; 
    7.   
  
  
  
  7.         } 
    8.   
  
  
  
  8.     } 
    9.   
  
  
  
  9.  
    10.   
  
  
  
  10.     return res; 
    11.   
  
  
  
  11. } 
    12.

「Python3」

 
 
 
 
    
  
  
  
  
  1. def balancedStringSplit(self, s: str) -> int: 
    2.   
  
  
  
  2.     res, cnt = 0, 0         
    3.   
  
  
  
  3.     for c in s: 
    4.   
  
  
  
  4.         cnt += 1 if c == 'R' else -1           
    5.   
  
  
  
  5.         if cnt == 0: 
    6.   
  
  
  
  6.             res += 1 
    7.   
  
  
  
  7.          
    8.   
  
  
  
  8.     return res 
    9.

「Golang」

 
 
 
 
    
  
  
  
  
  1. func balancedStringSplit(s string) int { 
    2.   
  
  
  
  2.     cnt, res := 0, 0 
    3.   
  
  
  
  3.     for _, ch := range s { 
    4.   
  
  
  
  4.         if ch == 'R' { 
    5.   
  
  
  
  5.             cnt++ 
    6.   
  
  
  
  6.         } else { 
    7.   
  
  
  
  7.             cnt-- 
    8.   
  
  
  
  8.         } 
    9.   
  
  
  
  9.  
    10.   
  
  
  
  10.         if cnt == 0 { 
    11.   
  
  
  
  11.             res++ 
    12.   
  
  
  
  12.         } 
    13.   
  
  
  
  13.     } 
    14.   
  
  
  
  14.  
    15.   
  
  
  
  15.     return res 
    16.   
  
  
  
  16. } 
    17.

复杂度分析

  • 时间复杂度：O(n)，其中 n 为字符串的长度，需要遍历一遍字符串。
  • 空间复杂度：O(1)，未开辟额外的存储空间。

网站题目：贪心让你分割更多平衡字符串
网页路径：http://www.shufengxianlan.com/qtweb/news4/504454.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

商城网站知识

行业网站建设

成都微信开发　　 　蓬溪网站建设　　 　营销型网站建设　　 　成都定制网站开发　　 　成都VI设计　　 　手机网站制作设计　　 　虚拟主机　　 　成都广告设计　　 　东电技服　　 　网站制作公司　　 　成都网站建设公司　　 　高防机房　　 　达州网站建设　　 　成都光华机房服务器托管　　 　移动网站建设　　 　成都网站维护　　 　名片印刷厂　　 　成都网站建设　　 　成都微商城开发　　 　橡塑保温材料