2026-05-14：使二進(jìn)制字符串相等的最小成本。用go語言，給定兩個長度為 n 的二進(jìn)制字符串 s 和 t，以及三個正整數(shù) flipCost、swa...

2026-05-14 00:10:55　來源: moonfdd

北京舉報

分享至

2026-05-14：使二進(jìn)制字符串相等的最小成本。用go語言，給定兩個長度為 n 的二進(jìn)制字符串 s 和 t，以及三個正整數(shù) flipCost、swapCost、crossCost。
你可以對 s、t 進(jìn)行任意多次操作（操作順序不限），目標(biāo)是讓最終的 s 與 t 完全相同。
允許的操作為：

1. 翻轉(zhuǎn)操作：任選一個位置 i，把 s[i] 或 t[i] 的比特取反（0 變 1，1 變 0）。該操作花費 flipCost。
2. 同串交換：任選兩個不同位置 i、j，將 s[i] 與 s[j 對調(diào)，或?qū)?t[i] 與 t[j 對調(diào)。該操作花費 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。

解釋:

我們可以執(zhí)行以下操作：

交換 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"。

翻轉(zhuǎn) s[4]（flipCost = 10）。操作后，s = t = "10011"。

總成本為 2 + 2 + 2 + 10 = 16。

題目來自力扣3800。

分步詳細(xì)過程第一步：統(tǒng)計核心問題類型（最關(guān)鍵的一步）

我們的目標(biāo)是讓s和t每一位都完全相同，首先要逐位對比兩個字符串，統(tǒng)計所有不匹配的位置類型，這是所有計算的基礎(chǔ)。

二進(jìn)制字符只有0和1，兩個字符串對位對比，只會出現(xiàn)4種情況：

1.s[i]=0，t[i]=0：完全匹配，無需處理
2.s[i]=1，t[i]=1：完全匹配，無需處理
3.s[i]=0，t[i]=1：定義為類型A不匹配（記總數(shù)量為a）
4.s[i]=1，t[i]=0：定義為類型B不匹配（記總數(shù)量為b）

代入輸入示例統(tǒng)計

輸入：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
最終統(tǒng)計結(jié)果：
a=4（4個0→1不匹配），b=1（1個1→0不匹配）
為了方便計算，我們統(tǒng)一讓a ≤ b，調(diào)整后：a=1，b=4

第二步：明確三種核心修復(fù)方案（僅針對不匹配位）

所有不匹配的位置，只能通過翻轉(zhuǎn)、同串交換、跨串交換三種操作修復(fù)。
代碼中計算了三種最優(yōu)的組合方案成本，最終取最小值就是答案。

方案1：純翻轉(zhuǎn)操作（最簡單的暴力方案）

規(guī)則：對每一個不匹配的位置，單獨執(zhí)行翻轉(zhuǎn)操作（改s或改t都可以），直到匹配。

? 總不匹配位數(shù) = a + b
? 總成本 = (a + b) × 翻轉(zhuǎn)成本

代入示例計算：
總不匹配位數(shù)=1+4=5，翻轉(zhuǎn)成本=10
總成本=5×10=50

方案2：同串交換 + 剩余翻轉(zhuǎn)

規(guī)則：

1.同串交換：只能修復(fù)數(shù)量相等的類型A和類型B不匹配（交換后直接讓兩組位置都匹配），最多能交換a次（因為a≤b）
2.剩余不匹配：交換后剩下的b-a個類型B不匹配，只能用翻轉(zhuǎn)操作修復(fù)

? 交換成本 = a × 同串交換成本
? 翻轉(zhuǎn)成本 = (b - a) × 翻轉(zhuǎn)成本
? 總成本 = 交換成本 + 翻轉(zhuǎn)成本

代入示例計算：
a=1，b=4，同串交換成本=2，翻轉(zhuǎn)成本=10
交換成本=1×2=2
翻轉(zhuǎn)成本=(4-1)×10=30
總成本=2+30=32

方案3：跨串交換 + 同串交換 + 剩余翻轉(zhuǎn)（最優(yōu)方案，示例答案來源）

規(guī)則：這是組合操作的最優(yōu)解，利用跨串交換處理成對的不匹配，結(jié)合同串交換，最后處理剩余單個不匹配：

1. 總不匹配對數(shù)：total = a + b
2. 成對處理：用跨串交換+同串交換組合修復(fù)total/2對不匹配
3. 剩余單個：如果總數(shù)量是奇數(shù)，最后剩1個不匹配，用翻轉(zhuǎn)修復(fù)

? 核心成本 = 成對數(shù)量×同串交換成本 + 差值×跨串交換成本
? 剩余成本 = 奇數(shù)個時×翻轉(zhuǎn)成本
? 總成本 = 核心成本 + 剩余成本

代入示例計算：
total=5，成對數(shù)量=2，剩余1個；跨串成本=2，同串成本=2，翻轉(zhuǎn)成本=10
核心成本=2×2 + (2-1)×2 = 4+2=6
剩余成本=1×10=10
總成本=6+10=16

第三步：選取最小成本

我們得到三種方案的成本：
方案1：50 → 方案2：32 → 方案3：16
最終最小成本=16，和題目示例輸出完全一致。

補充：三種操作的作用理解（輔助理解）

1.翻轉(zhuǎn)操作：萬能操作，單個位置修復(fù)，成本固定
2.同串交換：批量修復(fù)一對不同類型的不匹配，比兩次翻轉(zhuǎn)更便宜
3.跨串交換：對位交換s和t的字符，配合交換能高效處理批量不匹配

時間復(fù)雜度 & 額外空間復(fù)雜度 1. 時間復(fù)雜度

? 核心操作：逐位遍歷一次字符串，統(tǒng)計不匹配類型，遍歷長度為n
? 后續(xù)計算：都是固定次數(shù)的數(shù)學(xué)運算（常數(shù)時間）
? 總時間復(fù)雜度：O(n)
（線性時間，處理10萬長度的字符串也能高效運行）

2. 額外空間復(fù)雜度

? 僅使用了固定大小的變量：統(tǒng)計用的2×2數(shù)組、a/b/res1/res2/res3等變量
? 無論輸入字符串長度n是多少，占用的額外空間都不會變化
? 總額外空間復(fù)雜度：O(1)
（常數(shù)空間，幾乎不占用額外內(nèi)存）

總結(jié)

1. 核心流程：統(tǒng)計不匹配類型 → 計算三種操作組合成本 → 取最小值
2. 示例中通過「交換+跨串交換+翻轉(zhuǎn)」的組合得到最低成本16
3. 時間復(fù)雜度O(n)，空間復(fù)雜度O(1)，完美適配題目最大數(shù)據(jù)規(guī)模

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科普文章、工具評測、提升效率的秘籍以及行業(yè)洞察。歡迎關(guān)注“福大大架構(gòu)師每日一題”，發(fā)消息可獲得面試資料，讓AI助力您的未來發(fā)展。

特別聲明：以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺“網(wǎng)易號”用戶上傳并發(fā)布，本平臺僅提供信息存儲服務(wù)。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.