使給定子串恰好包含 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++ 語言的理解結合起來，以解決複雜問題。理解和實現此類問題對於軟體工程師，尤其是在編碼面試和競賽程式設計中，都大有裨益。

更新於：2023年5月18日

83 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告