【C++前后缀分解】1888. 使二进制字符串字符交替的最少反转次数|2005

本文涉及知识点

C++前后缀分解

LeetCode1888. 使二进制字符串字符交替的最少反转次数

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：
类型 1 ：删除字符串 s 的第一个字符并将它添加到字符串结尾。
类型 2 ：选择字符串 s 中任意一个字符并将该字符反转，也就是如果值为 ‘0’ ，则反转得到 ‘1’ ，反之亦然。
请你返回使 s 变成交替字符串的前提下，类型 2 的最少操作次数。
我们称一个字符串是交替的，需要满足任意相邻字符都不同。
比方说，字符串 “010” 和 “1010” 都是交替的，但是字符串 “0100” 不是。
示例 1：
输入：s = “111000”
输出：2
解释：执行第一种操作两次，得到 s = “100011” 。
然后对第三个和第六个字符执行第二种操作，得到 s = “101010” 。
示例 2：
输入：s = “010”
输出：0
解释：字符串已经是交替的。
示例 3：
输入：s = “1110”
输出：1
解释：对第二个字符执行第二种操作，得到 s = “1010” 。
提示：
1 <= s.length <= 10⁵
s[i] 要么是 ‘0’ ，要么是 ‘1’ 。

前后缀分解

right[i]记录s长度为i的后缀，转换成以0结尾的交叉串需要的第二种操作的次数。
即s的转置字符串相同长度前缀，以0开头的交叉串需要的次数。
显然s长度为i的后缀，转换成以1结尾的交叉串需要i-right[i]次。

left[i]记录 s长度为i的前缀转换成以0开头的交叉串需要的第二种操作的次数。
显然将长度为i的前缀，转换成以1开头的交叉串需要的次数为：i -left[i]次。

代码

打开打包代码的方法兼述单元测试

核心代码

class Solution {public:int minFlips(string s) {auto Pre = [&](const string& s) {vector<int> ret(1);for (int i = 0; i < s.length(); i++) {ret.emplace_back(ret.back()+(i % 2 != (s[i] - '0')));}return ret;};auto Get =[] (const vector<int>& preSum,int len, int value){if (0 == value) { return preSum[len]; }return len - preSum[len];};auto left = Pre(s);auto right = Pre(string(s.rbegin(), s.rend()));int ret = s.length();for (int i = 0; i <= s.length(); i++) {int begin = 0;{const int sufEnd = (i & 1) ? begin : (begin + 1) % 2;const int preBegin = (sufEnd + 1) % 2;ret = min(ret, Get(right, i, sufEnd) + Get(left, s.length() - i, preBegin));}begin = 1;{const int sufEnd = (i & 1) ? begin : (begin + 1) % 2;const int preBegin = (sufEnd + 1) % 2;ret = min(ret, Get(right, i, sufEnd) + Get(left, s.length() - i, preBegin));}}return ret;}};

单元测试

string s;TEST_METHOD(TestMethod11){s = "111000";auto res = Solution().minFlips(s);AssertEx(2, res);}TEST_METHOD(TestMethod12){s = "010";auto res = Solution().minFlips(s);AssertEx(0, res);}TEST_METHOD(TestMethod13){s = "1110";auto res = Solution().minFlips(s);AssertEx(1, res);}TEST_METHOD(TestMethod14){s="001000000010";auto res = Solution().minFlips(s);AssertEx(4, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功