2026-05-14：使二进制字符串相等的最小成本。用go语言，给定两个长度为 n 的二进制字符串 s 和 t，以及三个正整数 flipCost、swa…

2026-05-14：使二进制字符串相等的最小成本。用go语言，给定两个长度为 n 的二进制字符串 s 和 t，以及三个正整数 flipCost、swapCost、crossCost。
你可以对 s、t 进行任意多次操作（操作顺序不限），目标是让最终的 s 与 t 完全相同。
允许的操作为：

1. 翻转操作：任选一个位置 i，把 s[i] 或 t[i] 的比特取反（0 变 1，1 变 0）。该操作花费 flipCost。

2. 同串交换：任选两个不同位置 i、j，将 s[i] 与 s[j 对调，或将 t[i] 与 t[j 对调。该操作花费 swapCost。

3. 跨串交换：任选一个位置 i，交换 s[i] 与 t[i]。该操作花费 crossCost。

求：使 s 与 t 相等所需的最小总成本。

n == s.length == t.length。

1 <= n <= 100000。

1 <= flipCost, swapCost, crossCost <= 1000000000。

s 和 t 仅由字符 ‘0’ 和 ‘1’ 组成。

输入: s = “01000”, t = “10111”, flipCost = 10, swapCost = 2, crossCost = 2。

输出: 16。

解释:

我们可以执行以下操作：

交换 s[0] 和 s[1]（swapCost = 2）。操作后，s = “10000”，t = “10111”。

交换 s[2] 和 t[2]（crossCost = 2）。操作后，s = “10100”，t = “10011”。

交换 s[2] 和 s[3]（swapCost = 2）。操作后，s = “10010”，t = “10011”。

翻转 s[4]（flipCost = 10）。操作后，s = t = “10011”。

总成本为 2 + 2 + 2 + 10 = 16。

题目来自力扣3800。

分步详细过程 第一步：统计核心问题类型（最关键的一步）

我们的目标是让s和t每一位都完全相同，首先要逐位对比两个字符串，统计所有不匹配的位置类型，这是所有计算的基础。

二进制字符只有0和1，两个字符串对位对比，只会出现4种情况：

1.s[i]=0，t[i]=0：完全匹配，无需处理

2.s[i]=1，t[i]=1：完全匹配，无需处理

3.s[i]=0，t[i]=1：定义为类型A不匹配（记总数量为a）

4.s[i]=1，t[i]=0：定义为类型B不匹配（记总数量为b）

代入输入示例统计

输入：s=01000，t=10111
逐位对比：
第0位：0 vs 1 → 类型A
第1位：1 vs 0 → 类型B
第2位：0 vs 1 → 类型A
第3位：0 vs 1 → 类型A
第4位：0 vs 1 → 类型A
最终统计结果：
a=4（4个0→1不匹配），b=1（1个1→0不匹配）
为了方便计算，我们统一让a ≤ b，调整后：a=1，b=4

第二步：明确三种核心修复方案（仅针对不匹配位）

所有不匹配的位置，只能通过翻转、同串交换、跨串交换三种操作修复。
代码中计算了三种最优的组合方案成本，最终取最小值就是答案。

方案1：纯翻转操作（最简单的暴力方案）

规则：对每一个不匹配的位置，单独执行翻转操作（改s或改t都可以），直到匹配。

• 总不匹配位数 = a + b

• 总成本 = (a + b) × 翻转成本

代入示例计算：
总不匹配位数=1+4=5，翻转成本=10
总成本=5×10=50

方案2：同串交换 + 剩余翻转

规则：

1.同串交换：只能修复数量相等的类型A和类型B不匹配（交换后直接让两组位置都匹配），最多能交换a次（因为a≤b）

2.剩余不匹配：交换后剩下的b-a个类型B不匹配，只能用翻转操作修复

• 交换成本 = a × 同串交换成本

• 翻转成本 = (b – a) × 翻转成本

• 总成本 = 交换成本 + 翻转成本

代入示例计算：
a=1，b=4，同串交换成本=2，翻转成本=10
交换成本=1×2=2
翻转成本=(4-1)×10=30
总成本=2+30=32

方案3：跨串交换 + 同串交换 + 剩余翻转（最优方案，示例答案来源）

规则：这是组合操作的最优解，利用跨串交换处理成对的不匹配，结合同串交换，最后处理剩余单个不匹配：

1. 总不匹配对数：total = a + b

2. 成对处理：用跨串交换+同串交换组合修复total/2对不匹配

3. 剩余单个：如果总数量是奇数，最后剩1个不匹配，用翻转修复

• 核心成本 = 成对数量×同串交换成本 + 差值×跨串交换成本

• 剩余成本 = 奇数个时×翻转成本

• 总成本 = 核心成本 + 剩余成本

代入示例计算：
total=5，成对数量=2，剩余1个；跨串成本=2，同串成本=2，翻转成本=10
核心成本=2×2 + (2-1)×2 = 4+2=6
剩余成本=1×10=10
总成本=6+10=16

第三步：选取最小成本

我们得到三种方案的成本：
方案1：50 → 方案2：32 → 方案3：16
最终最小成本=16，和题目示例输出完全一致。

补充：三种操作的作用理解（辅助理解）

1.翻转操作：万能操作，单个位置修复，成本固定

2.同串交换：批量修复一对不同类型的不匹配，比两次翻转更便宜

3.跨串交换：对位交换s和t的字符，配合交换能高效处理批量不匹配

时间复杂度 & 额外空间复杂度 1. 时间复杂度

• 核心操作：逐位遍历一次字符串，统计不匹配类型，遍历长度为n

• 后续计算：都是固定次数的数学运算（常数时间）

• 总时间复杂度：O(n)
（线性时间，处理10万长度的字符串也能高效运行）

2. 额外空间复杂度

• 仅使用了固定大小的变量：统计用的2×2数组、a/b/res1/res2/res3等变量

• 无论输入字符串长度n是多少，占用的额外空间都不会变化

• 总额外空间复杂度：O(1)
（常数空间，几乎不占用额外内存）

总结

1. 核心流程：统计不匹配类型 → 计算三种操作组合成本 → 取最小值

2. 示例中通过「交换+跨串交换+翻转」的组合得到最低成本16

3. 时间复杂度O(n)，空间复杂度O(1)，完美适配题目最大数据规模

Go完整代码如下：

package main

 import (
    "fmt"
)

 func minimumCost(s, t string, flipCost, swapCost, crossCost int)int64 {
    cnt := [2][2]int{}
    for i, ch := range s {
        cnt[ch&1][t[i]&1]++
    }

     a := cnt[0][1]
    b := cnt[1][0]
    if a > b {
        a, b = b, a
    }

     res1 := (a + b) * flipCost
    res2 := a*swapCost + (b-a)*flipCost
    avg := (a + b) / 2
    res3 := (avg-a)*crossCost + avg*swapCost + (a+b)%2*flipCost
    returnint64(min(res1, res2, res3))
}

 func main() {
    s := "01000"
    t := "10111"
    flipCost := 10
    swapCost := 2
    crossCost := 2
    result := minimumCost(s, t, flipCost, swapCost, crossCost)
    fmt.Println(result)
}

Python完整代码如下：

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

 def minimumCost(s: str, t: str, flipCost: int, swapCost: int, crossCost: int) -> int:
    cnt = [[0, 0], [0, 0]]
    for sc, tc in zip(s, t):
        cnt[ord(sc) & 1][ord(tc) & 1] += 1

     a = cnt[0][1]
    b = cnt[1][0]
    if a > b:
        a, b = b, a

     res1 = (a + b) * flipCost
    res2 = a * swapCost + (b - a) * flipCost
    avg = (a + b) // 2
    res3 = (avg - a) * crossCost + avg * swapCost + (a + b) % 2 * flipCost
    return min(res1, res2, res3)

 if __name__ == "__main__":
    s = "01000"
    t = "10111"
    flipCost = 10
    swapCost = 2
    crossCost = 2
    result = minimumCost(s, t, flipCost, swapCost, crossCost)
    print(result)

C++完整代码如下：

  

   


 using namespace std;

 long long minimumCost(string s, string t, int flipCost, int swapCost, int crossCost) {
    int cnt[2][2] = {{0, 0}, {0, 0}};
    for (size_t i = 0; i < s.length(); i++) {
        cnt[s[i] & 1][t[i] & 1]++;
    }

     int a = cnt[0][1];
    int b = cnt[1][0];
    if (a > b) {
        swap(a, b);
    }

     long long res1 = (a + b) * flipCost;
    long long res2 = a * swapCost + (b - a) * flipCost;
    int avg = (a + b) / 2;
    long long res3 = (avg - a) * crossCost + avg * swapCost + (a + b) % 2 * flipCost;
    return min({res1, res2, res3});
}

 int main() {
    string s = "01000";
    string t = "10111";
    int flipCost = 10;
    int swapCost = 2;
    int crossCost = 2;
    long long result = minimumCost(s, t, flipCost, swapCost, crossCost);
    cout << result << endl;
    return0;
}

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