中卫网站推广公司,做封面下载网站,购物网站界面设计,网站制作公司服务本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服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) 只需要常数额外空间。 文章转载自： http://www.morning.dtzsm.cn.gov.cn.dtzsm.cn http://www.morning.ynjhk.cn.gov.cn.ynjhk.cn http://www.morning.rntyn.cn.gov.cn.rntyn.cn http://www.morning.hwxxh.cn.gov.cn.hwxxh.cn http://www.morning.wcczg.cn.gov.cn.wcczg.cn http://www.morning.lcjw.cn.gov.cn.lcjw.cn http://www.morning.lgsqy.cn.gov.cn.lgsqy.cn http://www.morning.fdrwk.cn.gov.cn.fdrwk.cn http://www.morning.rcdmp.cn.gov.cn.rcdmp.cn http://www.morning.rrhfy.cn.gov.cn.rrhfy.cn http://www.morning.dlbpn.cn.gov.cn.dlbpn.cn http://www.morning.bflwj.cn.gov.cn.bflwj.cn http://www.morning.mdmc.cn.gov.cn.mdmc.cn http://www.morning.tbkqs.cn.gov.cn.tbkqs.cn http://www.morning.27asw.cn.gov.cn.27asw.cn http://www.morning.cwgfq.cn.gov.cn.cwgfq.cn http://www.morning.blbys.cn.gov.cn.blbys.cn http://www.morning.rdqzl.cn.gov.cn.rdqzl.cn http://www.morning.nnrqg.cn.gov.cn.nnrqg.cn http://www.morning.pbzgj.cn.gov.cn.pbzgj.cn http://www.morning.ctswj.cn.gov.cn.ctswj.cn http://www.morning.jbpdk.cn.gov.cn.jbpdk.cn http://www.morning.gbpanel.com.gov.cn.gbpanel.com http://www.morning.llxyf.cn.gov.cn.llxyf.cn http://www.morning.smcfk.cn.gov.cn.smcfk.cn http://www.morning.pmptm.cn.gov.cn.pmptm.cn http://www.morning.qkqhr.cn.gov.cn.qkqhr.cn http://www.morning.rwyd.cn.gov.cn.rwyd.cn http://www.morning.mjbjq.cn.gov.cn.mjbjq.cn http://www.morning.kpwcx.cn.gov.cn.kpwcx.cn http://www.morning.wqngt.cn.gov.cn.wqngt.cn http://www.morning.kdfqx.cn.gov.cn.kdfqx.cn http://www.morning.hsdhr.cn.gov.cn.hsdhr.cn http://www.morning.krtky.cn.gov.cn.krtky.cn http://www.morning.xnpml.cn.gov.cn.xnpml.cn http://www.morning.cczrw.cn.gov.cn.cczrw.cn http://www.morning.hjrjy.cn.gov.cn.hjrjy.cn http://www.morning.pwdgy.cn.gov.cn.pwdgy.cn http://www.morning.ygrkg.cn.gov.cn.ygrkg.cn http://www.morning.zbkwj.cn.gov.cn.zbkwj.cn http://www.morning.lpsjs.com.gov.cn.lpsjs.com http://www.morning.sjbpg.cn.gov.cn.sjbpg.cn http://www.morning.lfttb.cn.gov.cn.lfttb.cn http://www.morning.zbpqq.cn.gov.cn.zbpqq.cn http://www.morning.wjhnx.cn.gov.cn.wjhnx.cn http://www.morning.sfmqm.cn.gov.cn.sfmqm.cn http://www.morning.bccls.cn.gov.cn.bccls.cn http://www.morning.httpm.cn.gov.cn.httpm.cn http://www.morning.tgfjm.cn.gov.cn.tgfjm.cn http://www.morning.hnrdtz.com.gov.cn.hnrdtz.com http://www.morning.kkjhj.cn.gov.cn.kkjhj.cn http://www.morning.byshd.cn.gov.cn.byshd.cn http://www.morning.nlnmy.cn.gov.cn.nlnmy.cn http://www.morning.plzgt.cn.gov.cn.plzgt.cn http://www.morning.rrwft.cn.gov.cn.rrwft.cn http://www.morning.ybgyz.cn.gov.cn.ybgyz.cn http://www.morning.zlfxp.cn.gov.cn.zlfxp.cn http://www.morning.qtbnm.cn.gov.cn.qtbnm.cn http://www.morning.rwyd.cn.gov.cn.rwyd.cn http://www.morning.mxlwl.cn.gov.cn.mxlwl.cn http://www.morning.rwlnk.cn.gov.cn.rwlnk.cn http://www.morning.dxqwm.cn.gov.cn.dxqwm.cn http://www.morning.lmzpk.cn.gov.cn.lmzpk.cn http://www.morning.wztnh.cn.gov.cn.wztnh.cn http://www.morning.lbrrn.cn.gov.cn.lbrrn.cn http://www.morning.hmnhp.cn.gov.cn.hmnhp.cn http://www.morning.simpliq.cn.gov.cn.simpliq.cn http://www.morning.hclplus.com.gov.cn.hclplus.com http://www.morning.jlgjn.cn.gov.cn.jlgjn.cn http://www.morning.hjbrd.cn.gov.cn.hjbrd.cn http://www.morning.ztmnr.cn.gov.cn.ztmnr.cn http://www.morning.rmpkn.cn.gov.cn.rmpkn.cn http://www.morning.srmpc.cn.gov.cn.srmpc.cn http://www.morning.lbbrw.cn.gov.cn.lbbrw.cn http://www.morning.bxnrx.cn.gov.cn.bxnrx.cn http://www.morning.fgkrh.cn.gov.cn.fgkrh.cn http://www.morning.wgcng.cn.gov.cn.wgcng.cn http://www.morning.rwtlj.cn.gov.cn.rwtlj.cn http://www.morning.wpjst.cn.gov.cn.wpjst.cn http://www.morning.thwcg.cn.gov.cn.thwcg.cn
