博亚体育 2026-05-14: 使二进制字符串荒谬的最小本钱。用go谈话, 给定两个
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
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）
赛车pk10官网平台首页代入输入示例统计
输入：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++完整代码如下：
#include
#include
#include
#include
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
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
return0;
}
咱们确信东说念主工智能为平庸东说念主提供了一种“增强器具”，并发奋于共享全主意的AI学问。在这里，您不错找到最新的AI科普著述、器具评测、栽培后果的隐秘以及行业洞悉。
宽饶关怀“福大大架构师逐日一题”博亚体育，发音尘可取得口试贵寓，让AI助力您的夙昔发展。