LeetCode 1888 使二进制字符串交替的最少翻转次数题目描述给你一个二进制字符串s你可以进行两种操作翻转任意一个字符0 变 11 变 0。将字符串的第一个字符移动到末尾即旋转。你可以任意次旋转然后进行若干次翻转使得最终的字符串变成交替字符串即相邻字符都不相同。求最少翻转次数。解题思路交替字符串的两种模式长度为n的交替字符串只有两种可能模式0以0开头偶数下标0,2,4,…为0奇数下标为1。模式1以1开头偶数下标为1奇数下标为0。对于任意一个固定的字符串我们可以统计偶数位置上0的个数和奇数位置上0的个数然后利用总数推导出与两种模式匹配所需翻转次数偶数位置总数 n - n/2向上取整奇数位置总数 n/2向下取整。与模式0匹配的翻转次数 (偶数位置总数 - 偶数位0的个数) 奇数位0的个数 (n - n/2 - even0) odd0。与模式1匹配的翻转次数 偶数位0的个数 (奇数位置总数 - 奇数位0的个数) even0 (n/2 - odd0)。取两者较小值即为当前字符串的最小翻转次数。旋转的影响旋转操作会使字符串的索引发生变化每旋转一次原第一个字符移到最后其余字符的索引减 1。这会导致原本在偶数位置的字符变成奇数位置反之亦然除了移到末尾的那个字符。因此如果我们能维护当前字符串中偶数位置和奇数位置上0的个数就可以通过模拟旋转过程计算出所有旋转情况下的最少翻转次数。核心算法先统计原始字符串中偶数下标和奇数下标上0的个数even0和odd0。初始化答案为n最大可能值。循环n次模拟每次旋转后的状态更新移除当前第一个字符原字符串的第i个字符它在当前字符串中位于下标 0。如果该字符是0则even0--因为下标 0 是偶数。剩余字符的索引全部减 1奇偶性互换交换odd0和even0。把刚才移除的字符放到末尾它现在位于下标n-1。如果该字符是0根据n-1的奇偶性增加对应的计数n-1为偶数则even0否则odd0。利用当前的even0和odd0计算两种模式的最小翻转次数更新答案。返回答案。代码实现CclassSolution{public:intminFlips(string s){intns.length();inteven00,odd00;// 原始字符串中偶数下标、奇数下标上 0 的个数for(inti0;in;i){if(s[i]0){if(i1)odd0;// 奇数下标elseeven0;// 偶数下标}}intansn;// 初始化答案为最大值 nfor(inti0;in;i){// 1. 移除第一个字符下标 0if(s[i]0)even0--;// 2. 剩余字符索引减1奇偶互换swap(odd0,even0);// 3. 把移出的字符放到末尾下标 n-1if(s[i]0){if((n-1)1)odd0;// n-1 为奇数elseeven0;// n-1 为偶数}// 计算当前旋转后的字符串所需最少翻转次数// 偶数位置总数 n - n/2奇数位置总数 n/2intflipsmin(even0n/2-odd0,odd0n-n/2-even0);ansmin(ans,flips);}returnans;// ans 一定非负直接返回}};复杂度分析时间复杂度O(n)只需一次遍历和一次循环没有额外嵌套。空间复杂度O(1)只使用了常数个变量。总结本题的关键在于理解旋转对字符奇偶位置的影响通过维护偶数位和奇数位上0的个数可以 O(n) 时间内求出所有旋转情况的最少翻转次数。这种模拟旋转并动态更新计数的方法避免了显式地旋转字符串非常高效。扩展如果题目要求输出最少翻转次数对应的具体旋转次数也可以在此算法基础上记录。