数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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]，在第 3 次移动中更改 A[5] 到 A[7]，数组将为 [1,1,1,1,1,1,1,1]。
为了解决这个问题，我们将遵循以下步骤：
n := A 的大小
定义一个大小为 n 的数组 moves
counter := 0
for 初始化 i := 0，当 i + K <= n 时，更新（i 增加 1），执行：
如果 i > 0，则：
moves[i] := moves[i] + moves[i - 1]
如果 (moves[i] mod 2) + A[i] 的模 2 不为零，则：
moves[i] := moves[i] + 1
如果 i + K < n，则：
moves[i + K] - = 1
（counter 增加 1）
for i < n，更新（i 增加 1），执行：
如果 i > 0，则：
moves[i] := moves[i] + moves[i - 1]
如果 (moves[i] mod 2) + A[i] 的模 2 不为零，则：
返回 -1
返回 counter
让我们看看下面的实现以获得更好的理解：
输出
#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
更新于： 2020年6月4日
190 次浏览
广告