2026-10-05：变换二进制字符串的最少操作次数。用 go 语言，给定两个长度都为 n、只包含字符 0 和 1 的字符串 a 和 b。

从字符串 a 开始，你可以按任意顺序反复执行下面两种改动，次数不限：

1. 如果某个位置当前是 0，可以把这一位单独变成 1。

2. 如果某两个相邻位置当前都是 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 ] 的值分情况处理 情况 A：s [ i ]

因为 s [ i ] 不等于 t [ i ] ，所以此时 t [ i ] 必然是 '1'。

也就是说，当前位置需要从 '0' 变成 '1'。

这时只能使用操作 1，把这一位的 '0' 单独改成 '1'。

因此操作次数 ans 加 1。

这一位处理完毕后，后续不再考虑它。

情况 B：s [ i ]

因为 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 = "01"，s2 = "10" 为例：

• 长度 n = 2，不是特殊情况。

• 初始化 s = [ '0', '1' ] ，ans = 0。

• 下标 i = 0：s [ 0 ] = '0'，t [ 0 ] = '1'，不相等。

因为 s [ 0 ] 是 '0'，所以执行情况 A，ans 加 1，变成 1。

逻辑上相当于把位置 0 从 '0' 变成了 '1'，字符串变为 "11"。

• 下标 i = 1：s [ 1 ] = '1'，t [ 1 ] = '0'，不相等。

因为 s [ 1 ] 是 '1'，且 i = 1 是最后一位，右边没有相邻位置，所以进入情况 B 的否则分支。

ans 加 2，变成 3。

• 遍历结束，返回 ans = 3。

对应的实际操作是：

1. 把下标 0 的 '0' 变成 '1'，"01" → "11"。

2. 把下标 0 和 1 的两个 '1' 同时变成 '0'，"11" → "00"。

3. 把下标 0 的 '0' 变成 '1'，"00" → "10"。

总共 3 次操作，与输出一致。

五、返回结果

遍历完所有位置后，返回累计的操作次数 ans。

如果一开始就遇到无法完成的情况（即 n == 1 且 s1 == "1"、t == "0"），则返回 -1。

六、复杂度分析

•时间复杂度：

算法只从左到右遍历字符串一次，每个位置的处理都是常数时间操作，因此总时间复杂度为O ( n ) ，其中 n 是字符串长度。

•额外空间复杂度：

在给出的 Go 代码中，创建了一个与 s1 等长的字节切片 s 来模拟修改，因此额外空间为O ( n ) 。

注释中提到也可以用布尔变量记录状态，从而做到 O ( 1 ) 额外空间，但就当前代码而言，额外空间复杂度是O ( n ) 。

Go 完整代码如下：

package main

import (

"fmt"

)

func minOperations ( s1, t string ) ( ans int ) {

n := len ( s1 )

if n == 1 && s1 == "1" && t == "0" {

return-1

}

// 也可以用一个布尔变量表示 s1 [ i ] 是否操作过，从而做到 O ( 1 ) 空间，见 Python3 写法二

s := [ ] byte ( s1 )

for i := range n {

if s [ i ] == t [ i ] {

continue

}

if s [ i ] == '0' {

ans++

} elseif i < n-1 && s [ i+1 ] == '1' {

ans++

s [ i+1 ] = '0'

} else {

ans += 2

}

}

return

}

func main ( ) {

s1 := "01"

s2 := "10"

result := minOperations ( s1, s2 )

fmt.Println ( result )

}

Python 完整代码如下：

# -*-coding:utf-8-*-

def minOperations ( s1, t ) :

n = len ( s1 )

if n == 1 and s1 == "1" and t == "0":

return-1

s = list ( s1 )

ans = 0

for i in range ( n ) :

if s [ i ] == t [ i ] :

continue

if s [ i ] == '0':

ans += 1

elif i < n - 1 and s [ i + 1 ] == '1':

ans += 1

s [ i + 1 ] = '0'

else:

ans += 2

return ans

def main ( ) :

s1 = "01"

s2 = "10"

result = minOperations ( s1, s2 )

print ( result )

if __name__ == "__main__":

main ( )

C++ 完整代码如下：

using namespace std;

int minOperations ( string s1, string t ) {

int n = s1.size ( ) ;

if ( n == 1 && s1 == "1" && t == "0" ) {

return-1;

}

string s = s1;

int ans = 0;

for ( int i = 0; i < n; ++i ) {

if ( s [ i ] == t [ i ] ) {

continue;

}

if ( s [ i ] == '0' ) {

++ans;

} elseif ( i < n - 1 && s [ i + 1 ] == '1' ) {

++ans;

s [ i + 1 ] = '0';

} else {

ans += 2;

}

}

return ans;

}

int main ( ) {

string s1 = "01";

string s2 = "10";

int result = minOperations ( s1, s2 ) ;

cout << result << endl;

return0;

}

我们相信人工智能为普通人提供了一种 " 增强工具 "，并致力于分享全方位的 AI 知识。在这里，您可以找到最新的 AI 科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注 " 福大大架构师每日一题 "，发消息可获得面试资料，让 AI 助力您的未来发展。