Heim > Artikel > Backend-Entwicklung > Wie viele Austausche sind mindestens erforderlich, damit ein gegebener Teilstring genau K 1 enthält?
找到子串恰好包含 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++ 语言的理解结合起来解决复杂的问题。理解和实现此类问题对于软件工程师来说非常有益,尤其是在编码面试和竞争性编程中。
Das obige ist der detaillierte Inhalt vonWie viele Austausche sind mindestens erforderlich, damit ein gegebener Teilstring genau K 1 enthält?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!