【算法学习】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 博客原创~

相关文章
|
14天前
|
JavaScript 前端开发 Java
通义灵码 Rules 库合集来了,覆盖Java、TypeScript、Python、Go、JavaScript 等
通义灵码新上的外挂 Project Rules 获得了开发者的一致好评:最小成本适配我的开发风格、相当把团队经验沉淀下来,是个很好功能……
482 100
|
3月前
|
运维 监控 算法
监控局域网其他电脑:Go 语言迪杰斯特拉算法的高效应用
在信息化时代,监控局域网成为网络管理与安全防护的关键需求。本文探讨了迪杰斯特拉(Dijkstra)算法在监控局域网中的应用,通过计算最短路径优化数据传输和故障检测。文中提供了使用Go语言实现的代码例程,展示了如何高效地进行网络监控,确保局域网的稳定运行和数据安全。迪杰斯特拉算法能减少传输延迟和带宽消耗,及时发现并处理网络故障,适用于复杂网络环境下的管理和维护。
|
2月前
|
Java API Docker
在线编程实现!如何在Java后端通过DockerClient操作Docker生成python环境
以上内容是一个简单的实现在Java后端中通过DockerClient操作Docker生成python环境并执行代码,最后销毁的案例全过程,也是实现一个简单的在线编程后端API的完整流程,你可以在此基础上添加额外的辅助功能,比如上传文件、编辑文件、查阅文件、自定义安装等功能。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
在线编程实现!如何在Java后端通过DockerClient操作Docker生成python环境
|
3月前
|
存储 缓存 监控
企业监控软件中 Go 语言哈希表算法的应用研究与分析
在数字化时代,企业监控软件对企业的稳定运营至关重要。哈希表(散列表)作为高效的数据结构,广泛应用于企业监控中,如设备状态管理、数据分类和缓存机制。Go 语言中的 map 实现了哈希表,能快速处理海量监控数据,确保实时准确反映设备状态,提升系统性能,助力企业实现智能化管理。
48 3
|
3月前
|
存储 监控 算法
探秘员工泄密行为防线:基于Go语言的布隆过滤器算法解析
在信息爆炸时代,员工泄密行为对企业构成重大威胁。本文聚焦布隆过滤器(Bloom Filter)这一高效数据结构,结合Go语言实现算法,帮助企业识别和预防泄密风险。通过构建正常操作“指纹库”,实时监测员工操作,快速筛查可疑行为。示例代码展示了如何利用布隆过滤器检测异常操作,并提出优化建议,如调整参数、结合日志分析系统等,全方位筑牢企业信息安全防线,守护核心竞争力。
|
4月前
|
Java 调度 开发者
Java线程池ExecutorService学习和使用
通过学习和使用Java中的 `ExecutorService`,可以显著提升并发编程的效率和代码的可维护性。合理配置线程池参数,结合实际应用场景,可以实现高效、可靠的并发处理。希望本文提供的示例和思路能够帮助开发者深入理解并应用 `ExecutorService`,实现更高效的并发程序。
70 10
|
4月前
|
存储 监控 算法
内网监控系统之 Go 语言布隆过滤器算法深度剖析
在数字化时代,内网监控系统对企业和组织的信息安全至关重要。布隆过滤器(Bloom Filter)作为一种高效的数据结构,能够快速判断元素是否存在于集合中,适用于内网监控中的恶意IP和违规域名筛选。本文介绍其原理、优势及Go语言实现,提升系统性能与响应速度,保障信息安全。
49 5
|
4月前
|
Java 数据库连接 数据库
【潜意识Java】深度分析黑马项目《苍穹外卖》在Java学习中的重要性
《苍穹外卖》项目对Java学习至关重要。它涵盖了用户管理、商品查询、订单处理等模块,涉及Spring Boot、MyBatis、Redis等技术栈。
351 4
|
4月前
|
前端开发 Java 数据库连接
【潜意识Java】深度解读JavaWeb开发在Java学习中的重要性
深度解读JavaWeb开发在Java学习中的重要性
63 4
|
4月前
|
存储 移动开发 算法
【潜意识Java】Java基础教程:从零开始的学习之旅
本文介绍了 Java 编程语言的基础知识,涵盖从简介、程序结构到面向对象编程的核心概念。首先,Java 是一种高级、跨平台的面向对象语言,支持“一次编写,到处运行”。接着,文章详细讲解了 Java 程序的基本结构,包括包声明、导入语句、类声明和 main 方法。随后,深入探讨了基础语法,如数据类型、变量、控制结构、方法和数组。此外,还介绍了面向对象编程的关键概念,例如类与对象、继承和多态。最后,针对常见的编程错误提供了调试技巧,并总结了学习 Java 的重要性和方法。适合初学者逐步掌握 Java 编程。
78 1

热门文章

最新文章

AI助理

你好,我是AI助理

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