分割字符串的最大得分
难度:
标签:
题目描述
代码结果
运行时间: 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'进行加减操作?
▷🦆
在遍历字符串计算最大得分时,为什么选择忽略最后一个字符,这样的处理有什么特别的意义吗?
▷🦆
题解中提到每次更新得分时,使用的公式是`c - o + z`,能否详细解释这个公式是如何计算得分的?
▷🦆
在实际编码中,是否需要考虑输入字符串`s`只包含一个字符的特殊情况?
▷