2026-10-05变换二进制字符串的最少操作次数。用go语言给定两个长度都为 n、只包含字符 0 和 1 的字符串 a 和 b。从字符串 a 开始你可以按任意顺序反复执行下面两种改动次数不限如果某个位置当前是 0可以把这一位单独变成 1。如果某两个相邻位置当前都是 1可以把这两位同时变成 0。问最少经过多少次改动才能让 a 变得和 b 完全一样如果无论怎样都做不到就返回 -1。1 n s1.length s2.length 100000。s1 和 s2 仅由 ‘0’ 和 ‘1’ 组成。输入 s1 “01”, s2 “10”。输出 3。解释将下标 0 从 ‘0’ 更改为 ‘1’ 这样 “01” 就变成了 “11” 。将下标 0 和 1 从 ‘1’ 更改为 ‘0’ 这样 “11” 就变成了 “00” 。将下标 0 从 ‘0’ 更改为 ‘1’ 这样 “00” 就变成了 “10” 。因此答案为 3 。题目来自力扣3980。一、特殊情况处理首先判断字符串长度n是否为 1。如果n 1并且初始字符串s1是1目标字符串t是0那么直接返回-1。原因是单个字符1无法通过任何一种操作变成0。操作 1 只能把0变成1操作 2 需要两个相邻的1才能同时变成0而长度为 1 时没有相邻位置因此无法消除这个单独的1。二、初始化如果通过了特殊情况判断就把初始字符串s1转成一个可修改的字符序列例如字节切片或列表记为s用来模拟当前字符串状态。同时设置一个变量ans记录操作次数初始为 0。三、从左到右遍历每一位接下来从下标i 0开始一直遍历到n - 1。对于每个位置i比较当前字符s[i]和目标字符t[i]。1. 如果s[i]已经等于t[i]说明这一位已经符合目标要求不需要任何操作直接跳过继续检查下一位。2. 如果s[i]不等于t[i]则根据s[i]的值分情况处理情况 As[i]是0因为s[i]不等于t[i]所以此时t[i]必然是1。也就是说当前位置需要从0变成1。这时只能使用操作 1把这一位的0单独改成1。因此操作次数ans加 1。这一位处理完毕后后续不再考虑它。情况 Bs[i]是1因为s[i]不等于t[i]所以此时t[i]必然是0。也就是说当前位置需要从1变成0。这时要尽量利用操作 2即把相邻的两个1同时变成0。于是检查右边相邻位置i 1如果i不是最后一位并且s[i 1]当前是1可以执行一次操作 2把i和i 1这两个相邻的1同时变成0。操作次数ans加 1。同时因为i 1位置也被变成了0所以要把s[i 1]标记为0这样后续扫描到i 1时会根据新的状态继续处理。否则右边不是1或者i已经是最后一位无法直接找到相邻的1来配对。这时需要消耗 2 次操作来消除这个孤立的1。具体做法是先花 1 次操作把右边某个0变成1然后再花 1 次操作把这两个1一起变成0。总共消耗 2 次操作因此ans加 2。在这种情况下不需要修改s[i 1]因为那个位置最终会恢复成原来的状态先变成1再变回0。四、举例说明以题目给出的例子s1 01s2 10为例长度n 2不是特殊情况。初始化s [0, 1]ans 0。下标i 0s[0] 0t[0] 1不相等。因为s[0]是0所以执行情况 Aans加 1变成 1。逻辑上相当于把位置 0 从0变成了1字符串变为11。下标i 1s[1] 1t[1] 0不相等。因为s[1]是1且i 1是最后一位右边没有相邻位置所以进入情况 B 的否则分支。ans加 2变成 3。遍历结束返回ans 3。对应的实际操作是把下标 0 的0变成101→11。把下标 0 和 1 的两个1同时变成011→00。把下标 0 的0变成100→10。总共 3 次操作与输出一致。五、返回结果遍历完所有位置后返回累计的操作次数ans。如果一开始就遇到无法完成的情况即n 1且s1 1、t 0则返回-1。六、复杂度分析时间复杂度算法只从左到右遍历字符串一次每个位置的处理都是常数时间操作因此总时间复杂度为O(n)其中n是字符串长度。额外空间复杂度在给出的 Go 代码中创建了一个与s1等长的字节切片s来模拟修改因此额外空间为O(n)。注释中提到也可以用布尔变量记录状态从而做到 O(1) 额外空间但就当前代码而言额外空间复杂度是O(n)。Go完整代码如下packagemainimport(fmt)funcminOperations(s1,tstring)(ansint){n:len(s1)ifn1s11t0{return-1}// 也可以用一个布尔变量表示 s1[i] 是否操作过从而做到 O(1) 空间见 Python3 写法二s:[]byte(s1)fori:rangen{ifs[i]t[i]{continue}ifs[i]0{ans}elseifin-1s[i1]1{anss[i1]0}else{ans2}}return}funcmain(){s1:01s2:10result:minOperations(s1,s2)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defminOperations(s1,t):nlen(s1)ifn1ands11andt0:return-1slist(s1)ans0foriinrange(n):ifs[i]t[i]:continueifs[i]0:ans1elifin-1ands[i1]1:ans1s[i1]0else:ans2returnansdefmain():s101s210resultminOperations(s1,s2)print(result)if__name____main__:main()C完整代码如下#includeiostream#includestringusingnamespacestd;intminOperations(string s1,string t){intns1.size();if(n1s11t0){return-1;}string ss1;intans0;for(inti0;in;i){if(s[i]t[i]){continue;}if(s[i]0){ans;}elseif(in-1s[i1]1){ans;s[i1]0;}else{ans2;}}returnans;}intmain(){string s101;string s210;intresultminOperations(s1,s2);coutresultendl;return0;}