【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 <= 105
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);}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
