【算法学习】1221. 分割平衡字符串(java / c / c++ / python / go / rust)

二当家的白帽子 2021-10-29 15:05:10
学习 算法 法学 平衡 分割

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子 https://le-yi.blog.csdn.net/ 博客原创~



1221. 分割平衡字符串:

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

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

注意:分割得到的每个字符串都必须是平衡字符串,且分割得到的平衡字符串是原平衡字符串的连续子串。

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

样例 1

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

样例 2

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

样例 3

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

样例 4

输入:
s = "RLRRRLLRLL"
输出:
2
解释:
s 可以分割为 "RL"、"RRRLLRLL" ,每个子字符串中都包含相同数量的 'L' 和 'R' 。

提示

  • 1 <= s.length <= 1000
  • s[i] = ‘L’ 或 ‘R’
  • s 是一个 平衡 字符串

分析

  • 这道算法题如果说s本身不是平衡字符串就会有点难度。
  • 由于s本身就是平衡字符串,所以从左到右可以使用贪心,越短则可以分的越多,而且剩下的字符串也是平衡字符串。
  • 我们需要记录遍历过程中‘L’和‘R’的数量,如果相等就是一个平衡字符串。
  • 分别记录‘L’和‘R’的数量需要2个变量,但是我们可以记录他们的差值,差为0就说明数量相等,也就是平衡字符串了,这样就只需要一个变量来做记录。

题解

java

class Solution {

public int balancedStringSplit(String s) {

int ans = 0;
// 记录左和右的差值,左减,右加,为0表示左右数量一样
int v = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {

if (s.charAt(i) == 'L') {

--v;
} else {

++v;
}
if (v == 0) {

++ans;
}
}
return ans;
}
}

c

int balancedStringSplit(char * s){

int ans = 0;
// 记录左和右的差值,左减,右加,为0表示左右数量一样
int v = 0;
while (*s) {

*s == 'L' ? --v : ++v;
if (v == 0) {

++ans;
}
++s;
}
return ans;
}

c++

class Solution {

public:
int balancedStringSplit(string s) {

int ans = 0;
// 记录左和右的差值,左减,右加,为0表示左右数量一样
int v = 0;
for (char c : s) {

c == 'L' ? --v : ++v;
if (v == 0) {

++ans;
}
}
return ans;
}
};

python

class Solution:
def balancedStringSplit(self, s: str) -> int:
ans = 0
# 记录左和右的差值,左减,右加,为0表示左右数量一样
v = 0
for c in s:
if c == 'L':
v -= 1
else:
v += 1
if v == 0:
ans += 1
return ans

go

func balancedStringSplit(s string) int {

ans := 0
// 记录左和右的差值,左减,右加,为0表示左右数量一样
v := 0
for _, c := range s {

if c == 'L' {

v--
} else {

v++
}
if v == 0 {

ans++
}
}
return ans
}

rust

impl Solution {
pub fn balanced_string_split(s: String) -> i32 {
s.chars().scan(0, |v, c| {
match c {
'L' => *v -= 1,
_ => *v += 1
};
Some(*v)
}).filter(|v| { *v == 0 }).count() as i32
}
}

在这里插入图片描述


原题传送门:https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/


版权声明
本文为[二当家的白帽子]所创,转载请带上原文链接,感谢
https://blog.csdn.net/leyi520/article/details/121034127

  1. Python題,我剛學,還不會
  2. Je viens d'apprendre, pas encore.
  3. 云计算开发:Python3-find()方法详解
  4. Real time access to stock data, free—— Python crawler Sina stock actual combat
  5. Développement de l'informatique en nuage: détails de la méthode Python 3 - find ()
  6. 如何使用Python进行超参调参和调优
  7. 如何使用Python進行超參調參和調優
  8. Comment utiliser Python pour le réglage hyperparamétrique
  9. Première connaissance du module urllib Python
  10. Python入门:看了这篇文章如果1个小时没法入门Python,那么还是换个语言吧!!
  11. Python(day1):Python 3 教程
  12. Python(day3):Python3 安装与环境搭建
  13. Python (day3): installation et environnement Python 3
  14. Python (day1): tutoriel Python 3
  15. Démarrer avec Python: Si vous ne pouvez pas commencer avec Python en une heure, changez de langue!!
  16. Pandas:DataFrame对象的基础操作
  17. 关于#python#的问题:月球上物体的体重在地球上的16.5%,编写程序输出未来10年在地球上和月球上的体重状况
  18. 反转一个3位整数(Python 实现)
  19. Inverse un entier de 3 bits (implémentation Python)
  20. Questions sur # Python #: les objets lunaires pèsent 16,5% de la masse de la terre et un programme est programmé pour produire la masse de la terre et de la lune au cours des 10 prochaines années
  21. Compared with Excel, it is easy to learn Python report automation practice!
  22. 7 excellent open source libraries for learning Python Programming
  23. Use of Python pandas!!!!! Explain in detail
  24. Python Qt GUI设计:QPrinter打印图片类(基础篇—21)
  25. Use of Python pandas!!!!! Explain in detail
  26. 2n行输入,Python,判断字母个数
  27. Notes de Python (XV): dérivation de liste
  28. Notes sur Python (XVI): générateur et Itérateur
  29. Notes de Python (18): décorateur
  30. 2n entrée de ligne, Python, nombre de lettres de jugement
  31. Notes Python (17): fermetures
  32. Notes sur Python (20): fonctions d'ordre supérieur intégrées
  33. 想问问这个Python编程咋做呀?
  34. 想問問這個Python編程咋做呀?
  35. Vous voulez savoir ce que fait cette programmation python?
  36. 11.5K Star,一个开源的 Python 静态类型检查库
  37. Sweetviz:让你只需三行代码实现Python探索性数据分析
  38. Sweetviz:讓你只需三行代碼實現Python探索性數據分析
  39. Sweetviz: vous permet d'effectuer une analyse exploratoire des données python avec seulement trois lignes de code
  40. 11.5k Star, une bibliothèque de vérification de type statique Python Open Source
  41. 刚学Python,想让大大给我解释一下代码
  42. 剛學Python,想讓大大給我解釋一下代碼
  43. Je viens d'apprendre Python et je veux que tu m'expliques le Code.
  44. Python QT GUI Design: qmainwindow, QWidget and qdialog window classes (Fundamentals - 10)
  45. Python爬虫项目实战:快手网页版滑块captchaSession分析
  46. python计算时间十二小时制
  47. Temps de calcul Python 12 heures
  48. Python crawler Project actual Fighting: faster Web Version Slider CAPTCHA session Analysis
  49. Python要学习多久可以掌握?多久可以精通?
  50. Combien de temps Python va - t - il apprendre à maîtriser? Combien de temps faut - il pour maîtriser?
  51. 从官网上下载的python安装包安装不了
  52. 深度学习项目:如何使用Python和OpenCV进行人脸识别
  53. python编辑语言如内容所示
  54. La langue d'édition Python est affichée dans le contenu
  55. 有谁知道这怎么回事嘛(Python的简单代码)
  56. 有誰知道這怎麼回事嘛(Python的簡單代碼)
  57. Qui sait ce qui se passe?
  58. Python求某个数的因数【因数是指能被这个数整除的数。例如6的因数有:1、2、3、6; 7的因数有:1、7; 8的因数有:1、2、4、8】。
  59. Python calcule les facteurs d'un nombre [les facteurs sont des nombres qui peuvent être divisés par ce nombre. Par exemple, les facteurs de 6 sont: 1, 2, 3, 6; les facteurs de 7 sont: 1, 7; et les facteurs de 8 sont: 1, 2, 4, 8].
  60. 如何创建一个python程序来模拟电影院的座位预订