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

简介: 在一个 平衡字符串 中,'L' 和 'R' 字符的数量是相同的。给你一个平衡字符串 s,请你将它分割成尽可能多的平衡字符串。注意:分割得到的每个字符串都必须是平衡字符串,且分割得到的平衡字符串是原平衡字符串的连续子串。返回可以通过分割得到的平衡字符串的 最大数量 。

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://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~

相关文章
|
1月前
|
JavaScript 前端开发 Java
通义灵码 Rules 库合集来了,覆盖Java、TypeScript、Python、Go、JavaScript 等
通义灵码新上的外挂 Project Rules 获得了开发者的一致好评:最小成本适配我的开发风格、相当把团队经验沉淀下来,是个很好功能……
674 101
|
6月前
|
人工智能 安全 Java
Java和Python在企业中的应用情况
Java和Python在企业中的应用情况
180 7
|
2月前
|
Java API Docker
在线编程实现!如何在Java后端通过DockerClient操作Docker生成python环境
以上内容是一个简单的实现在Java后端中通过DockerClient操作Docker生成python环境并执行代码,最后销毁的案例全过程,也是实现一个简单的在线编程后端API的完整流程,你可以在此基础上添加额外的辅助功能,比如上传文件、编辑文件、查阅文件、自定义安装等功能。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
在线编程实现!如何在Java后端通过DockerClient操作Docker生成python环境
|
6月前
|
Java 程序员 开发工具
在比较Java和Python哪个更易学
在比较Java和Python哪个更易学
78 4
|
3月前
|
C语言 Python
Python学习:内建属性、内建函数的教程
本文介绍了Python中的内建属性和内建函数。内建属性包括`__init__`、`__new__`、`__class__`等,通过`dir()`函数可以查看类的所有内建属性。内建函数如`range`、`map`、`filter`、`reduce`和`sorted`等,分别用于生成序列、映射操作、过滤操作、累积计算和排序。其中,`reduce`在Python 3中需从`functools`模块导入。示例代码展示了这些特性和函数的具体用法及注意事项。
|
7月前
|
存储 算法 API
Python学习五:函数、参数(必选、可选、可变)、变量、lambda表达式、内置函数总结、案例
这篇文章是关于Python函数、参数、变量、lambda表达式、内置函数的详细总结,包含了基础知识点和相关作业练习。
100 0
|
11月前
|
存储 Python Windows
【Python学习篇】Python实验小练习——函数(十)
【Python学习篇】Python实验小练习——函数(十)
71 1
|
11月前
|
存储 Python
【Python学习篇】Python——函数(九)
【Python学习篇】Python——函数(九)
102 1
|
10月前
|
API Python
Python学习日记(二:函数和逻辑操作)
Python中的函数和逻辑操作至关重要。函数包括可变和不可变参数。
|
Python
【Python21天学习挑战赛】- 函数进阶
【Python21天学习挑战赛】- 函数进阶

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等