leetcode1422题解 —— 一次遍历的在线算法

Problem

Problem: 1422. 分割字符串的最大得分

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

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

示例 1：

1 2 3 4 5 6 7 8 9

输入：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：

1 2 3

输入：s = "00111" 输出：5 解释：当 左子字符串 = "00" 且 右子字符串 = "111" 时，我们得到最大得分 = 2 + 3 = 5

示例 3：

1 2	输入：s = "1111" 输出：3

提示：

• 2 <= s.length <= 500
• 字符串 s 仅由字符 '0' 和 '1' 组成。

核心思想

单次遍历的在线贪心算法，同时解得分割线位置与最大得分。

思路

首先注意到，一个字符对于得分的贡献，完全取决于它位于分隔线的左侧还是右侧。于是我们可以发现：对于一个前缀子串, 其内部的最优分割方案不会受到及之后字符的影响。这意味着问题具备最优子结构，我们可以先尝试求解子问题的最优解然后转移得到最优解。
设想一个子问题，我们已经得到了它的最优解(最大得分和分割线位置)。现增添一个新的字符，构成一个新问题, 那么这个新问题的最优解有两种来源:

1. 最优分割点在原串范围内: 由于新字符添加之后，所有旧的分割方案得分都会同步变化，因此旧范围内最优分割点位置不变，只需更新得分即可。
2. 最优分割点就是新增的位置：即和之间, 这是一个全新的候选解。

那么，新问题的最大得分就是上述两种情况中的较大者。即只需要比较原最优分割位置与新位置的得分，取最大值，即可完成状态转移。与此同时，我们可以通过维护原最优分割线到新分割线之间0和1的数量，来快速比较两个得分，并完成切换分割点时得分的更新。
所以每一步，我们只需要贪心地比较新旧位置的得分并完成更新即可。

解题过程

设字符串为，长度为n。定义下标范围为的子问题，其状态为，其中：

• : 当前子串的最大得分
• : 当前子串的一个最优分割点位置; 表示分割线位于到之间
• : 当前子问题分割点右侧0的个数
• : 当前子问题分割点右侧1的个数

初始状态(base case):

状态转移:
从转移到:

具体步骤可分解为:

1. 初始化: , 左侧为0则初始1分。
2. 遍历字符串中剩下的字符, 索引为 (在的时候旧位置与新位置重合，不破坏逻辑)
   1. 每次先判断，若满足则更新, +=-, 同时清空, 。
   2. 再判断若新字符为0，则++, 否则++并且++。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int maxScore(string s) {

        if(s.size()<2) throw exception();

        int r0 = 0;//分割点右边的0的个数
        int r1 = 0;//分割点右边的1的个数
        int p = 1; //分割线在index几的左边

        int score = (s[0]=='0');
        for(int i=1; i<s.size(); ++i){
            if(r0 > r1){//更新分割点
                p = i;
                score += r0 - r1;
                r0 = r1 = 0;
            }

            if(s.at(i) == '0'){
                ++r0;
            }
            else{
                ++r1;
                ++score;
            }
        }
        return score;
    }
};

复杂度

• 时间复杂度:
• 空间复杂度:

虽然这只是一道简单题，但追求极致效率的过程还是蛮有趣的。在LeetCode上看到了很多题解，但是似乎没有人提到17号的这种方法，并且17号自认这个方法简单易懂效率高，遂写了份题解，分享一下~
因为17号是算法小白，写得不好的地方还请大佬们轻喷orz