LeetCode Contest 186 5392. 分割字符串的最大得分 Maximum Score After Splitting a String

简介: LeetCode Contest 186 5392. 分割字符串的最大得分 Maximum Score After Splitting a String

LeetCode Contest 186 5392. 分割字符串的最大得分 Maximum Score After Splitting a String


Table of Contents

一、中文版

二、英文版

三、My answer

四、解题报告


一、中文版

给你一个由若干 0 和 1 组成的字符串 s ,请你计算并返回将该字符串分割成两个 非空 子字符串(即 左 子字符串和 右 子字符串)所能获得的最大得分。

「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。

 

示例 1:

输入:s = "011101"

输出:5  

解释:

将字符串 s 划分为两个非空子字符串的可行方案有:

左子字符串 = "0" 且 右子字符串 = "11101",得分 = 1 + 4 = 5  

左子字符串 = "01" 且 右子字符串 = "1101",得分 = 1 + 3 = 4  

左子字符串 = "011" 且 右子字符串 = "101",得分 = 1 + 2 = 3  

左子字符串 = "0111" 且 右子字符串 = "01",得分 = 1 + 1 = 2  

左子字符串 = "01110" 且 右子字符串 = "1",得分 = 2 + 1 = 3

示例 2:

输入:s = "00111"

输出:5

解释:当 左子字符串 = "00" 且 右子字符串 = "111" 时,我们得到最大得分 = 2 + 3 = 5

示例 3:

输入:s = "1111"

输出:3

提示:

2 <= s.length <= 500

字符串 s 仅由字符 '0' 和 '1' 组成。


二、英文版

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).
The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.
Example 1:
Input: s = "011101"
Output: 5  
Explanation:  
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5  
left = "01" and right = "1101", score = 1 + 3 = 4  
left = "011" and right = "101", score = 1 + 2 = 3  
left = "0111" and right = "01", score = 1 + 1 = 2  
left = "01110" and right = "1", score = 2 + 1 = 3
Example 2:
Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5
Example 3:
Input: s = "1111"
Output: 3
Constraints:
2 <= s.length <= 500
The string s consists of characters '0' and '1' only.


三、My answer

class Solution:
    def maxScore(self, s: str) -> int:
        res = 0
        for i in range(1,len(s)):
            tmp = s[:i].count('0') + s[i:].count('1')
            res = max(res, tmp)
        return res


四、解题报告

因为 s 的长度不会超过 500,所以可以使用暴力遍历方法:

截断每个位置,判断截断前半部分中 0 的个数和截断后半部分中 1 的个数之和。

与 res 比较,选出最大值,赋给 res。

相关文章
|
7天前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
23 1
|
21天前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
22 9
|
21天前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
14 0
|
21天前
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
27 0
|
21天前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
15 0
|
21天前
【LeetCode 19】541.反转字符串II
【LeetCode 19】541.反转字符串II
18 0
|
21天前
【LeetCode 18】6.2.反转字符串
【LeetCode 18】6.2.反转字符串
14 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
52 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2