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

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

题目链接

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

题目描述

给你一个二进制字符串 s,你需要通过翻转尽可能少的字符,使得到的字符串成为交替二进制字符串。交替二进制字符串是指相邻两个字符永不相同的字符串(例如 "0101""1010")。

如果字符串的长度是偶数,则交替字符串的两种可能形式为 "0101...""1010...";如果长度是奇数,则两种形式可能在首尾字符相同(因为奇数长度的环形结构需要特殊处理)。

解法分析:滑动窗口(环形处理)

核心思路

该解法通过滑动窗口结合环形字符串处理,高效计算最少翻转次数。核心逻辑如下:

  1. 交替模式:二进制交替字符串有两种基础模式:

    • 模式A:"010101..."(偶数位为0,奇数位为1,下标从0开始)
    • 模式B:"101010..."(偶数位为1,奇数位为0)
    • 两种模式的翻转次数互补(模式B的翻转次数 = 字符串长度 - 模式A的翻转次数)。
  2. 环形处理:通过将字符串视为“环形”,用长度为 2n-1 的循环覆盖所有可能的窗口。

  3. 滑动窗口计算:用滑动窗口遍历所有可能的长度为 n 的子串(覆盖环形的所有起始位置),计算每个窗口对模式A的翻转次数,取最小值(及模式B的互补值)。

代码实现

class Solution:def minFlips(self, s: str) -> int:ans = n = len(s)  # ans:最小翻转次数;n:字符串长度cnt = l = 0       # cnt:当前窗口对模式A的翻转次数;l:窗口左指针# 遍历2n-1个位置(覆盖所有可能的环形窗口)for i in range(2 * n - 1):# 计算当前位置i(模n)对模式A的翻转次数:# 模式A要求i%2位置为i%2(0或1),若字符不等于i%2则需要翻转(加1)cnt += int(s[i % n]) != (i % 2)# 窗口未达到n长度时,继续累加if i + 1 < n:continue# 窗口达到n长度后,更新最小翻转次数:# 模式A的翻转次数为cnt,模式B为n - cnt,取两者最小值ans = min(ans, cnt, n - cnt)# 滑动窗口:移除左指针位置的翻转次数,左指针右移cnt -= int(s[l]) != (l % 2)l += 1return ans

代码解析

  1. 变量初始化

    • ans:初始化为 n(最大可能的翻转次数,即翻转所有字符)。
    • cnt:记录当前窗口对模式A的翻转次数(需要翻转的字符数)。
    • l:滑动窗口的左指针,初始为0。
  2. 环形窗口遍历

    • 循环 i02n-2(共 2n-1 次),通过 i % n 处理环形字符串的索引。
    • int(s[i % n]) != (i % 2):判断当前位置字符是否需要翻转以符合模式A(i%2 是模式A在该位置的目标值)。若需要翻转则 cnt += 1
  3. 窗口长度判断

    • i + 1 < n 时,窗口长度不足 n,继续累加翻转次数。
    • 当窗口长度达到 n 后(i + 1 >= n),开始计算当前窗口的最小翻转次数。
  4. 更新最小翻转次数

    • 对于当前窗口,模式A的翻转次数为 cnt,模式B的翻转次数为 n - cnt(互补关系)。
    • ans = min(ans, cnt, n - cnt):更新全局最小翻转次数。
  5. 滑动窗口维护

    • 移除左指针 l 位置对模式A的翻转次数(int(s[l]) != (l % 2))。
    • 左指针 l += 1,窗口整体右移,继续下一个窗口的计算。

关键逻辑说明

  • 环形覆盖:通过 2n-1 次遍历,覆盖了所有可能的起始位置(0n-1)的窗口,确保奇数长度字符串的跨边界情况被考虑。
  • 模式互补:利用 n - cnt 直接计算模式B的翻转次数,避免重复计算,提高效率。
  • 滑动窗口效率:每个位置仅被加入和移除窗口各一次,时间复杂度为 O(n),空间复杂度为 O(1)

示例详解

s = "01001001101"n=11,奇数)为例:

  • 模式A为 "01010101010",模式B为 "10101010101"
  • 遍历 i0202*11-1=21 次),每个窗口长度为11。
  • 对于窗口 i=10(覆盖 0-10),计算 cnt 为模式A的翻转次数,n - cnt 为模式B的翻转次数。
  • 对于跨边界窗口(如 i=15,覆盖 5-100-4),通过 i%11 处理环形索引,计算翻转次数。
  • 最终 ans 取所有窗口的最小翻转次数。

复杂度分析

  • 时间复杂度O(n),其中 n 是字符串长度。遍历 2n-1 个位置,每个位置的操作是 O(1)
  • 空间复杂度O(1),仅使用常数级额外空间。

总结

该解法通过滑动窗口高效处理了环形二进制字符串的交替翻转问题,核心优势在于:

  1. 环形覆盖:用 2n-1 次遍历覆盖所有可能的起始窗口,解决了奇数长度字符串的跨边界问题。
  2. 模式互补:利用两种模式的翻转次数互补性,减少一半计算量。
  3. 线性效率O(n) 时间复杂度,适用于大规模输入(n10^5)。

这是处理“环形字符串交替”问题的经典方法,结合了滑动窗口和模式互补的思想,是该问题的最优解法之一。

http://www.lryc.cn/news/589548.html

相关文章:

  • 整除分块练习题
  • 使用Spring Cloud LoadBalancer报错java.lang.IllegalStateException
  • AI助手指南:从零开始打造Python学习环境(VSCode + Lingma/Copilot + Anaconda + 效率工具包)
  • 学习秒杀系统-实现秒杀功能(商品列表,商品详情,基本秒杀功能实现,订单详情)
  • Sharding-JDBC 分布式事务实战指南:XA/Seata 方案解析(三)
  • 2HDMI/1DP转EDP/LVDS,支持4K,144HZ和240HZ.
  • LSA链路状态通告
  • 学习软件测试的第十六天
  • 项目进度跨地域团队协作困难,如何统一进度安排
  • 原来时间序列挖掘这么简单
  • 力扣73:矩阵置零
  • NW917NW921美光固态闪存NW946NW952
  • 游戏行业中的恶梦:不断升级的DDoS攻击
  • 【HarmonyOS】ArkUI-X 跨平台框架入门详解(一)
  • 3.正则化——新闻分类
  • 【stm32】新建工程
  • STM32裸机开发(中断,轮询,状态机)与freeRTOS
  • MyBatis与Spring整合优化实战指南:从配置到性能调优
  • Conda 核心命令快速查阅表
  • 系统编程是什么
  • 22-C#的委托简单使用-2
  • ai问答推荐企业排名优化?:五大企业核心竞争力全景对比
  • 从0开始学习R语言--Day47--Nomogram
  • 【51单片机先流水2秒后数码显示2秒后显示END】2022-9-5
  • 判断QMetaObject::invokeMethod()里的函数是否调用成功
  • 密码协议的基本概念
  • 【Linux手册】重定向是如何实现的?Linux下为什么一切皆文件?
  • 【env环境】rtthread5.1.0使用fal组件
  • npm install failed如何办?
  • 差分信号接口选型指南:深入解析LVDS、SubLVDS、SLVDS与SLVDS-EC**