当前位置：首页 > news >正文

LeetCode 1888 使二进制字符串交替的最少翻转次数

news 2026/5/12 2:33:23

LeetCode 1888 使二进制字符串交替的最少翻转次数

题目描述

给你一个二进制字符串s，你可以进行两种操作：

翻转任意一个字符（0 变 1，1 变 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计算两种模式的最小翻转次数，更新答案。
返回答案。

代码实现（C++）

classSolution{public:intminFlips(string s){intn=s.length();inteven0=0,odd0=0;// 原始字符串中偶数下标、奇数下标上 '0' 的个数for(inti=0;i<n;++i){if(s[i]=='0'){if(i&1)odd0++;// 奇数下标elseeven0++;// 偶数下标}}intans=n;// 初始化答案为最大值 nfor(inti=0;i<n;++i){// 1. 移除第一个字符（下标 0）if(s[i]=='0')even0--;// 2. 剩余字符索引减1，奇偶互换swap(odd0,even0);// 3. 把移出的字符放到末尾（下标 n-1）if(s[i]=='0'){if((n-1)&1)odd0++;// n-1 为奇数elseeven0++;// n-1 为偶数}// 计算当前旋转后的字符串所需最少翻转次数// 偶数位置总数 = n - n/2，奇数位置总数 = n/2intflips=min(even0+n/2-odd0,odd0+n-n/2-even0);ans=min(ans,flips);}returnans;// ans 一定非负，直接返回}};