本文涉及知识点

C++前后缀分解

LeetCode926. 将字符串翻转到单调递增

如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。
给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。
返回使 s 单调递增的最小翻转次数。
示例 1：
输入：s = “00110”
输出：1
解释：翻转最后一位得到 00111.
示例 2：
输入：s = “010110”
输出：2
解释：翻转得到 011111，或者是 000111。
示例 3：
输入：s = “00011000”
输出：2
解释：翻转得到 00000000。
提示：
1 <= s.length <= 10⁵
s[i] 为 ‘0’ 或 ‘1’

前后缀分解

pre[i] 记录s长度为i的前缀翻转成全部是’0’需要的次数。
suff[i]记录s长度为i的后缀翻转成全部是’1’需要的次数。
枚举0的长度，求最小翻转次数。

代码

核心代码

	class Solution {
		public:
			int minFlipsMonoIncr(string s) {
				vector<int> pre(1), suff(1);
				for (const auto& ch : s) {
					pre.emplace_back(pre.back() + ('1' == ch));
				}
				for (auto it = s.rbegin(); it != s.rend(); ++it) {
					suff.emplace_back(suff.back() + ('0' == *it));
				}
				int ans = s.length();
				for (int i = 0; i <= s.length(); i++) {
					ans = min(ans, pre[i] + suff[s.length() - i]);
				}
				return ans;
			}
		};

单元测试

string s;
		TEST_METHOD(TestMethod11)
		{
			s = "00110";
			auto res = Solution().minFlipsMonoIncr(s);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "010110";
			auto res = Solution().minFlipsMonoIncr(s);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			s = "00011000";
			auto res = Solution().minFlipsMonoIncr(s);
			AssertEx(2, res);
		}