1422. 分割字符串的最大得分 Maximum Score After Splitting a String

问题描述

暴力法

这个用于验证思路, 直接遍历数组, 计算每个分隔位点的数值, 求得其中最大的那个.

#![allow(unused)]
fn main() {
// Brute force
pub fn max_score1(s: String) -> i32 {
    debug_assert!(s.len() >= 2);

    let mut max_value = 0;
    for i in 1..s.len() {
        let count_zeros = s[0..i]
            .as_bytes()
            .iter()
            .copied()
            .filter(|byte| *byte == b'0')
            .count();
        let count_ones = s[i..]
            .as_bytes()
            .iter()
            .copied()
            .filter(|byte| *byte == b'1')
            .count();
        let sum = count_zeros + count_ones;
        max_value = max_value.max(sum);
    }
    max_value as i32
}
}

这个算法的时间复杂度是 O(n^2), 因为存在两层遍历数组的操作; 空间复杂度是 O(1).

前缀和 Prefix sum

这个方法, 先计算好每个分隔位点之前的 0 的个数以及分隔位点之后的 1 的个数, 然后计算其中最大的那个组合.

具体步骤是:

1. 创建 count_zeros 数组, 用于存放从前向后字符 0 出现的次数之和
2. 从前向后遍历字符串, 统计出字符 0 出现的次数之和, 并存入 count_zeros 数组
3. 创建 count_ones 数组, 用于存放从后向前字符 1 出现的次数之和
4. 从后向前遍历字符串, 统计出字符 1 出现的次数之和, 并存入 count_ones 数组
5. 将 count_ones 数组反转, 方便后面的计算
6. 遍历计数数组 (cont_ones, count_zeros), 找出最大的那个组合

#![allow(unused)]
fn main() {
// Prefix sum
pub fn max_score2(s: String) -> i32 {
    debug_assert!(!s.is_empty());

    let len = s.len();

    // 从前向后统计字符 `0` 出现的次数
    let count_zeros = {
        let mut count_zeros = Vec::with_capacity(len);
        let mut last_zeros = 0;
        for &byte in s.as_bytes() {
            if byte == b'0' {
                last_zeros += 1;
            }
            count_zeros.push(last_zeros);
        }
        count_zeros
    };

    // 从后向前统计字符 `1` 出现的次数
    let count_ones = {
        let mut count_ones = Vec::with_capacity(len);
        let mut last_ones = 0;
        for &byte in s.as_bytes().iter().rev() {
            if byte == b'1' {
                last_ones += 1;
            }
            count_ones.push(last_ones);
        }
        // 将 `1` 的计数数组反转
        count_ones.reverse();
        count_ones
    };

    // 遍历计数数组, 找到最大的那个组合
    let mut max_sum = 0;
    for i in 1..len {
        // s[0..i] 计算包含 `0` 的个数
        // s[i..] 计算包含 `1` 的个数
        let sum = count_zeros[i - 1] + count_ones[i];
        max_sum = max_sum.max(sum);
    }
    max_sum
}
}

算法的时间复杂度是 O(n), 空间复杂度是 O(n), 因为引入了两个辅助数组.