leetcode
leetcode 1301 ~ 1350
分割字符串的最大得分

分割字符串的最大得分

难度:

标签:

题目描述

代码结果

运行时间: 22 ms, 内存: 15.9 MB


/*
 * 题目思路:
 * 使用Java Stream API实现同样的逻辑。
 * 具体步骤:
 * 1. 初始化一个变量maxScore记录最大得分,初始值为0。
 * 2. 遍历字符串s的每一个分割点,将字符串分为左子字符串和右子字符串。
 * 3. 使用Stream API计算左子字符串中0的数量和右子字符串中1的数量。
 * 4. 更新maxScore为当前得分和maxScore中的较大值。
 * 5. 返回maxScore。
 */
import java.util.stream.IntStream;

public class Solution {
    public int maxScore(String s) {
        return IntStream.range(1, s.length())
                .map(i -> {
                    long leftScore = s.substring(0, i).chars().filter(c -> c == '0').count();
                    long rightScore = s.substring(i).chars().filter(c -> c == '1').count();
                    return (int)(leftScore + rightScore);
                })
                .max()
                .orElse(0);
    }
}

解释

方法:

首先,计算字符串中'1'的总数。然后,初始化得分(ans)为整个字符串中'1'的数量加上第一个字符如果是'0'则加1,如果是'1'则减1。这样处理后,得分反映了在第一个字符处分割字符串的情况。接着,遍历字符串的其余部分(除了最后一个字符,因为右侧子字符串不能为空),更新左侧子字符串中'0'的数量和'1'的数量。每次遍历到新的字符时,计算新的得分:整个字符串的'1'的数量减去当前左侧'1'的数量加上当前左侧'0'的数量。如果这个得分大于当前记录的最大得分,就更新最大得分。这种方法确保了每一种可能的分割都被考虑,且每次只考虑当前位置的字符,有效地更新当前的得分。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在初始化时,得分需要根据第一个字符是否为'0'或'1'进行加减操作?
在这个算法中,初始化得分的操作是为了设置第一个字符作为分割点(即左子字符串包含第一个字符,右子字符串包含其余所有字符)的初始情况。如果第一个字符是'0',则左侧子字符串的得分应该增加1(因为'0'的得分是1),如果是'1',则因为这个'1'已经被计入了总的'1'的数量c中,所以需要从得分中减去这个'1',以反映它不再为右侧子字符串贡献得分。这样做可以正确地初始化得分,反映出在第一个字符处进行分割的情况。
🦆
在遍历字符串计算最大得分时,为什么选择忽略最后一个字符,这样的处理有什么特别的意义吗?
在题解中,忽略最后一个字符是因为分割字符串必须确保左右两侧都至少有一个字符。如果包括最后一个字符在内进行遍历,那么在到达字符串末尾时,右侧子字符串将为空,这违反了题目的原则。因此,为了保证每次分割后的两个子字符串都是有效的,算法只遍历到倒数第二个字符。
🦆
题解中提到每次更新得分时,使用的公式是`c - o + z`,能否详细解释这个公式是如何计算得分的?
在公式`c - o + z`中,`c`代表整个字符串中'1'的总数,`o`代表当前左侧子字符串中'1'的数量,`z`代表左侧子字符串中'0'的数量。公式中的`c - o`实际上是计算右侧子字符串中'1'的数量,因为整个字符串的'1'数量减去左侧的'1'数量就得到右侧的'1'数量。而`z`直接代表左侧子字符串中'0'的得分。所以,`c - o + z`表示左侧子字符串的'0'得分加上右侧子字符串的'1'得分,这是当前分割位置的总得分。
🦆
在实际编码中,是否需要考虑输入字符串`s`只包含一个字符的特殊情况?
是的,在实际编码实践中,应该考虑输入字符串`s`只有一个字符的情况。这种情况下,无法进行有效的分割,因为分割后一侧必然为空,这违反了题目要求左右两侧都至少有一个字符的规定。因此,应当在代码中增加判断,如果输入字符串长度不大于1,则直接返回0或其他特定值,以处理这种边界情况。

相关问题