X

LEETCODE 1422. Maximum Score After Splitting a String 解题思路分析

题目大意:

分割字符串的最大得分

给你一个由若干 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' 组成。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1422

解题思路分析:

这道题没有太大的难度,我们分别遍历每一种分割方式,计算出各自的得分,然后再取一个最大得分即可。本题唯一可以优化的地方便是,每一次分割后,我们不需要重新计算一次总分,只需要更改变化的部分即可。具体实现可参照代码。

实现代码:

public int maxScore(String s) {
    // 先将s分割为长度为1(左)和length减一(右)两部分
    // 计算出下标大于等于1(右半部分)的所有1的数量
    int countOne=0;
    for(int i=1;i<s.length();i++){
        if(s.charAt(i)=='1') countOne++;
    }
    // 计算出下标小于1的所有(第0位,左半部分)0的数量
    int countZero= s.charAt(0)=='0'?1:0;
    // 当前分割的得分。即当前最大得分
    int max=countZero + countOne;
    // 遍历其他所有分割方式
    for(int i=2;i<s.length();i++){
        // 如果右半部分减少的是1,则右半部分1的数量减一
        if(s.charAt(i-1)=='1') countOne--;
        // 反之如果右半部分减少的是0,也就是左半部分0的数量加一
        else countZero++;
        // 利用当前的和更新全局最大和
        max=Math.max(max, countZero + countOne);
    }
    return max;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 99.14% of Java online submissions for Maximum Score After Splitting a String.

Memory Usage: 38.1 MB, less than 100.00% of Java online submissions for Maximum Score After Splitting a String.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1422-maximum-score-after-splitting-a-string-解题思路分析/
Categories: leetcode
kwantong: