LeetCode 1758. 生成交替二进制字符串的最少操作数【字符串,模拟】1353
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。
为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。
由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。
给你一个仅由字符 '0' 和 '1' 组成的字符串 s 。一步操作中,你可以将任一 '0' 变成 '1' ,或者将 '1' 变成 '0' 。
交替字符串 定义为:如果字符串中不存在相邻两个字符相等的情况,那么该字符串就是交替字符串。例如,字符串 "010" 是交替字符串,而字符串 "0100" 不是。
返回使 s 变成 交替字符串 所需的 最少 操作数。
示例 1:
输入:s = "0100"
输出:1
解释:如果将最后一个字符变为 '1' ,s 就变成 "0101" ,即符合交替字符串定义。
示例 2:
输入:s = "10"
输出:0
解释:s 已经是交替字符串。
示例 3:
输入:s = "1111"
输出:2
解释:需要 2 步操作得到 "0101" 或 "1010" 。
提示:
1 <= s.length <= 10^4s[i]是'0'或'1'
解法 模拟
根据题意,经过多次操作, s s s 可能会变成两种不同的交替二进制字符串,即:
- 开头为 0 0 0 ,后续交替的字符串;
- 开头为 1 1 1 ,后续交替的字符串。
注意到,变成这两种不同的交替二进制字符串所需要的最少操作数加起来等于 s s s 的长度,我们只需要计算出变为其中一种字符串的最少操作数,就可以推出另一个最少操作数,然后取最小值即可。
// cpp
class Solution {
public:int minOperations(string s) {int cnt = 0;for (int i = 0; i < s.size(); ++i) {char c = s[i];if (c != ('0' + i % 2)) ++cnt;}return min(cnt, (int)s.size() - cnt);}
};// java
class Solution {public int minOperations(String s) {int cnt = 0;for (int i = 0; i < s.length(); ++i) {char c = s.charAt(i);if (c != (char)('0' + i % 2)) ++cnt;}return Math.min(cnt, s.length() - cnt);}
}// python
class Solution:def minOperations(self, s: str) -> int:cnt = sum(int(c) != i % 2 for i, c in enumerate(s)) # 010101...return min(cnt, len(s) - cnt)// go
func minOperations(s string) int {cnt := 0for i, c := range s {if i % 2 != int(c - '0') {cnt++}}return min(cnt, len(s) - cnt)
}
func min(a, b int) int {if a > b {return b}return a
}
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n) ,其中 n n n 为输入 s s s 的长度,仅需遍历一遍字符串。
- 空间复杂度: O ( 1 ) O(1) O(1) ,只需要常数额外空间。
相关文章:
LeetCode 1758. 生成交替二进制字符串的最少操作数【字符串,模拟】1353
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...
Spring-IOC-xml方式
简介 **控制反转**(Inversion of Control,缩写为**IoC**),是[面向对象编程]中的一种设计原则,可以用来减低计算机[代码]之间的[耦合度]。其中最常见的方式叫做[依赖注入]Dependency Injection,简称DI&#…...
HUAWEI华为荣耀MagicBook X 15酷睿i5-10210U处理器集显(BBR-WAH9)笔记本电脑原装出厂Windows10系统
链接:https://pan.baidu.com/s/1YVcnOP5YKfFOoLt0z706rg?pwdfwp0 提取码:fwp0 MagicBook荣耀原厂Win10系统自带所有驱动、出厂主题壁纸、系统属性专属LOGO标志、Office办公软件、华为/荣耀电脑管家等预装程序 文件格式:esd/wim/swm 安装…...
React使用动态标签名称
最近在一项目里(React antd)遇到一个需求,某项基础信息里有个图标配置(图标用的是antd的Icon组件),该项基础信息的图标信息修改后,存于后台数据库,后台数据库里存的是antd Icon组件…...
Java异常篇----第二篇
系列文章目录 文章目录 系列文章目录前言一、 Excption与Error包结构二、Thow与thorws区别三、Error与Exception区别?四、error和exception有什么区别前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女…...
微服务(1)
目录 1.什么是微服务?谈谈你对微服务的理解? 2.什么是Spring Cloud? 3.Springcloud中的组件有哪些? 3.具体说说SpringCloud主要项目? 5.SpringCloud项目部署架构? 1.什么是微服务?谈谈你对微…...
195.【2023年华为OD机试真题(C卷)】5G 网络建设(最小生成树—JavaPythonC++JS实现)
请到本专栏顶置查阅最新的华为OD机试宝典 点击跳转到本专栏-算法之翼:华为OD机试 🚀你的旅程将在这里启航!本专栏所有题目均包含优质解题思路,高质量解题代码,详细代码讲解,助你深入学习,深度掌握! 文章目录 【2023年华为OD机试真题(C卷)】5G 网络建设(最小生…...
2024年1月1日答案
a)i. V B B V C C 16 V V_{BB} V_{CC} 16V VBBVCC16V R t h R B R E R B R E 10 k Ω 3 k Ω 10 k Ω 3 k Ω ≈ 2.31 k Ω R_{th} \frac{R_B \times R_E}{R_B R_E} \frac{10k\Omega \times 3k\Omega}{10k\Omega 3k\Omega} \approx 2.31k\Omega RthRBR…...
【算法】dp题单
题单链接: https://vjudge.net/contest/574209#overview 目录 1. 洛谷 P1020 导弹拦截 (dp二分Dilworth 定理) 2. P1439 最长公共子序列(二分求最长公共子序列) 3. 洛谷 P1854 花店橱窗布置 (线性dp 用…...
Verilog视频信号图形显示 FPGA(iCE40)
您需要一块带视频输出的 FPGA 板。 我们将在 640x480 下工作,几乎任何视频输出都可以在此像素工作。 它有助于轻松地对 FPGA 板进行编程并相当熟悉 Verilog。 如果您没有开发板,请不要担心,您可以使用 Verilator 模拟器。 材料 Lattice iCE…...
【LeetCode 面试经典150题】26. Remove Duplicates from Sorted Array 在有序数组中移除重复元素
26. Remove Duplicates from Sorted Array 题目大意 Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then …...
linux系统下sql脚本的执行与导出
terminal中执行 执行 mysql -u [username] -p -D [databasename] < [XXX.sql] 导出 mysql -u [username] -p [datbasename] > [XXX.sql] 导出的数据库名自定义。 mysql -u [username] -p [databasename] [tablename] > [xxx.sql] 导出表名自定义 mysql shell 执行 …...
MyBatis学习一:快速入门
前言 公司要求没办法,前端也要了解一下后端知识,这里记录一下自己的学习 学习教程:黑马mybatis教程全套视频教程,2天Mybatis框架从入门到精通 文档: https://mybatis.net.cn/index.html MyBatis 快速入门…...
零售业物流这个防漏水技术,居然没有翻车!
随着科技的不断发展,水浸监控系统在各个领域得到了广泛应用。水浸监控不仅仅是为了保护建筑结构和设备,更是为了防范因水灾引起的生命安全和财产损失。 因此,为了有效预防和应对水浸事件,水浸监控系统应运而生,成为各行…...
主浏览器优化之路1——你现在在用的是什么浏览器?Edge?谷歌?火狐?360!?
上一世,我的浏览器之路 引言为什么要用两个浏览器为什么一定要放弃火狐结尾给大家一个猜数字小游戏(测运气) 引言 小时候,我一开始上网的浏览器是2345王牌浏览器吧, 因为上面集成了很多网站,我记得上面有7…...
gitlab请求合并分支
直接去看原文: 原文链接:Gitlab合并请求相关流程_source branch target branch-CSDN博客 --------------------------------------------------------------------------------------------------------------------------------- 入口: 仓库控制台的这两个地方都…...
使用Vue3开发学生管理系统模板1
环境搭建 通过解压之前《Vue3开发后台管理系统模板》的代码,我们能够得到用户增删改查的页面,我们基于用户增删改查的页面做进一步的优化。 创建学生增删改查页面 第一步:复制用户增删改查页面,重命名为StudentCRUD.vue <…...
【cmake实战:番外】交叉编译——Linaro
【cmake实战:番外】交叉编译——Linaro 一、交叉编译1、交叉编译简介2、为什么会有交叉编译 二、交叉编译链1、什么是交叉编译链2、交叉编译工具 三、Linaro1、下载2、解压3、demo3.1、toolchain_aarch64.cmake3.2、CMakeLists.txt3.3、main.cpp 4、执行编译5、查看…...
2024年年初Java5年实战面试题(北京)
高阶篇: 一、在面对千万条并发请求的情况下,如果数据库频繁查询导致崩溃,可以采取以下措施来解决问题: 1.缓存数据:可以使用缓存技术来减少对数据库的查询次数。将经常查询的数据存储在缓存中,例如使用Redis等内存数据库ÿ…...
【Apache-2.0】springboot-openai-chatgpt超级AI大脑产品架构图
springboot-openai-chatgpt: 一个基于SpringCloud的Chatgpt机器人,已对接GPT-3.5、GPT-4.0、百度文心一言、stable diffusion AI绘图、Midjourney绘图。用户可以在界面上与聊天机器人进行对话,聊天机器人会根据用户的输入自动生成回复。同时也支持画图&a…...
高频测试接口弹性插座技术解析与应用
1. 高频测试接口的革命性解决方案 在射频和毫米波器件测试领域,连接器性能往往成为整个系统的瓶颈。传统弹簧探针式测试插座在GHz频段会面临严重的信号完整性问题,而焊接式方案又缺乏必要的灵活性。Ironwood Electronics推出的SG-MLF-7078弹性插座&#…...
如何快速解密RPG Maker加密文件:新手必看的完整解密指南
如何快速解密RPG Maker加密文件:新手必看的完整解密指南 【免费下载链接】RPGMakerDecrypter Tool for decrypting and extracting RPG Maker XP, VX and VX Ace encrypted archives and MV and MZ encrypted files. 项目地址: https://gitcode.com/gh_mirrors/rp…...
LlamaGen:自回归模型在图像生成领域挑战扩散模型
1. 项目概述:当Llama遇见图像生成最近在图像生成领域,一个名为LlamaGen的项目引起了我的注意。它提出了一个非常大胆且反直觉的观点:纯自回归模型(AR)在图像生成任务上,可以超越当前如日中天的扩散模型&…...
深入Android系统源码:screencap命令背后,SurfaceFlinger如何“画”出一张图?
深入Android系统源码:screencap命令背后,SurfaceFlinger如何“画”出一张图? 当我们轻敲adb shell screencap -p /sdcard/screenshot.png命令时,手机屏幕上瞬间闪现的内容便被永久定格。这个看似简单的操作背后,却隐藏…...
C# —— 结构体、类型转换与运算符
一、结构体(struct)与常量(const)结构体用于打包多个相关变量,常量用于定义不可修改的值,是规范数据的常用方式。1. 结构体(struct)作用:把多个变量打包成一个整体&#…...
微机原理课设别头疼!手把手教你用8255和8253芯片搞定电子琴仿真(附Proteus工程和汇编源码)
微机原理课设实战:82558253芯片构建电子琴仿真系统全解析 记得第一次拿到微机原理课设题目时,面对一堆芯片型号和汇编指令,我整个人都是懵的。作为过来人,我完全理解你现在可能面临的困惑——如何把抽象的芯片功能转化为实际可运行…...
3大核心优势:Detect It Easy 如何成为文件类型识别的终极工具
3大核心优势:Detect It Easy 如何成为文件类型识别的终极工具 【免费下载链接】Detect-It-Easy Program for determining types of files for Windows, Linux and MacOS. 项目地址: https://gitcode.com/gh_mirrors/de/Detect-It-Easy 想象一下,你…...
MyScaleDB:基于SQL的向量数据库实战,实现混合查询与AI应用开发
1. 项目概述:当向量数据库遇见SQL如果你最近在折腾大模型应用,尤其是想给AI应用加上“长期记忆”或者实现精准的文档问答,那你大概率已经听过“向量数据库”这个词。从早期的Milvus、Pinecone,到后来各大云厂商纷纷入局࿰…...
DS4Windows完全指南:让你的PS4手柄在Windows上大放异彩 [特殊字符]
DS4Windows完全指南:让你的PS4手柄在Windows上大放异彩 🎮 【免费下载链接】DS4Windows Like those other ds4tools, but sexier 项目地址: https://gitcode.com/gh_mirrors/ds/DS4Windows 还在为PC游戏不支持PS4手柄而烦恼吗?想要在W…...
开发者知识管理工具CodingIT:架构设计与应用实践
1. 项目概述:一个面向开发者的“一站式”知识管理工具最近在整理个人技术笔记和项目文档时,我发现自己陷入了典型的“信息碎片化”困境:代码片段散落在Gist、笔记软件、本地文件甚至聊天记录里;项目文档要么是简陋的README&#x…...
