【leetcode】【2022/8/14】1422. 分割字符串的最大得分

问题描述：

• 给定一个二进制字符串，将字符串分割为非空的左字符串和非空的右字符串，其中左字符串中统计 0 的个数，右字符串中统计 1 的个数，将数量相加即为分割所得分数，返回分割所能获得的最大分数。

核心思路：

• 可以直接用前缀数组 + 后缀数组的方法来解决。
  • 前缀数组记录 0 的个数，后缀数组记录 1 的个数，两次遍历统计完个数后再单次遍历所有的分割情况即可。
• 实际上不需要额外利用数组来统计前缀后缀。
  • 可以单次遍历获得 1 的总数，接着再单次遍历获得前缀 0 的个数，过程中将前缀 1 的个数从总数中减去即可。

代码实现：

• 前缀后缀思路代码实现如下：

  class Solution
  {
  public:
      int maxScore(string s)
      {
          int m = s.size();
          vector<int> prefix(m);
          vector<int> suffix(m);
          prefix[0] = s[0] == '0';
          for(int i = 1; i < m; ++i) prefix[i] = prefix[i-1] + (s[i] == '0');
          suffix[m-1] = s[m-1] == '1';
          for(int i = m-2; i >= 0; --i) suffix[i] = suffix[i+1] + (s[i] == '1');
          int ans = 0;
          for(int i = 0; i < m-1; ++i)
              ans = max(ans, prefix[i] + suffix[i+1]);
          return ans;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18

• 优化思路代码实现如下：

  class Solution
  {
  public:
      int maxScore(string s)
      {
          int m = s.size();
          int cnt1 = 0;
          for(int i = 0; i < m; ++i) cnt1 += s[i] == '1';
          int cnt0 = 0;
          int ans = 0;
          for(int i = 0; i < m-1; ++i)
          {
              cnt0 += s[i] == '0';
              cnt1 -= s[i] == '1';
              ans = max(ans, cnt0 + cnt1);
          }
          return ans;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19