最少需要多少次交換才能使給定的子字串中恰好包含K個1

找到子字串剛好包含 K 個 1 所需的最小交換次數是電腦科學和程式設計領域的常見問題。在這篇文章中，我們將深入研究這個問題並為其提供 C 解決方案。這個問題在各個領域都有應用，包括字串操作、資料結構優化和麵試中的編碼挑戰。

問題陳述

給定一個二進位字串和一個數字 K，任務是找到確保字串的每個子字串恰好都有 K 個 1 所需的最小交換次數。

方法

為了解決這個問題，我們可以使用兩個指標方法和滑動視窗技術。基本想法是維護一個大小為K的窗口，並計算窗口中全1所需的交換次數。

範例

這是一個實作上述方法的 C 函數 -

#include<bits/stdc++.h>
using namespace std;

int minSwaps(string s, int K) {
   int n = s.length();
   vector<int> onesPrefix(n, 0);
   if(s[0] == '1') onesPrefix[0] = 1;
   
   for(int i = 1; i < n; i++) {
      onesPrefix[i] = onesPrefix[i-1];
      if(s[i] == '1') onesPrefix[i]++;
   }
   
   int ans = INT_MAX;
   for(int i = 0; i <= n - K; i++) {
      int j = i + K - 1;
      int ones = onesPrefix[j] - ((i == 0) ? 0 : onesPrefix[i - 1]);
      ans = min(ans, K - ones);
   }
   
   return ans;
}

int main() {
   string s = "10010110";
   int K = 3;
   cout << "Minimum number of swaps = " << minSwaps(s, K) << endl;
   return 0;
}

輸出

Minimum number of swaps = 1

測試案例說明

假設字串為“10010110”，K = 3。

在初始二進位字串「10010110」中，我們想要讓每個大小為3的子字串剛好有3個1。例如，子字串“100”需要2次交換才能變成“111”。同樣，子字串「001」也需要2次交換。透過迭代字串，我們發現子字串「101」所需的最小交換次數為 1。

結論

這個問題是一個很好的例子，說明如何將演算法、資料結構和 C 語言的理解結合起來解決複雜的問題。理解和實現此類問題對於軟體工程師來說非常有益，尤其是在程式設計面試和競爭性程式設計中。

以上是最少需要多少次交換才能使給定的子字串中恰好包含K個1的詳細內容。更多資訊請關注PHP中文網其他相關文章！