C ++中K个连续位翻转的最小数目
假设我们有一个数组A。它只包含0和1,这里的K位翻转包括选择一个长度为K的(连续)子数组,同时将子数组中的位取反。我们必须找到所需的最小K位翻转次数,以便数组中不存在0。如果没有这种可能性,则返回-1。
因此,如果输入像[0,0,0,1,0,1,1,0]且K=3,则输出将为3,因为我们需要在第一次尝试中执行三次运算将A[0]翻转为A[3],则数组将为[1,1,1,1,0,1,1,0],第二次运行将A[4]翻转为A[6]将为[1,1,1,1,1,0,0,0],在第三步将A[5]更改为A[7]时,数组将为[1,1,1,1,1,,1,1,1]。
为了解决这个问题,我们将遵循以下步骤-
n:=A的大小
定义大小为n的数组移动
计数器:=0
对于初始化i:=0,当i+K<=n时,更新(将i增加1),执行-
移动[i]:=移动[i]+1
如果i+K<n,则-
(将计数器增加1)
移动[i+K]-=1
移动[i]:=移动[i]+移动[i-1]
如果i>0,则-
如果不是((moves[i]mod2)+A[i])mod2不为零,则-
对于i<n,更新(i增加1),做-
返回-1
移动[i]:=移动[i]+移动[i-1]
如果i>0,则-
如果不是((moves[i]mod2)+A[i])mod2不为零,则-
返回柜台
让我们看下面的实现以更好地理解-
输出结果
#include <bits/stdc++.h> using namespace std; class Solution { public: int minKBitFlips(vector<int>& A, int K){ int n = A.size(); vector<int> moves(n); int i; int counter = 0; for (i = 0; i + K <= n; i++) { if (i > 0) moves[i] += moves[i - 1]; if (!(((moves[i] % 2) + A[i]) % 2)) { moves[i] += 1; if (i + K < n) moves[i + K] -= 1; counter++; } } for (; i < n; i++) { if (i > 0) moves[i] += moves[i - 1]; if (!(((moves[i] % 2) + A[i]) % 2)) return -1; } return counter; } }; main(){ Solution ob; vector<int> v = {0,0,0,1,0,1,1,0}; cout << (ob.minKBitFlips(v, 3)); }
输入项
{0,0,0,1,0,1,1,0}, 3
输出结果
3