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

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

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

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

2. 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. 1. 把下标 0 的'0'变成'1'，"01"→"11"。

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

3. 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)。

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助力您的未来发展。